загрузка...

трусы женские
загрузка...
Реферати » Реферати з інформатики та програмування » Максимальне прискорення алгоритму пошуку

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

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

Дмитро Сахань

Тимчасові витрати алгоритму пошуку відчутно відчуваються при обробці великих обсягів інформації. Якщо проводиться пошук 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-порівняння.

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

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

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

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

 
Подібні реферати:
Пошук підрядка в рядку за допомогою хеш-функції
Пошук підрядка в рядку - часто виникає на практиці завдання. Пошук підрядка в рядку звичайної підстановкою до кожної позиції рядка всій підрядка - метод неефективний і взагалі сумний.
10 завдань з рішеннями програмуванням на Паскалі
procedure arf (m, n: integer; var x: m); var i, j, s: integer; sr: real; begin for i: = 1 to m do begin s: = 0; sr: = 0; if x [i, n] = 1 then begin for j: = 1 to n do s: = s + x [i, j]; sr: = s / n; writeln ('середнє арифметичне', i, 'з
Лабораторна робота № 16
procedure Trim (Var s: string); begin {Trim} while (s [ 1] = '') and (length (s)> 0) do delete (s, 1,1); while (s [length (s)] = '') and (length (s)> 0) do delete ( s, length (s), 1); end; {Trim} procedure sravn (sl: string; Var k1: i
Строковий тип даних у мові Pascal
Рядок - це послідовність символів. Кожен символ займає 1 байт пам'яті (код ASCII). Кількість символів в рядку називається її завдовжки. Довжина рядка може перебувати в діапазоні від 0 до 255.
Строковий тип даних у мові Pascal
Ознайомимося з типом даних, який відноситься до числа структурованих. Це рядковий тип даних (рядок). Рядок - це послідовність символів. Кожен символ займає 1 байт пам'яті (код ASCII).
Алгоритми пошуку в тексті
Алгоритм грубої сили і простий варіант алгоритму Бойєр-Мура .. Більш ефективний варіант.
Операції багаторазової точності (операції з довгими числами)
Де S - константа або обчислюване значення. Якщо це - константа, то С - число в строковому вигляді, перед яким стоїть символ «@» , а якщо S треба знайти те S = V, де V - вираз зі змінними і числами. У рядку
Масиви в мовах Pascal і Basic
Масив в Бейсике. Масив в Паскалі. Дії над масивами.
Послідовні таблиці
невідсортовану таблиці.
Трансляція коду Delphi в код C + + Builder
Типи даних. Ключові слова. Операторні ознаки кінця. Оголошення змінних. Рядки. Прирівнювання і порівняння змінних. Оголошення констант. Функції та процедурие Конструкція with ... do.
Алгоритм Кнута - Морріса - Пратта
Рішення типових завдань.
Алгоритм Кнута - Морріса - Пратта
Рішення типових завдань.
Шпаргалки по Fortrany
Автоматичні масиви У процедурі може бути заданий локальний масив, розміри якого можуть змінюватися при різних викликах процедури. Такі масиви, так само як і локальні рядки змінної довжини (розд. 1
Послідовні таблиці
невідсортовану таблиці.
Обробка рядків у РНР
Однією з найбільш часто зустрічаються завдань у програмуванні є обробка символьних послідовностей. Якщо простіше - рядків. Як це робиться на мові гіпертекстового препроцесора РНР і є тема цієї статті.
Лабораторні роботи з системного ПО
Мета роботи. Пояснити особливості технічних засобів мікрокомп'ютера та організації програмного забезпечення. Вивчити машинний мова, введення команд в пам'ять і виконання програм. Показати основні вимоги до
Програмування елементів розгалужується структури
uses crt; var i: integer; a: array [1 .. 20] of integer; c: array [1 .. 20] of integer; begin clrscr ; writeln ('Перший масив:'); for i: = 1 to 20 do begin a [i]: = random (30); write ('', a [i]); end; writeln
Масиви в мовах Pascal і Basic
Масив в Бейсике. Масив в Паскалі. Дії над масивами.
Документація на основі RTF-шаблону
Розробка прикладного ПЗ - це не лише написання коду програм, а й проектування друкованих документів і звітів. Практично всі інтегровані середовища мають у своєму складі генератори звітів, в тій чи іншій мірі допомагають вирішити цю задачу.
Маніпулювання з цілими числами довільної довжини
Складання процедур маніпулювання, що забезпечують формування і введення цілих чисел довільної довжини, додавання, віднімання, порівняння і множення цілих чисел.
загрузка...
ur.co.ua

енциклопедія  з сиру  аджапсандалі  ананаси  узвар