Максимальне прискорення алгоритму пошуку

Максимальное прискорення алгоритму пошуку

Дмитрий Сахань Временные витрати алгоритму пошуку відчутно відчуваються при обробці великих обсягів інформації. Якщо виробляється пошук DWORD-числа серед набору (масиву) так само значень, то найоптимальнішим і швидкісним буде послідовне порівняння заданого значення з усіма елементами масиву до виявлення збіги. Проте задля пошуку рядків чи деяких об'єктів, коли дані представлені у вигляді досить великої набору байт, справи інакше. Рядок чи вміст об'єкта — це DWORD-значение, і порівнювати доводиться побайтно все вміст до першого відмінності чи його повної збіги. Саме те й з'їдає основну частину витраченого до пошуку часу.

Но програмісти швидко вирахували, як вдосконалити алгоритм пошуку, що він не витрачав зайве час. Суть в тому, щоб спочатку порівнювати довжини шуканої і аналізованої рядків (для об'єктів — площі їхніх вмісту). Різниця в длинах/размерах точно свідчить різницю вмісту строк/объектов, тому немає сенсу витрачати час на побайтное порівняння їх вмісту. І лише за збігу довжин виконується «повільна «код порівняння вмісту.

Вот що таке простий алгоритм порівняння. Є глобальний масив M з певними рядками, є вхідні строковая змінна P. S з текстом шуканої рядки, і треба знайти ті ж самі рядок в масиві M. Приклад перебільшений і показує, що насправді виконується при порівнянні рядків (адже програміст просто написав б код if p. s = m[i] then замість зазначених мною рядків з if … then).

var.

m: array[1.1000] of AnsiString;

procedure Find (s: AnsiString);

var.

i: Integer;

begin.

for і = 1 to Length (m) do.

if Длина (s) = Длина (m[i]) then.

if Содержимое (s) = Содержимое (m[i]) then.

нашли рядок в m[i];

end;

Однако таке вдосконалення передбачає прискорення лише за різних довжинах розміщених у масиві рядків. Вже за розташуванні в масиві понад 100 тисяч рядків ефективність порівняння «длина-содержимое «починає знижуватися, оскільки масив заповнюється велику кількість однакових по длинам рядків. І що більше розташовувати в масиві рядків, проте ефективним стає дане вдосконалення.

Но найнеприємніше при цьому методу порівняння починається, як у силу якихось обставин чи заздалегідь заданих умов у масиві розташовуються однакові по длинам строки/объекты. Тоді порівняння доводиться вести лише з вмісту, а порівняння довжин виявляється зайвої операцією. При величезних обсягах інформації падіння продуктивності дуже великий. Тут слід або використовувати похідний (від цього) алгоритм пошуку, або написати більш універсальний алгоритм. Програмістам ж добре відомо, що універсальність рідко узгоджується з продуктивністю. І все-таки хочу запропонувати від своєї ідеї, оскільки він добре поєднує універсальність з продуктивністю.

Для початку хочу згадати, що довгі рядки (AnsiString) містяться у пам’яті разом із довжиною рядки. Отримавши адресу рядки, потім вирахувавши з нього 4 байта, ви потрапляєте на адресу довжини рядки. Розповідаю це задля системних програмістів, оскільки програмістів на Delphi, Visual Basic і З++ мало цікавить, як там зберігаються і порівнюються рядки чи масиви. Реалізувавши новий алгоритм на ассемблері, ви отримаєте універсальну і швидку функцію пошуку. Отож, полі довжини рядки завжди поставлено типом 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 і = 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-сравнения.

А тепер погляньмо, наскільки перевершує алгоритм із державним контрольним кодом в «важких «випадках порівняння. Припустимо, ми порівнюємо рядок «Які чудові квіти «зі рядком «Які чудові кольору ». Звичайний алгоритм знайде розбіжність у рядках, коли сягне порівняння останнього символу рядків, тоді як алгоритм із контрольним кодом знайде відмінність вже у результаті порівняння контрольних кодів рядків. Виграш вимірюється відсутністю значної кількості зайвих операцій.

Теряя мінімум у своїх кризових ситуаціях, алгоритм із контрольним кодом дає максимум продуктивності в кризових місцях алгоритма-соперника. Новий алгоритм піднімає продуктивність пошуку значно. Після обробітку надвисоких обсягів інформації такий алгоритм може надати неоціненну послугу, звільняючи з часу пошуку вагому його долю.

Список литературы

Для підготовки даної праці були використані матеріали із російського сайту internet.