Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
End Type
‘ Выделить память под записи.
Dim EmloyeeData(1 To 10000)
Чтобы отсортировать сотрудников по идентификационному номеру, нужно создать таблицу индексов, которая содержит индексы и значения ID values из записей. Индекс элемента показывает, какая запись в массиве EmployeeData содержит соответствующие данные.
Type IdIndex
ID As Integer
Index As Integer
End Type
‘ Таблица индексов.
Dim IdIndexData(1 To 10000)
Проинициализируем таблицу индексов так, чтобы первый индекс указывал на первую запись данных, второй — на вторую, и т.д.
For i = 1 To 10000
IdIndexData(i).ID = EmployeeData(i).ID
IdIndexData(i).Index = i
Next i
Затем, отсортируем таблицу индексов по идентификационному номеру ID. После этого, поле Index в каждом элементе IdIndexData указывает на соответствующую запись данных. Например, первая запись в отсортированном списке — это EmployeeData(IdIndexData(1).Index). На рис. 9.1 показана взаимосвязь между индексом и записью данных до, и после сортировки.
=======226
@Рисунок 9.1. Сортировка с помощью таблицы индексов
Для того, чтобы сортировать данные в разном порядке, можно создать несколько различных таблиц индексов и управлять ими по отдельности. В приведенном примере можно было бы создать еще одну таблицу индексов, упорядочивающую сотрудников по фамилии. Подобно этому списки со ссылками могут сортировать список различными способами, как показано во 2 главе. При добавлении или удалении записи необходимо обновлять каждую таблицу индексов независимо.
Помните, что таблицы индексов занимают дополнительную память. Если создать по таблице индексов для каждого из полей данных, объем занимаемой памяти более чем удвоится.
Объединение и сжатие ключей
Иногда можно хранить ключи списка в комбинированной или сжатой форме. Например, можно было бы объединить (combine) в программе два поля, соответствующих имени и фамилии, в одни ключ. Это позволило бы упростить и ускорить сравнение. Обратите внимание на различия между двумя следующими фрагментами кода, которые сравнивают две записи о сотрудниках:
‘ Используя разные ключи.
If emp1.LastName > emp2.LastName Or _
(emp1.LastName = emp2.LastName And _
And emp1.FirstName > emp2.FirstName) Then
DoSomething
‘ Используя объединенный ключ.
If emp1.CominedName > emp2.CombinedName Then
DoSomething
========227
Также иногда можно сжимать (compress) ключи. Сжатые ключи занимают меньше места, уменьшая размер таблиц индексов. Это позволяет сортировать списки большего размера без перерасхода памяти, быстрее перемещать элементы в списке, и часто также ускоряет сравнение элементов.
Одни из методов сжатия строк — кодирование их целыми числами или данными другого числового формата. Числовые данные занимают меньше места, чем строки и сравнение двух численных значений также происходит намного быстрее, чем сравнение двух строк. Конечно, строковые операции неприменимы для строк, представленных числами.
Например, предположим, что мы хотим закодировать строки, состоящие из заглавных латинских букв. Можно считать, что каждый символ — это число по основанию 27. Необходимо использовать основание 27, чтобы представить 26 букв и еще одну цифру для обозначения конца слова. Без отметки конца слова, закодированная строка AA шла бы после строки B, потому что в строке AA две цифры, а в строке B — одна.
Код по основанию 27 для строки из трех символов дает формула 272 * (первая буква - A + 1) + 27 * (вторая буква - A + 1) + 27 * (третья буква - A + 1). Если в строке меньше трех символов, вместо значения (третья буква - A + 1) подставляется 0. Например, строка FOX кодируется так:
272 * (F - A + 1) + 27 * (O - A + 1) + (X - A +1) = 4803
Строка NO кодируется следующим образом:
272 * (N - A + 1) + 27 * (O - A + 1) + (0) = 10.611
Заметим, что 10.611 больше 4803, поскольку NO > FOX.
Таким же образом можно закодировать строки из 6 заглавных букв в виде числа в формате long и строки из 10 букв — как число в формате double. Две следующие процедуры конвертируют строки в числа в формате double и обратно:
Const STRING_BASE = 27
Const ASC_A = 65 ‘ ASCII код для символа "A".
‘ Преобразование строки с число в формате double.
‘
‘ full_len — полная длина, которую должна иметь строка.
‘ Нужна, если строка слишком короткая (например "AX" —
‘ это строка из трех символов).
Function StringToDbl (txt As String, full_len As Integer) As Double
Dim strlen As Integer
Dim i As Integer
Dim value As Double
Dim ch As String * 1
strlen = Len(txt)
If strlen > full_len Then strlen = full_len
value = 0#
For i = 1 To strlen
ch = Mid$(txt, i, 1)
value = value * STRING_BASE + Asc(ch) - ASC_A + 1
Next i
For i = strlen + 1 To full_len
value = value * STRING_BASE
Next i
End Function
‘ Обратное декодирование строки из формата double.
Function DblToString (ByVal value As Double) As String
Dim strlen As Integer
Dim i As Integer
Dim txt As String
Dim Power As Integer
Dim ch As Integer
Dim new_value As Double
txt = ""
Do While value > 0
new_value = Int(value / STRING_BASE)
ch = value - new_value * STRING_BASE
If ch <> 0 Then txt = Chr$(ch + ASC_A - 1) + txt
value = new_value
Loop
DblToString = txt
End Function
===========228
В табл. 9.1 приведено время выполнения программой Encode сортировки 2000 строк различной длины на компьютере с процессором Pentium и тактовой частотой 90 МГц. Заметим, что результаты похожи для каждого типа кодирования. Сортировка 2000 чисел в формате double занимает примерно одинаковое время независимо от того, представляют ли они строки из 3 или 10 символов.
========229
@Таблица 9.1. Время сортировки 2000 строк с использованием различных кодировок в секундах
Можно также кодировать строки, состоящие не только из заглавных букв. Строку из заглавных букв и цифр можно закодировать по основанию 37 вместо 27. Код буквы A будет равен 1, B — 2, … , Z — 26, код 0 будет 27, … , и 9 — 36. Строка AH7 будет кодироваться как 372 * 1 + 37 * 8 + 35 = 1700.
Конечно, при использовании большего основания, длина строки, которую можно закодировать числом типа integer, long или double будет соответственно короче. При основании равном 37, можно закодировать строку из 2 символов в числе формата integer, из 5 символов в числе формата long, и 10 символов в числе формата double.
Примеры программ
Чтобы облегчить сравнение различных алгоритмов сортировки, программа Sort демонстрирует большинство алгоритмов, описанных в этой главе. Сортировка позволяет задать число сортируемых элементов, их максимальное значение, и порядок расположения элементов - прямой, обратный или расположение в случайном порядке. Программа создает список случайно расположенных чисел в формате long и сортирует его, используя выбранный алгоритм. Вначале сортируйте короткие списки, пока не определите, насколько быстро ваш компьютер может выполнять операции сортировки. Это особенно важно для медленных алгоритмов сортировки вставкой, сортировки вставкой с использованием связного списка, сортировки выбором, и пузырьковой сортировки.
Некоторые алгоритмы перемещают большие блоки памяти. Например, алгоритм сортировки вставкой перемещает элементы списка для того, чтобы можно было вставить новый элемент в середину списка. Для перемещения элементов программе, написанной на Visual Basic, приходится использовать цикл For. Следующий код показывает, как сортировка вставкой перемещает элементы с List(j) до List(max_sorted) для того, чтобы освободить место под новый элемент в позиции List(j):
For k = max_sorted To j Step -1
List(k + 1) = List(k)
Next k
List(j) = next_num
==========230
Интерфейс прикладного программирования системы Windows включает две функции, которые позволяют намного быстрее выполнять перемещение блоков памяти. Программы, скомпилированные 16‑битной версией компилятора Visual Basic 4, могут использовать функцию hmemcopy. Программы, скомпилированные 32‑битными компиляторами Visual Basic 4 и 5, могут использовать функцию RtlMoveMemory. Обе функции принимают в качестве параметров конечный и исходный адреса и число байт, которое должно быть скопировано. Следующий код показывает, как объявлять эти функции в модуле .BAS:
#if Win16 Then
Declare Sub MemCopy Lib "Kernel" Alias _
"hmemcpy" (dest As Any, src As Any, _
ByVal numbytes As Long)
#Else
Declare Sub MemCopy Lib "Kernel32" Alias _
"RtlMoveMemory" (dest As Any, src As Any, _
ByVal numbytes As Long)
#EndIf
Следующий фрагмент кода показывает, как сортировка вставкой может использовать эти функции для копирования блоков памяти. Этот код выполняет те же действия, что и цикл For, приведенный выше, но делает это намного быстрее:
If max_sorted >= j Then _
MemCopy List(j + 1), List(j), _
Len(next_num) * (max_sorted - j + 1)
List(j) = next_num
Программа FastSort аналогична программе Sort, но она использует функцию MemCopy для ускорения работы некоторых алгоритмов. В программе FastSort алгоритмы, использующие функцию MemCopy, выделены синим цветом.
Страницы: 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
