Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
Примером многопоточной очереди в обычной жизни является очередь клиентов в банке. Все клиенты находятся в одной очереди, но их обслуживает несколько служащих. Освободившийся банковский работник обслуживает клиента, который находится в очереди первым. Такой порядок обслуживания кажется справедливым, поскольку клиенты обслуживаются в порядке прибытия. Он также эффективен, так как все служащие остаются занятыми до тех пор, пока клиенты ждут в очереди.
Сравните этот тип очереди с несколькими однопоточными очередями в супермаркете, в которых покупатели не обязательно обслуживаются в порядке прибытия. Покупатель в медленно движущейся очереди, может прождать дольше, чем тот, который подошел позже, но оказался в очереди, которая продвигается быстрее. Кассиры также могут быть не всегда заняты, так как какая‑либо очередь может оказаться пустой, тогда как в других еще будут находиться покупатели.
В общем случае, многопоточные очереди более эффективны, чем несколько однопоточных очередей. Последний вариант используется в супермаркетах потому, что тележки для покупок занимают много места. При использовании многопоточной очереди всем покупателям пришлось бы построиться в одну очередь. Когда кассир освободится, покупателю пришлось бы переместиться с громоздкой тележкой к кассиру. С другой стороны, в банке посетителям не нужно двигать большие тележки для покупок, поэтому они легко могут уместиться в одной очереди.
Очереди на регистрацию в аэропорту иногда представляют собой комбинацию этих двух ситуаций. Хотя пассажиры имеют с собой большое количество багажа, в аэропорту все‑таки используются многопоточные очереди, при этом приходится отводить дополнительное место, чтобы пассажиры могли выстроиться в порядке очереди.
Многопоточную очередь просто построить, используя обычную однопоточную очередь. Элементы, представляющие клиентов, хранятся в обычной однопоточной очереди. Когда агент (кассир, банковский служащий и т.д.) освобождается, первый элемент в начале очереди удаляется и передается этому агенту.
Модель очереди
Предположим, что вы отвечаете за разработку счетчика регистрации для нового терминала в аэропорту и хотите сравнить возможности одной многопоточной очереди или нескольких однопоточных. Вам потребуется какая‑то модель поведения пассажиров. Для этого примера можно сделать следующие предположения:
=====63
* регистрация каждого пассажира занимает от двух до пяти минут;
* при использовании нескольких однопоточных очередей, прибывающие пассажиры встают в самую короткую очередь;
* скорость поступления пассажиров примерно неизменна.
Программа HeadedQ моделирует эту ситуацию. Вы можете менять некоторые параметры модели, включая следующие:
* число прибывающих в течение часа пассажиров;
* минимальное и максимальное затрачиваемое время;
* число свободных служащих;
* паузу между шагами программы в миллисекундах.
При выполнении программы, модель показывает прошедшее время, среднее и максимальное время ожидания пассажирами обслуживания, и процент времени, в течение которого служащие заняты.
При экспериментировании с различными значениями параметров, вы заметите несколько любопытных моментов. Во-первых, для многопоточной очереди среднее и максимальное время ожидания будет меньше. При этом, служащие также оказываются немного более загружены, чем в случае однопоточной очереди.
Для обоих типов очереди есть порог, при котором время ожидания пассажиров значительно возрастает. Предположим, что на обслуживание одного пассажира требуется от 2 до 10 минут, или в среднем 6 минут. Если поток пассажиров составляет 60 человек в час, тогда персонал потратит около 6*60=360 минут в час на обслуживание всех пассажиров. Разделив это значение на 60 минут в часе, получим, что для обслуживания клиентов в этом случае потребуется 6 клерков.
Если запустить программу HeadedQ с этими параметрами, вы увидите, что очереди движутся достаточно быстро. Для многопоточной очереди время ожидания составит всего несколько минут. Если добавить еще одного служащего, чтобы всего было 7 служащих, среднее и максимальное время ожидания значительно уменьшатся. Среднее время ожидания упадет примерно до одной десятой минуты.
С другой стороны, если уменьшить число служащих до 5, это приведет к большому увеличению среднего и максимального времени ожидания. Эти показатели также будут расти со временем. Чем дольше будет работать программа, тем дольше будут задержки.
@Таблица 3.1. Время ожидания в минутах для одно‑ и многопоточных очередей
======64
@Рис. 3.9. Программа HeadedQ
В табл. 3.1 приведены среднее и максимальное время ожидания для 2 разных типов очередей. Программа моделирует работу в течение 3 часов и предполагает, что прибывает 60 пассажиров в час и на обслуживание каждого из них уходит от 2 до 10 минут.
Многопоточная очередь также кажется более справедливой, так как пассажиры обслуживаются в порядке прибытия. На рис. 3.9 показана программа HeadedQ после моделирования чуть более, чем двух часов работы терминала. В многопоточной очереди первым стоит пассажир с номером 104. Все пассажиры, прибывшие до него, уже обслужены или обслуживаются в настоящий момент. В однопоточной очереди, обслуживается пассажир с номером 106. Пассажиры с номерами 100, 102, 103 и 105 все еще ждут своей очереди, хотя они и прибыли раньше, чем пассажир с номером 106.
Резюме
Разные реализации стеков и очередей обладают различными свойствами. Стеки и циклические очереди на основе массивов просты и эффективны, в особенности, если заранее известно насколько большим может быть их размер. Связные списки обеспечивают большую гибкость, если размер списка часто изменяется.
Стеки и очереди на основе коллекций Visual Basic не так эффективны, как реализации на основе массивов, но они очень просты. Коллекции могут подойти для небольших структур данных, если производительность не критична. После тестирования приложения, можно переписать код для стека или очереди, если коллекции окажутся слишком медленными.
Глава 4. МассивыВ этой главе описаны структуры данных в виде массивов. С помощью Visual Basic вы можете легко создавать массивы данных стандартных или определенных пользователем типов. Если определить массив без границ, затем можно изменять его размер при помощи оператора ReDim. Эти свойства делают применение массивов в Visual Basic очень полезным.
Некоторые программы используют особые типы массивов, которые не поддерживаются Visual Basic непосредственно. К этим типа относятся треугольные массивы, нерегулярные массивы и разреженные массивы. В этой главе объясняется, как можно использовать гибкие структуры массивов, которые могут значительно снизить объем занимаемой памяти.
Треугольные массивы
Некоторым программам требуется только половина элементов в двумерном массиве. Предположим, что мы располагаем картой, на которой 10 городов обозначены цифрами от 0 до 9. Можно использовать массив для создания матрицы смежности (adjacency matrix), показывающей наличие автострады между парами городов. Элемент A(I,J) равен True, если между городами I и J есть автострада.
В этом случае, значения в половине матрицы будут дублировать значения в другой ее половине, так как A(I, J)=A(J, I). Также элемент A(I, I) не имеет смысла, так как бессмысленно строить автостраду из города I в тот же самый город. В действительности потребуются только элементы A(I,J) из верхнего левого угла, для которых I > J. Вместо этого можно также использовать элементы из верхнего правого угла. Поскольку эти элементы образуют треугольник, этот тип массивов называется треугольным массивом (triangular array).
На рис. 4.1 показан треугольный массив. Элементы со значащими данными обозначены буквой X, ячейки, соответствующие дублирующимся элементам, оставлены пустыми. Незначащие элементы A(I,I) обозначены тире.
Для небольших массивов потери памяти при использовании обычных двумерных массивов для хранения таких данных не слишком существенны. Если же на карте много городов, потери памяти могут быть велики. Для N городов эти потери составят N*(N-1)/2 дублирующихся элементов и N незначащих диагональных элементов A(I,I). Если карта содержит 1000 городов, в массиве будет более полумиллиона ненужных элементов.
====67
@Рис. 4.1. Треугольный массив
Избежать потерь памяти можно, создав одномерный массив B и упаковав в него значащие элементы из массива A. Разместим элементы в массиве B по строкам, как показано на рис. 4.2. Заметьте, что индексы массивов начинаются с нуля. Это упрощает последующие уравнения.
Для того, чтобы упростить использование этого представления треугольного массива, можно написать функции для преобразования индексов массивов A и B. Уравнение для преобразования индекса A(I,J) в B(X) выглядит так:
X = I * (I - 1) / 2 + J ' Для I > J.
Например, для I=2 и J=1 получим X = 2 * (2 - 1) / 2 + 1 = 2. Это значит, что A(2,1) отображается на 2 позицию в массиве B, как показано на рис. 4.2. Помните, что массивы нумеруются с нуля.
Уравнение остается справедливым только для I > J. Значения других элементов массива A не сохраняются в массиве B, потому что они являются избыточными или незначащими. Если вам нужно получить значение A(I,J) при I < J, вместо этого следует вычислять значение A(J,I).
Уравнения для обратного преобразования B(X) в A(I,J) выглядит так:
I = Int((1 + Sqr(1 + 8 * X)) / 2)
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82
