Дмитрий Сахань
Временные затраты алгоритма поиска ощутимо чувствуются при обработке больших объемов информации. Если производится поиск 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 тысяч строк эффективность сравнения "длина-содержимое" начинает снижаться, так как массив заполняется большим количеством одинаковых по длинам строк. И чем больше располагать в массиве строк, тем менее эффективным становится данное усовершенствование.
Забиваем Сайты В ТОП КУВАЛДОЙ - Уникальные возможности от SeoHammer
Каждая ссылка анализируется по трем пакетам оценки: SEO, Трафик и SMM.
SeoHammer делает продвижение сайта прозрачным и простым занятием.
Ссылки, вечные ссылки, статьи, упоминания, пресс-релизы - используйте по максимуму потенциал SeoHammer для продвижения вашего сайта.
Что умеет делать SeoHammer
— Продвижение в один клик, интеллектуальный подбор запросов, покупка самых лучших ссылок с высокой степенью качества у лучших бирж ссылок.
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.
SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз,
а первые результаты появляются уже в течение первых 7 дней.
Зарегистрироваться и Начать продвижение
Но самое неприятное для этого метода сравнения начинается, когда в силу каких-то обстоятельств или заранее заданных условий в массиве располагаются одинаковые по длинам строки/объекты. Тогда сравнение приходится вести только по содержимому, а сравнение длин оказывается лишней операцией. При огромных объемах информации падение производительности очень большое. Здесь нужно либо использовать производный (от данного) алгоритм поиска, либо написать более универсальный алгоритм. Программистам хорошо известно, что универсальность редко сочетается с производительностью. И все же хочу предложить свою идею, поскольку она хорошо сочетает универсальность с производительностью.
Для начала хочу упомянуть, что длинные строки (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
Сервис онлайн-записи на собственном Telegram-боте
Попробуйте сервис онлайн-записи VisitTime на основе вашего собственного Telegram-бота:
— Разгрузит мастера, специалиста или компанию;
— Позволит гибко управлять расписанием и загрузкой;
— Разошлет оповещения о новых услугах или акциях;
— Позволит принять оплату на карту/кошелек/счет;
— Позволит записываться на групповые и персональные посещения;
— Поможет получить от клиента отзывы о визите к вам;
— Включает в себя сервис чаевых.
Для новых пользователей первый месяц бесплатно.
Зарегистрироваться в сервисе
if Содержимое(s.Text) = Содержимое(m[i].Text) then
нашли строку в m[i];
end;
На первый взгляд кажется, что дополнительное сравнение прибавит к времени поиска еще лишнее время, но на деле это не так. Контрольный код позволяет с большой долей вероятности определять не равные строки, даже не прибегая к анализу их длин. Смысл в том, что одинаковые строки дадут одинаковый контрольный код. Но за любую универсальность приходится расплачиваться определенными исключениями, когда нововведение вместо пользы приносит лишние затраты. А любое нововведение хорошо только в том случае, если его "закономерные" затраты меньше затрат без него. И здесь новшество с контрольным кодом справляется самым лучшим образом. Дело в том, что контрольный код может быть одинаковым у заведомо разных строк. Объясню это на примере.
Допустим, мы сравниваем строку "вот так" со строкой "так вот". Контрольный код у них будет одинаковый, так как в обеих строках имеются те же самые символы. Алгоритм с контрольным кодом сравнит контрольные коды строк, затем длины строк, затем первый символ строк и найдет различие. Обычный алгоритм сравнит длины строк, а затем первый символ строк и также найдет различие. Выигрыш обычного алгоритма составит одно лишнее DWORD-сравнение алгоритма с контрольным кодом. В кризисных ситуациях (те самые исключения) алгоритм с контрольным кодом несет с собой самые минимальные затраты в виде лишнего DWORD-сравнения.
А теперь посмотрим, насколько превосходит алгоритм с контрольным кодом в "тяжелых" случаях сравнения. Допустим, мы сравниваем строку "Какие восхитительные цветы" со строкой "Какие восхитительные цвета". Обычный алгоритм обнаружит различие в строках, когда дойдет до сравнения последнего символа строк, в то время как алгоритм с контрольным кодом обнаружит различие уже в результате сравнения контрольных кодов строк. Выигрыш измеряется отсутствием значительного количества лишних операций.
Теряя минимум в своих кризисных ситуациях, алгоритм с контрольным кодом дает максимум производительности в кризисных местах алгоритма-соперника. Новый алгоритм поднимает производительность поиска на порядок. При обработке сверхвысоких объемов информации такой алгоритм может оказать неоценимую услугу, высвобождая из времени поиска весомую его долю.
|
