Файл: Освой самостоятельно программирование для MS Access 2002 за 24 часа [П.Киммел].pdf

Что еще следует знать о массивах

Массивы просты в использовании, но не достаточно надежны. Чтобы ладить с ни-

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

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

"попадание" последнего в допустимый интервал. Функции Lbound и Dbound — вот

ваши надежные помощники.

При использовании глобальных массивов создайте отдельные функции для выполне-

ния операции изменения их размеров и проверки

 индексов. Хотя подобные

функции окажутся небольшими по объему, ваша программа приобретет ясность и управ-

ляемость — ведь один фрагмент кода исправить гораздо легче, чем несколько, верно?

Сортировка данных

Массивы — простой и удобный инструмент хранения и логической организации

данных. Одна из наиболее распространенных операций, выполняемых над элемента-

ми массивов, — это

 сортировка.

 Существует целый ряд алгоритмов и методов сорти-

ровки. В их числе достаточно назвать метод "пузырька", сортировку посредством вы-
бора и "быструю

Проблемам сортировки посвящено достаточное количество статей, монографий и

учебников.

 жанра" считается

 Numerical Recipes in С: The Art of Scientific Com-

puting

 Уильяма Пресса (William H. Press) (издательство

 Cambridge University Press,

 1993).

Названная работа содержит исчерпывающий свод подробных описаний самых разнооб-

разных алгоритмов и их реализаций на языке программирования С. Существуют и пуб-

ликации, которые специально ориентированы на читателя, нуждающегося в готовых

решениях на языке Visual Basic. Например, обратившись к книге

 Visual

Basic Algorithms

 Рода (Rod) и Кеннета (Kenneth) Стефензов (Stephens) (издательство

 John

Wiley & Sons,

 1998), вы сможете пользоваться приведенной информацией непосредст-

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

программирования на другой. (В числе лучших книг следует упомянуть всемирно из-

вестную монографию Дональда Кнута (Donald E. Knuth)

 Искусство программирования,

т.З. Сортировка и поиск. —

 Изд. дом "Вильяме", 2000. —

На страницах нашей книги представлено три самых популярных, достаточно про-

стых и чрезвычайно эффективных алгоритма сортировки. При нынешних скоростях

процессоров, подбирающихся к гигагерцовым отметкам, даже старенький метод

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

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

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

"быстрой сортировки", с другой, существенно возрастают.

Сортировка методом

Алгоритм "пузырька"

 (Bubble Sort) — неплохой выбор в том случае, если объем

массива не превышает 10000 элементов и данные уже в достаточной мере отсортиро-
ваны. Если говорить кратко, метод состоит в сопоставлении содержимого каждой па-
ры элементов массива и обмене их местами в случае успешного результата сравнения.

При выполнении сортировки по возрастанию значение элемента с индексом  сопос-

тавляется с содержимым следующего элемента —

 Если первая величина превос-

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

(т.е. получить массив, упорядоченный по убыванию), достаточно вместо оператора
сравнения "больше" (>) использовать оператор "меньше" (<). Пример процедуры сор-

тировки, реализующей метод "пузырька", приведен в листинге 12.9.

220 Часть IV. Определение типов данных. Использование массивов и коллекций

Листинг 12.9. Пример сортировки массива с помощью метода "пузырька"

Sub

 As Long,

 I As Long,

 0 As Long)

Dim Temp As Long
Temp =

 (I)

 (I) =

 = Temp

 "Меняем местами

 &

 и

 &

End Sub

Sub BubbleSort (ByRef

 As Long)

Dim I As Long, J As Long
For I =

 Data ) To

 Data

For J = I + 1 To

 Data )

If

 >

 Then

Call Swap ( Data, I, J )

End If

Next J

Next I

End Sub

10:

15:

17:

18:

19:

20:

22:

23: Const Size = 10

Dim

 As Long

Dim I As Long

Randomize Time

For I =

 to

 = Rnd * Size

Next I

 "Начало работы:

 & Time

Call

 "Конец работы:

 & Time

I Для выполнения сортировки по методу "пузырька" необходимо иметь
I два целочисленных индекса -- I и J. Строка

 содержит заголовок

внешнего цикла, а строка 12 — внутреннего. Чтобы сопоставить значение
каждого

 элемента массива с содержимым

 элемента, необхо-

димы именно два цикла. Обратите внимание на начальное значение пе-

ременной внутреннего цикла — J = I + 1 (строка 12). Строка 13 вы-
полняет сравнение значений элементов

 и

 В случае

удачи (когда значение предьщущего элемента окажется большим очеред-
ного последующего) элементы меняются местами — эта операция вы-
полняется с помощью процедуры Swap. Чтобы протестировать подпро-
грамму сортировки, выполните процедуру FillArrayAndSort.

Следует отметить, что метод "пузырька" не заслуживает высокой оцен-
ки. Его частое использование объясняется исключительной простотой.
Столкнувшись с задачей сортировки, вы должны непременно уделить
время изучению характеристики данных и выбору алгоритма, который в

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

 час. Управление данными переменного объема

221

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

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

Все остальное останется в силе. Следует также обратить ваше внимание на значение
верхней границы внешнего цикла,

 - 1. Последний элемент массива

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

Процедура сортировки методом "пузырька" в изложенной выше редакции, приме-

ненная к массиву из 10000 целых чисел, выполняется на компьютере Intel Pentium 800 с
256 Мбайт оперативной памяти приблизительно 51 секунду. Возможно, это мало о чем
говорит, но подобная информация вам пригодится, так как такая скорость работы впол-
не может устроить. В терминах теории вычислительной сложности алгоритмов степень
эффективности метода "пузырька" оценивается функцией

 О(п2).

 Другими словами,

время решения задачи — это квадратичная функция от ее "размерности"

 в данной

ситуации равно числу элементов массива), поскольку в худшем случае программе пред-
стоит выполнить

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

чество операций сравнения ограничено величиной 100000000. Ясно, что при дальней-
шем росте

 п

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

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

Для алгоритма

 сортировки посредством выбора

 (Selection Sort) справедлива та же

оценка эффективности, зависящая от размерности задачи, что и для метода
"пузырька", —

 О( п2 ).

 Отличие метода сортировки посредством выбора состоит в том,

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

позиция текущего элемента относительно остальных. Метод "пузырька" же предполага-
ет перемещение элементов при любом успешном результате теста сравнения.

Листинг 12.10 содержит текст процедуры, реализующей алгоритм сортировки по-

средством выбора. Как и в предыдущем примере, представлены неплохие результаты
при числе элементов, не превосходящем 10000, но с ростом размерности задачи пока-
затели производительности заметно ухудшаются.

Листинг

 Пример сортировки массива посредством выбора

1: Sub

 ) As Long)

2: Dim I As Integer, J As Integer,

 As Integer

3: For I =

 To

 - 1

4: Swaplndex

 I

5: For J = I + 1 To

 Data )

6: If

 >

 Then

7 : Swaplndex = J
8: End If
9: Next J

10: Call

 I, Swaplndex)

 Next I

 Sub

На том же компьютере на сортировку 10000 числовых элементов с помо-

щью алгоритма выбора было затрачено около 19 секунд — налицо повы-
шение эффективности работы примерно на 40%. Рост производительности

существенно зависит от числа реально выполняемых перемещений элемен-

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

упорядоченности исходного множества данных. Алгоритмы отличаются не-
значительно. Обратите внимание на дополнительную переменную Swapln-

dex, объявленную в строке 2. В строке 4 она получает текущее значение I.
В строке 7 вместо "слепого" перемещения элементов запоминается теку-
щее значение индекса J, для которого тест сравнения дал
результат. На очередном

 внутреннего цикла с J-м элементом будет

222 Часть IV. Определение типов данных. Использование массивов и коллекций

сопоставляться уже не

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

 Операция перемещения вынесена за пределы внутреннего

цикла и поэтому выполняется только один раз на каждом шаге внешнего
цикла, т.е. всего  раз вместо потенциальных

 п2

 раз в худшем случае.

Быстрая сортировка

Степень эффективности алгоритма

 быстрой сортировки

 (Quick Sort) оценивается

функцией

 О(п

 где

 — натуральный логарифм от числа

 п.

 Кривая натураль-

ного логарифма с увеличением значения аргумента растет гораздо медленнее, чем,

скажем, парабола квадратичной функции.

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

ной математике красочным классическим изречением

 (divide-and-

conquer). Сортируемый массив делится на части, которые анализируются и при необ-
ходимости вновь подвергаются делению. При значениях данных, близких к случай-

ным, исходное множество делится приблизительно пополам. Если степень упорядо-

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

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

вия алгоритма. Листинг

 демонстрирует пример реализации алгоритма быстрой

сортировки с помощью рекурсивной процедуры Quicksort.

Новый термин

Рекурсивной

 называется процедура или функция, которая в процессе вы-

полнения ссылается сама на себя.

Листинг

 Пример реализации алгоритма "быстрой сортировки"

1:

2:
3 :
4:

6:

7:

Sub

 ByRef

 ) As Long,

 Left As Long,

 Right As Long )

Dim I

 As

 Long, J As Long
 As Long

If (Right > Left) Then

Elem =

 Right )

I = Left - 1
J = Right

Do While (True)

Do

 =

 + 1

Loop  W h i l e

 < Elem)

Do

J = J - 1

If (J <

 Then GoTo Break

Loop While (J >=

 > Elem)

: If (I >= J) Then Exit Do
: Call

 Data, I, J )

: Loop

: Call

 Data, I, Right )

: Call

 Data, Left, I - 1 )

: Call

 Data, I + 1, Right )

: End If

 Sub

10:

11:

14:

15:

16:

18:

19:

20:

21:Break

24:

25:

26:

27:

28:

29

30

31

 час. Управление данными переменного объема

223

 )

33:

34: Const Size = 10 '
35: Dim

 As Long

 Dim I As Long

 Randomize Time

38: For I =

 Data ) To

 Data )

39: Data(I) = Rnd * Size

40: Next

 I

41:

 Call

43:

44:

 "Начало:

 &

 Time

45: Call

 Data,

 Data

 Data ) )

46:

 "Конец:

 & Time

47: Call

 Data )

48:

 Sub

50:
51:

 ) As Integer)

53 : Dim

 As Variant

54: For Each Elem In Data

 Elem

56: Next Elem

 Sub

5 8 :

 ByRef

 ) As Long,

 I As Long,

 J As Long )

60: Dim Temp As Long

 Temp =

  ( I )

62:

 =

63 :

 = Temp

 "Меняем местами

 &

 и  &

 Sub

Анализ

Процедура Quicksort, текст которой размещен в строках

 листин-

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

больших объемах данных — так, целочисленный массив размером 100000

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

же компьютере менее чем за 1 секунду, на сортировку 1 миллиона чисел

ушло приблизительно 10 секунд, а сортировка массива с 10 миллионами

элементов потребовала 2 минуты и 4 секунды.

Функция Dump используется для вывода содержимого сортируемого массива в окне

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

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

В строках

 размещен текст процедуры Swap, обращения к которой содержат-

ся в листингах 12.9,

 и

 Цель наших действий

 создать копию значе-

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

Процедура FillArrayAndSort создает массив, заполняет его случайными значе-

ниями, вызывает процедуру сортировки и выводит на экран справочные данные о

времени, затраченном на решение задачи. С ее помощью можно легко протестировать

 выше процедуры сортировки методом "пузырька" и выбора, если за-

менить выражение в строке 49 соответствующим вызовом.

Строки

 содержат процедуру Quicksort — это характерный случай, когда размер

кода подпрофаммы может превышать пределы нескольких строк. (В принципе, процедуру

Quicksort нетрудно и сократить, если вынести цикл, охватывающий строки

 в от-

дельный именованный блок.) Интерфейс подпрофаммы (строка 1) описывается тремя па-

224 Часть IV. Определение типов данных. Использование массивов и коллекций