VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

число шагов, которое нужно для построения всех пирамид, меньше, чем 2H*2.

Так как H — высота дерева, равная log(N), то полное число шагов меньше, чем

2log(N)*2=N*2. Это означает, что для первоначального построения пирамиды

требуется порядка O(N) шагов.

Для удаления элемента из приоритетной очереди, последний элемент

перемещается на вершину дерева. Затем он продвигается вниз, пока не займет

свое окончательное положение, и дерево снова не станет пирамидой. Так как

дерево имеет высоту log(N), процесс может занять не более log(N) шагов. Это

означает, что новый элемент к приоритетной очереди на основе пирамиды можно

добавить за O(log(N)) шагов.

Другим способом работы с приоритетными очередями является использование

упорядоченного списка. Вставка или удаление элемента из упорядоченного

списка с миллионом элементов занимает примерно миллион шагов. Вставка или

удаление элемента из сопоставимой по размерам приоритетной очереди,

основанной на пирамиде, занимает всего 20 шагов.

======253

Алгоритм пирамидальной сортировки

Алгоритм пирамидальной сортировки просто использует уже описанные алгоритмы

для работы с пирамидами. Идея состоит в том, чтобы создать приоритетную

очередь и последовательно удалять по одному элементу из очереди.

Для удаления элемента алгоритм меняет его местами с последним элементом в

пирамиде. Это помещает удаленный элемент в конечное положение в конце

массива. Затем алгоритм уменьшает счетчик элементов списка, чтобы исключить

из рассмотрения последнюю позицию

После того, как наибольший элемент поменялся местами с последним, массив

больше не является пирамидой, так как новый элемент на вершине может

оказаться меньше, чем его потомки. Поэтому алгоритм использует процедуру

HeapPushDown для продвижения элемента на его место. Алгоритм продолжает

менять элементы местами и восстанавливать пирамиду до тех пор, пока в

пирамиде не останется элементов.

Public Sub Heapsort(List() As Long, ByVal min As Long, ByVal max As Long)

Dim i As Long

Dim tmp As Long

' Создать пирамиду (кроме корневого узла).

For i = (max + min) \ 2 To min + 1 Step -1

HeapPushDown List(), i, max

Next i

' Повторять:

' 1. Продвинуться вниз по пирамиде.

' 2. Выдать корень.

For i = max To min + 1 Step -1

' Продвинуться вниз по пирамиде.

HeapPushDown List(), min, i

' Выдать корень.

tmp = List(min)

List(min) = List(i)

List(i) = tmp

Next i

End Sub

Предыдущее обсуждение приоритетных очередей показало, что первоначальное

построение пирамиды требует O(N) шагов. После этого требуется O(log(N))

шагов для восстановления пирамиды, когда элемент продвигается на свое

место. Пирамидальная сортировка выполняет это действие N раз, поэтому

требуется всего порядка O(N)*O(log(N))=O(N*log(N)) шагов, чтобы получить из

пирамиды упорядоченный список. Полное время выполнения для алгоритма

пирамидальной сортировки составляет порядка O(N)+O(N*log(N))=O(N*log(N)).

=========254

Такой же порядок сложности имеет алгоритм сортировки слиянием и в среднем

алгоритм быстрой сортировки. Так же, как и сортировка слиянием,

пирамидальная сортировка тоже не зависит от значений или распределения

элементов до начала сортировки. Быстрая сортировка плохо работает со

списками, содержащими большое число одинаковых элементов, а сортировка

слиянием и пирамидальная сортировка лишены этого недостатка.

Хотя обычно пирамидальная сортировка работает немного медленнее, чем

сортировка слиянием, для нее не требуется дополнительного пространства для

хранения временных значений, как для сортировки слиянием. Пирамидальная

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

пределах исходного массива списка.

Сортировка подсчетом

Сортировка подсчетом (countingsort) — специализированный алгоритм, который

очень хорошо работает, если элементы данных — целые числа, значения которых

находятся в относительно узком диапазоне. Этот алгоритм работает достаточно

быстро, например, если значения находятся между 1 и 1000.

Если список удовлетворяет этим требованиям, сортировка подсчетом

выполняется невероятно быстро. В одном из тестов на компьютере с

процессором Pentium с тактовой частотой 90 МГц, быстрая сортировка 100.000

элементов со значениями между 1 и 1000 заняла 24,44 секунды. Для сортировки

тех же элементов сортировке подсчетом потребовалось всего 0,88 секунд — в

27 раз меньше времени.

Выдающаяся скорость сортировки подсчетом достигается за счет того, что при

этом не используются операции сравнения. Ранее в этой главе отмечалось, что

время выполнения любого алгоритма сортировки, использующего операции

сравнения, порядка O(N*log(N)). Без использования операций сравнения,

алгоритм сортировки подсчетом позволяет упорядочивать элементы за время

порядка O(N).

Сортировка подсчетом начинается с создания массива для подсчета числа

элементов, имеющих определенное значение. Если значения находятся в

диапазоне между min_value и max_value, алгоритм создает массив Counts с

нижней границей min_value и верхней границей max_value. Если используется

массив из предыдущего прохода, необходимо обнулить значения его элементов.

Если существует M значений элементов, массив содержит M записей, и время

выполнения этого шага порядка O(M).

For i = min To max

Counts(List(i)) = Counts(List(i)) + 1

Next i

В конце концов, алгоритм обходит массив Counts, помещая соответствующее

число элементов в отсортированный массив. Для каждого значения i между

min_value и max_value, он помещает Counts(i) элементов со значением i в

массив. Так как этот шаг помещает по одной записи в каждую позицию в

массиве, он требует порядка O(N) шагов.

new_index = min

For i = min_value To max_value

For j = 1 To Counts(i)

sorted_list(new_index) = i

new_index = new_index + 1

Next j

Next i

======255

Алгоритм целиком требует порядка O(M)+O(N)+O(N)=O(M+N) шагов. Если M мало

по сравнению с N, он выполняется очень быстро. Например, если M Value Then min_value = Value

If max_value < Value Then max_value = Value

Set item = item.NextCell

Loop

' Если min_value = max_value, значит, есть единственное

' значение, и список отсортирован.

If min_value = max_value Then Exit Sub

' Если в списке не более, чем CutOff элементов,

' завершить сортировку процедурой LinkInsertionSort.

If count Value Then min_value = Value

If max_value < Value Then max_value = Value

Next i

' Если min_value = max_value, значит, есть единственное

' значение, и список отсортирован.

If min_value = max_value Then Exit Sub

' Создать пустой массив с отсчетами блоков.

ReDim counts(l To NumBuckets)

value_scale = _

CDbl (NumBuckets - 1) / _

CDbl (max_value - min_value)

' Создать отсчеты блоков.

For i = min To max

If List(i) = max_value Then

bucket_num = NumBuckets

Else

bucket_num = _

Int((List(i) - min_value) * _

value_scale) + 1

End If

counts(bucket_num) = counts(bucket_num) + 1

Next i

' Преобразовать отсчеты в смещение в массиве.

ReDim offsets(l To NumBuckets)

next_spot = min

For i = 1 To NumBuckets

offsets(i) = next_spot

next_spot = next_spot + counts(i)

Next i

' Разместить значения в соответствующих блоках.

For i = min To max

If List(i) = max_value Then

bucket_num = NumBuckets

Else

bucket_num = _

Int((List(i) - min_value) * _

value_scale) + 1

End If

Scratch (offsets (bucket_num)) = List(i)

offsets(bucket_num) = offsets(bucket_num) + 1

Next i

' Рекурсивная сортировка блоков, содержащих

' более одного элемента.

next_spot = min

For i = 1 To NumBuckets

If counts(i) > 1 Then ArrayBucketSort _

Scratch(), List(), next_spot, _

next_spot + counts(i) - 1, counts(i)

next_spot = next_spot + counts(i)

Next i

' Скопировать временный массив назад в исходный список.

For i = min To max

List(i) = Scratch(i)

Next i

End Sub

Из-за накладных расходов, которые требуются для работы со связными

списками, эта версия блочной сортировки работает намного быстрее, чем

версия с использованием связных списков. Тем не менее, используя методы

работы с псевдоуказателями, описанные во 2 главе, можно улучшить

производительность версии с использованием связных списков, так что обе

версии станут практически эквивалентными по скорости.

Новую версию также можно сделать еще быстрее, используя функцию API MemCopy

для копирования элементов из временного массива обратно в исходный список.

Эта усовершенствованную версию алгоритма демонстрирует программа FastSort.

===========259-261

Резюме

В таб. 9.4 приведены преимущества и недостатки алгоритмов сортировки,

описанных в этой главе, из которых можно вывести несколько правил, которые

могут помочь вам выбрать алгоритм сортировки.

Эти правила, изложенные в следующем списке, и информация в табл. 9.4 может

помочь вам подобрать алгоритм, который обеспечит максимальную

производительность:

10. если вам нужно быстро реализовать алгоритм сортировки, используйте

быструю сортировку, а затем при необходимости поменяйте алгоритм;

11. если более 99 процентов списка уже отсортировано, используйте

пузырьковую сортировку;

12. если список очень мал (100 или менее элементов), используйте сортировку

выбором;

13. если значения находятся в связном списке, используйте блочную

сортировку на основе связного списка;

14. если элементы в списке — целые числа, разброс значений которых невелик

(до нескольких тысяч), используйте сортировку подсчетом;

15. если значения лежат в широком диапазоне и не являются целыми числами,

используйте блочную сортировку на основе массива;

16. если вы не можете тратить дополнительную память, которая требуется для

блочной сортировки, используйте быструю сортировка

Если вы знаете структуру данных и различные алгоритмы сортировки, вы можете

выбрать алгоритм, наиболее подходящий для ваших нужд.

@Таблица 9.4. Преимущества и недостатки алгоритмов сортировки

=========263

Глава 10. Поиск

После того, как список элементов отсортирован, может понадобиться найти

определенный элемент в списке. В этой главе описаны некоторые алгоритмы для

поиска элементов в упорядоченных списках. Она начинается с краткого

описания сортировки методом полного перебора. Хотя этот алгоритм

выполняется не так быстро, как другие, метод полного перебора является

очень простым, что облегчает его реализацию и отладку. Из-за простоты этого

метода, сортировка полным перебором также выполняется быстрее других

алгоритмов для очень маленьких списков.

Далее в главе описан двоичный поиск. При двоичном поиске список многократно

разбивается на части, при этом для больших списков такой поиск выполняется

намного быстрее, чем полный перебор. Заключенная в этом методе идея

достаточно проста, но реализовать ее довольно сложно.

Затем в главе описан интерполяционный поиск. Так же, как и в методе

двоичного поиска, исходный список при этом многократно разбивается на

части. При использовании интерполяционного поиска, алгоритм делает

предположения о том, где может находиться искомый элемент, поэтому он

выполняется намного быстрее, если данные в списках распределены равномерно.

В конце главы обсуждаются методы следящего поиска. Применение этого метода

иногда уменьшает время поиска в несколько раз.

Примеры программ

Программа Search демонстрирует все описанные в главе алгоритмы. Введите

значение элементов, которые должен содержать список, и затем нажмите на

кнопку Make List (Создать список), и программа создаст список на основе

массива, в котором каждый элемент больше предыдущего на число от 0 до 5.

Программа выводит значение наибольшего элемента в списке, чтобы вы

представляли диапазон значений элементов.

После создания списка выберите алгоритмы, которые вы хотите использовать,

установив соответствующие флажки. Затем введите значение, которое вы хотите

найти и нажмите на кнопку Search (Поиск), и программа выполнит поиск

элемента при помощи выбранного вами алгоритма. Так как список содержит не

все возможные элементы в заданном диапазоне значений, то вам может

понадобиться ввести несколько различных значений, прежде чем одно из них

найдется в списке.

Программа также позволяет задать число повторений для каждого из алгоритмов

поиска. Некоторые алгоритмы выполняются очень быстро, поэтому для того,

чтобы сравнить их скорость, может понадобиться задать для них большое число

повторений.

=======265

На рис. 10.1 показано окно программы Search после поиска элемента со

значением 250.000. Этот элемент находился на позиции 99.802 в списке из

100.000 элементов. Чтобы найти этот элемент, потребовалось проверить 99.802

элемента при использовании алгоритма полного перебора, 16 элементов — при

использовании двоичного поиска и всего 3 — при выполнении интерполяционного

поиска.

Поиск методом полного перебора

При выполнении линейного (linear) поиска или поиска методом полного

перебора (exhaustive search), поиск ведется с начала списка, и элементы

перебираются последовательно, пока среди них не будет найден искомый.

Public Function LinearSearch(target As Long) As Long

Dim i As Long

For i = 1 To NumItems

If List(i) >= target Then Exit For

Next i

If i > NumItems Then

Search = 0 ' Элемент не найден.

Else

Search = i ' Элемент найден.

End If

End Function

Так как этот алгоритм проверяет элементы последовательно, то он находит

элементы в начале списка быстрее, чем элементы, расположенные в конце.

Наихудший случай для этого алгоритма возникает, если элемент находится в

конце списка или вообще не присутствует в нем. В этих случаях, алгоритм

проверяет все элементы в списке, поэтому время его выполнения сложность в

наихудшем случае порядка O(N).

@Рис. 10.1. Программа Search

========266

Если элемент находится в списке, то в среднем алгоритм проверяет N/2

элементов до того, как обнаружит искомый. Таким образом, в усредненном

случае время выполнения алгоритма также порядка O(N).

Хотя алгоритмы, которые выполняются за время порядка O(N), не являются

очень быстрыми, этот алгоритм достаточно прост, чтобы давать на практике

неплохие результаты. Для небольших списков этот алгоритм имеет приемлемую

производительность.

Поиск в упорядоченных списках

Если список упорядочен, то можно слегка модифицировать алгоритм полного

перебора, чтобы немного повысить его производительность. В этом случае,

если во время выполнения поиска алгоритм находит элемент со значением,

большим, чем значение искомого элемента, то он завершает свою работу. При

этом искомый элемент не находится в списке, так как иначе он бы встретился

раньше.

Например, предположим, что мы ищем значение 12 и дошли до значения 17. При

этом мы уже прошли тот участок списка, в котором мог бы находится элемент

со значением 12, значит, элемент 12 в списке отсутствует. Следующий код

демонстрирует доработанную версию алгоритма поиска полным перебором:

Public Function LinearSearch(target As Long) As Long

Dim i As Long

NumSearches = 0

For i = 1 To NumItems

NumSearches = NumSearches + 1

If List(i) >= target Then Exit For

Next i

If i > NumItems Then

LinearSearch = 0 ' Элемент не найден.

ElseIf List(i) <> target Then

LinearSearch = 0 ' Элемент не найден.

Else

LinearSearch = i ' Элемент найден.

End If

End Function

Эта модификация уменьшает время выполнения алгоритма, если элемент

отсутствует в списке. Предыдущей версии поиска требовалось проверить весь

список до конца, если искомого элемента в нем не было. Новая версия

остановится, как только обнаружит элемент больший, чем искомый.

Если искомый элемент расположен случайно между наибольшим и наименьшим

элементами в списке, то в среднем алгоритму понадобится порядка O(N) шагов,

чтобы определить, что искомый элемент отсутствует в списке. Время

выполнения при этом имеет тот же порядок, но на практике его

производительность будет немного выше. Программа Search использует эту

версию алгоритма.

======267

Поиск в связных списках

Поиск методом полного перебора — это единственный способ поиска в связных

списках. Так как доступ к элементам возможен только при помощи указателей

NextCell на следующий элемент, то необходимо проверить по очереди все

элементы с начала списка, чтобы найти искомый.

Так же, как и в случае поиска полным перебором в массиве, если список

упорядочен, то можно прекратить поиск, если найдется элемент со значением,

большим, чем значение искомого элемента.

Public Function LListSearch(target As Long) As SearchCell

Dim cell As SearchCell

NumSearches = 0

Set cell = ListTop.NextCell

Do While Not (cell Is Nothing)

NumSearches = NumSearches + 1

If cell.Value >= target Then Exit Do

Set cell = cell.NextCell

Loop

If Not (cell Is Nothing) Then

If cell.Value = target Then

Страницы: 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