Категория
Информатика
Тип
реферат
Страницы
5 стр.
Дата
12.06.2010
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
20510.zip — 6.52 kb
  • maksimalnoe-uskorenie-algoritma-poiska_20510_1.rtf — 28.98 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы

Максимальное ускорение алгоритма поиска
Дмитрий Сахань
Временные затраты алгоритма поиска ощутимо чувствуются при обработке больших объемов информации. Если производится поиск 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])



Ваше мнение



CAPTCHA