Предыдущая страница реферата | 21  22  23  24  25  26  27  28  29  30  31 | Следующая страница реферата

value = Queue(QueueFront)
QueueFront = (QueueFront + 1) Mod QueueSize

@Рис. 3.2. Циклическая очередь

=======55

@Рис. 3.3. Добавление элемента к циклической очереди

На рис. 3.4 показан процесс удаления элемента из циклической очереди.
Первый элемент, в данном случае элемент A, удаляется из начала очереди, и указатель на начало очереди обновляется, указывая на следующий элемент массива.
Для циклических очередей иногда бывает сложно отличить пустую очередь от полной. В обоих случаях значения переменных QueueBottom и QueueTop будут равны. На рис. 3.5 показаны две циклические очереди, пустая и полная.
Простой вариант решения этой проблемы — сохранять число элементов в очереди в отдельной переменной NumInQueue. При помощи этого счетчика можно узнать, остались ли в очереди еще элементы, и осталось ли в очереди место для новых элементов.

@Рис. 3.4. Удаление элемента из циклической очереди

@Рис. 3.5 Полная и пустая циклическая очереди

=========56

Следующий код использует все эти методы для управления циклической очередью:

Queue() As String ' Массив очереди.
QueueSize As Integer ' Наибольший индекс в очереди.
QueueFront As Integer ' Начало очереди.
QueueBack As Integer ' Конец очереди.
NumInQueue As Integer ' Число элементов в очереди.

Sub NewCircularQueue(num_items As Integer)

QueueSize = num_items

ReDim Queue(0 To QueueSize - 1)
End Sub

Sub EnterQueue(value As String)

' Если очередь заполнена, выйти из процедуры.

' В настоящем приложении потребуется более сложный код.

If NumInQueue >= QueueSize Then Exit Sub

Queue(QueueBack) = value

QueueBack = (QueueBack + 1) Mod QueueSize

NumInQueue = NumInQueue + 1
End Sub

Sub LeaveQueue (value As String)

' Если очередь пуста, выйти из процедуры.

' В настоящем приложении потребуется более сложный код.

If NumInQueue = QueueSize Then ResizeQueue

Queue(QueueBack) = value

QueueBack = (QueueBack + 1) Mod QueueSize

NumInQueue = NumInQueue + 1
End Sub

Private Sub LeaveQueue(value As String)

If NumInQueue new_priority cell = nxt nxt = cell.NextCell

Loop

' Вставить элемент после ячейки в списке.

:

Для удаления из списка элемента с наивысшим приоритетом, просто удаляется элемент после сигнальной метки начала. Так как список отсортирован в порядке приоритетов, первый элемент всегда имеет наивысший приоритет.
Добавление нового элемента в эту очередь занимает в среднем N/2 шагов.
Иногда новый элемент будет оказываться в начале списка, иногда ближе к концу, но в среднем он будет оказываться где-то в середине. Простая очередь на основе списка требовала O(1) шагов для добавления нового элемента и O(N) шагов для удаления элементов с наивысшим приоритетом из очереди. Версия на основе упорядоченного связного списка требует O(N) шагов для добавления элемента и O(1) шагов для удаления верхнего элемента. Обеим версиям требует
O(N) шагов для одной из этих операций, но в случае упорядоченного связного списка в среднем требуется только (N/2) шагов.
Программа PriList использует упорядоченный связный список для работы с приоритетной очередью. Вы можете задать приоритет и значение элемента данных и нажать кнопку Enter для добавления его в приоритетную очередь.
Нажмите на кнопку Leave для удаления из очереди элемента с наивысшим приоритетом.
Программа PriList2 аналогична программе PriList, но она использует для управления очередью класс LinkedPriorityQueue.

========63

Затратив еще немного усилий, можно построить приоритетную очередь, в которой добавление и удаление элемента потребуют порядка O(log(N)) шагов.
Для очень больших очередей, ускорение работы может стоить этих усилий. Этот тип приоритетных очередей использует структуры данных в виде пирамиды, которые также применяются в алгоритме пирамидальной сортировки. Пирамиды и приоритетные очереди на их основе обсуждаются более подробно в 9 главе.

Многопоточные очереди

Интересной разновидностью очередей являются многопоточные очереди (multi- headed queues). Элементы, как обычно, добавляются в конец очереди, но очередь имеет несколько потоков (front end) или голов (heads). Программа может удалять элементы из любого потока.
Примером многопоточной очереди в обычной жизни является очередь клиентов в банке. Все клиенты находятся в одной очереди, но их обслуживает несколько служащих. Освободившийся банковский работник обслуживает клиента, который находится в очереди первым. Такой порядок обслуживания кажется справедливым, поскольку клиенты обслуживаются в порядке прибытия. Он также эффективен, так как все служащие остаются занятыми до тех пор, пока клиенты ждут в очереди.
Сравните этот тип очереди с несколькими однопоточными очередями в супермаркете, в которых покупатели не обязательно обслуживаются в порядке прибытия. Покупатель в медленно движущейся очереди, может прождать дольше, чем тот, который подошел позже, но оказался в очереди, которая продвигается быстрее. Кассиры также могут быть не всегда заняты, так как какая-либо очередь может оказаться пустой, тогда как в других еще будут находиться покупатели.
В общем случае, многопоточные очереди более эффективны, чем несколько однопоточных очередей. Последний вариант используется в супермаркетах потому, что тележки для покупок занимают много места. При использовании многопоточной очереди всем покупателям пришлось бы построиться в одну очередь. Когда кассир освободится, покупателю пришлось бы переместиться с громоздкой тележкой к кассиру. С другой стороны, в банке посетителям не нужно двигать большие тележки для покупок, поэтому они легко могут уместиться в одной очереди.
Очереди на регистрацию в аэропорту иногда представляют собой комбинацию этих двух ситуаций. Хотя пассажиры имеют с собой большое количество багажа, в аэропорту все-таки используются многопоточные очереди, при этом приходится отводить дополнительное место, чтобы пассажиры могли выстроиться в порядке очереди.
Многопоточную очередь просто построить, используя обычную однопоточную очередь. Элементы, представляющие клиентов, хранятся в обычной однопоточной очереди. Когда агент (кассир, банковский служащий и т.д.) освобождается, первый элемент в начале очереди удаляется и передается этому агенту.

Модель очереди

Предположим, что вы отвечаете за разработку счетчика регистрации для нового терминала в аэропорту и хотите сравнить возможности одной многопоточной очереди или нескольких однопоточных. Вам потребуется какая-то модель поведения пассажиров. Для этого примера можно сделать следующие предположения:

=====63

1. регистрация каждого пассажира занимает от двух до пяти минут;
2. при использовании нескольких однопоточных очередей, прибывающие пассажиры встают в самую короткую очередь;
3. скорость поступления пассажиров примерно неизменна.
Программа HeadedQ моделирует эту ситуацию. Вы можете менять некоторые параметры модели, включая следующие:
4. число прибывающих в течение часа пассажиров;
5. минимальное и максимальное затрачиваемое время;
6. число свободных служащих;
7. паузу между шагами программы в миллисекундах.
При выполнении программы, модель показывает прошедшее время, среднее и максимальное время ожидания пассажирами обслуживания, и процент времени, в течение которого служащие заняты.
При экспериментировании с различными значениями параметров, вы заметите несколько любопытных моментов. Во-первых, для многопоточной очереди среднее и максимальное время ожидания будет меньше. При этом, служащие также оказываются немного более загружены, чем в случае однопоточной очереди.
Для обоих типов очереди есть порог, при котором время ожидания пассажиров значительно возрастает. Предположим, что на обслуживание одного пассажира требуется от 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 непосредственно. К этим типа относятся треугольные массивы, нерегулярные массивы и разреженные массивы. В этой главе объясняется, как можно использовать гибкие структуры массивов, которые могут значительно снизить объем занимаемой памяти.

Треугольные массивы

Рекомендуем скачать другие рефераты по теме: доклад по химии, конспект зима.



Предыдущая страница реферата | 21  22  23  24  25  26  27  28  29  30  31 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки