Максимальне прискорення алгоритму пошуку
Дмитро Сахань
Тимчасові
витрати алгоритму пошуку відчутно відчуваються при обробці великих обсягів
інформації. Якщо проводиться пошук DWORD-числа серед набору (масиву) таких же
значень, то найбільш оптимальним і швидкісним буде послідовне порівняння
заданого значення з усіма елементами масиву до виявлення збіги.
Однак для пошуку рядків або деяких об'єктів, коли дані представлені в
вигляді досить великого набору байт, справи йдуть інакше. Рядок або вміст
об'єкта - це не DWORD-значення, і порівнювати доводиться побайтно все
вміст до першого розходження або повного збігу. Саме це і з'їдає
основну частину витраченого на пошук часу.
Але
програмісти швидко вирахували, як удосконалити алгоритм пошуку, щоб він
не витрачав зайвий час. Суть полягала в тому, щоб спочатку порівнювати довжини
шуканою і аналізованої строк (для об'єктів - розміри їх вмісту). Різниця
в довжинах/розмірах точно свідчить про різницю вмісту строк/об 'єктів,
тому немає сенсу витрачати час на побайтно порівняння їх вмісту. І
тільки при збігу довжин виконується "повільний" код порівняння
вмісту.
Ось
як виглядає простий алгоритм порівняння. Є глобальний масив M з якимись
рядками, є вхідна строкою мінлива S з текстом шуканої рядка, і потрібно
знайти таку ж рядок у масиві M. Приклад перебільшений і просто показує, що
насправді виконується при порівнянні рядків (адже програміст просто написав
б код if s = m [i] then замість зазначених мною рядків з if .... then).
var
m: array [1 .. 1000] of AnsiString;
procedure Find (s: AnsiString);
var
i: Integer;
begin
for i = 1 to Length (m) do
if Довжина (s) = Довжина (m [i]) then
if
Вміст (s) = Вміст (m [i]) then
знайшли
рядок у m [i];
end;
Однак
таке вдосконалення має на увазі прискорення тільки при різних довжинах
розташованих у масиві рядків. Вже при розташуванні в масиві понад 100 тисяч
строк ефективність порівняння "довжина-вміст" починає знижуватися,
так як масив заповнюється великою кількістю однакових по довжинах рядків. І
чим більше мати у своєму розпорядженні в масиві рядків, тим менш ефективним стає дане
удосконалення.
Але
найнеприємніше для цього методу порівняння починається, коли в силу якихось
обставин або заздалегідь заданих умов в масиві розташовані однакові
по довжині рядка/об'єкти. Тоді порівняння доводиться вести тільки за
вмісту, а порівняння довжин виявляється зайвою операцією. При величезних
обсягах інформації падіння продуктивності дуже велике. Тут потрібно або
використовувати похідний (від даного) алгоритм пошуку, або написати більш
універсальний алгоритм. Програмістам добре відомо, що універсальність
рідко поєднується з ресурсами. І все ж хочу запропонувати свою ідею,
оскільки вона добре поєднує універсальність з ресурсами.
Для
Спершу хочу згадати, що довгі рядки (AnsiString) розташовуються в пам'яті
разом з довжиною рядка. Отримавши адреса рядка, потім відібравши від нього 4 байти, ви
потрапляєте на адресу довжини рядка. Розповідаю це для системних програмістів,
так як програмістів на Delphi, Visual Basic та C + + мало цікавить, як там
зберігаються і порівнюються рядка або масиви. Реалізувавши новий алгоритм на
асемблері, ви отримаєте універсальну і швидку функцію пошуку. Так ось, поле
довжини рядка завжди задано типом DWord (4 байти). У загальному випадку той же
відноситься і до байтовий масивів. Погано, що в стандарт
"довжина-вміст" складно впровадити ще одне DWORD-поле, тому
доведеться робити якось інакше.
Суть
моєї пропозиції полягає в тому, щоб розташувати перед довжиною рядки ще одне
DWORD-поле. Для зручності назвемо його "Контрольний код вмісту".
Установка вмісту будь-який рядок включає в себе: обчислення контрольного
коду, встановлення довжини рядка та її вмісту. Обчислення контрольного коду
виконується як побайтно складання всіх байт вмісту рядка в DWORD-суму.
Новий
алгоритм пошуку включає в себе додаткове порівняння - спочатку порівнюються
контрольні коди вмісту двох рядків, при їх збігу порівнюються довжини
рядків, і при збігу довжин порівнюється рядки. Формально алгоритм
пошуку приймає такий вигляд (для наочності я вивів тип TNewString, щоб ви
бачили, що робота ведеться зі зміненим типом рядка).
type TNewString = packed record
CRC: DWord;
Text: AnsiString;
end;
var
m: array [1 .. 1000] of TNewString;
procedure Find (s: TNewString);
var
i: Integer;
begin
for i = 1 to Length (m) do
if s.CRC = m [i]. CRC then
if Довжина (s.Text) = Довжина (m [i]. Text) then
if Вміст (s.Text) = Вміст (m [i]. Text) then
знайшли
рядок у m [i];
end;
На
перший погляд здається, що додаткове порівняння додасть до часу пошуку
ще зайвий час, але на ділі це не так. Контрольний код дозволяє з великою
часткою ймовірності визначати не рівні рядки, навіть не вдаючись до аналізу їх
довжин. Сенс у тому, що однакові рядки дадуть однаковий контрольний код. Але
за будь-яку універсальність доводиться розплачуватися певними винятками,
коли нововведення замість користі приносить зайві витрати. А будь-яке нововведення
добре тільки в тому випадку, якщо його "закономірні" витрати менше
витрат без нього. І тут нововведення з контрольним кодом справляється найкращим
чином. Справа в тому, що контрольний код може бути однаковим у завідомо
різних рядків. Поясню це на прикладі.
Припустимо,
ми порівнюємо рядок "ось так" з рядком "отож".
Контрольний код у них буде однаковий, оскільки в обох рядках є ті ж
самі символи. Алгоритм з контрольним кодом порівняє контрольні коди рядків,
потім довжини рядків, потім перший символ рядків і знайде відмінність. Звичайний
алгоритм порівняє довжини рядків, а потім перший символ рядків і також знайде
відмінність. Виграш звичайного алгоритму складе одне зайве DWORD-порівняння
алгоритму з контрольним кодом. У кризових ситуаціях (ті самі винятки)
алгоритм з контрольним кодом несе з собою самі мінімальні витрати у вигляді
зайвого DWORD-порівняння.
А
тепер подивимося, наскільки перевершує алгоритм з контрольним кодом в
"важких" випадках порівняння. Припустимо, ми порівнюємо рядок
"Які чудові квіти" з рядком "Які чудові
кольору ". Звичайний алгоритм виявить розходження в рядках, коли дійде до
порівняння останнього символу строк, у той час як алгоритм з контрольним кодом
виявить розходження вже в результаті порівняння контрольних кодів рядків. Виграш
вимірюється відсутністю значної кількості зайвих операцій.
Втрачаючи
мінімум у своїх кризових ситуаціях, алгоритм з контрольним кодом дає максимум
продуктивності в кризових місцях алгоритму-суперника. Новий алгоритм
піднімає продуктивність пошуку на порядок. При обробці надвисоких
обсягів інформації такий алгоритм може надати неоціненну послугу, вивільняючи
з часу пошуку вагому його частку.
Список літератури
Для
підготовки даної роботи були використані матеріали з сайту http://www.sciteclibrary.ru
