Очереди на регистрацию в аэропорту иногда представляют собой комбинацию этих двух ситуаций. Хотя пассажиры имеют с собой большое количество багажа, в аэропорту все‑таки используются многопоточные очереди, при этом приходится отводить дополнительное место, чтобы пассажиры могли выстроиться в порядке очереди.
Многопоточную очередь просто построить, используя обычную однопоточную очередь. Элементы, представляющие клиентов, хранятся в обычной однопоточной очереди. Когда агент (кассир, банковский служащий и т.д.) освобождается, первый элемент в начале очереди удаляется и передается этому агенту.
Предположим, что вы отвечаете за разработку счетчика регистрации для нового терминала в аэропорту и хотите сравнить возможности одной многопоточной очереди или нескольких однопоточных. Вам потребуется какая‑то модель поведения пассажиров. Для этого примера можно сделать следующие предположения:
=====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 не так эффективны, как реализации на основе массивов, но они очень просты. Коллекции могут подойти для небольших структур данных, если производительность не критична. После тестирования приложения, можно переписать код для стека или очереди, если коллекции окажутся слишком медленными.
В этой главе описаны структуры данных в виде массивов. С помощью 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)
J = X - I * (I - 1) / 2
@Рис. 4.2. Упаковка треугольного массива в одномерном массиве
=====68
Подстановка в эти уравнения X=4 дает I = Int((1 + Sqr(1 + 8 * 4)) / 2) = 3 и J = 4 – 3 * (3 ‑ 1) / 2 = 1. Это означает, что элемент B(4) отображается на позицию A(3,1). Это также соответствует рис. 4.2.
Эти вычисления не слишком просты. Они требуют нескольких умножений и делений, и даже вычисления квадратного корня. Если программе придется выполнять эти функции очень часто, это внесет определенную задержку скорости выполнения. Это пример компромисса между пространством и временем. Упаковка треугольного массива в одномерный массив экономит память, хранение данных в двумерном массиве требует больше памяти, но экономит время.
Используя эти уравнения, можно написать процедуры Visual Basic для преобразования координат между двумя массивами:
Private Sub AtoB(ByVal I As Integer, ByVal J As Integer, X As Integer)
Dim tmp As Integer
If I = J Then ' Незначащий элемент.
X = -1
Exit Sub
ElseIf I < J Then ' Поменять местами I и J.
tmp = I
I = J
J = tmp
End If
X = I * (I - 1) / 2 + J
End Sub
Private Sub BtoA(ByVal X As Integer, I As Integer, J As Integer)
I = Int((1 + Sqr(1 + 8 * X)) / 2)
J = X - I * (I - 1) /2
End Sub
Программа Triang использует эти подпрограммы для работы с треугольными массивами. Если вы нажмете на кнопку A to B (Из A в B), программа пометит элементы в массиве A и скопирует эти метки в соответствующие элементы массива B. Если вы нажмете на кнопку B to A (Из B в A), программа пометит элементы в массиве B, и затем скопирует метки в массив A.
Программа Triangc использует класс TriangularArray для работы с треугольным массивом. При старте программы, она записывает в объект TriangularArray строки, представляющие собой элементы массива. Затем она извлекает и выводит на экран элементы массива.
Некоторые программы используют треугольные массивы, которые включают диагональные элементы A(I, I). В этом случае необходимо внести только три изменения в процедуры преобразования индексов. Процедура преобразования AtoB не должна пропускать случаи с I=J, и должна добавлять к I единицу при подсчете индекса массива B.