СТАТЬИ И ПУБЛИКАЦИИ

Вход или Регистрация

ПОМОЩЬ В ПАТЕНТОВАНИИ НАУЧНО-ТЕХНИЧЕСКИЙ ФОРУМ Научно-техническая библиотекаНаучно-техническая библиотека SciTecLibrary
 
Cтатьи и Публикации    Программное обеспечение МАКСИМАЛЬНОЕ УСКОРЕНИЕ АЛГОРИТМА ПОИСКА

МАКСИМАЛЬНОЕ УСКОРЕНИЕ АЛГОРИТМА ПОИСКА

© Дмитрий Сахань

Контакт с автором: karina@st.lg.ukrtel.net

www.aimatrix.nm.ru

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

А теперь посмотрим, насколько превосходит алгоритм с контрольным кодом в "тяжелых" случаях сравнения. Допустим, мы сравниваем строку "Какие восхитительные цветы" со строкой "Какие восхитительные цвета". Обычный алгоритм обнаружит различие в строках, когда дойдет до сравнения последнего символа строк, в то время как алгоритм с контрольным кодом обнаружит различие уже в результате сравнения контрольных кодов строк. Выигрыш измеряется отсутствием значительного количества лишних операций.

Теряя минимум в своих кризисных ситуациях, алгоритм с контрольным кодом дает максимум производительности в кризисных местах алгоритма-соперника. Новый алгоритм поднимает производительность поиска на порядок. При обработке сверхвысоких объемов информации такой алгоритм может оказать неоценимую услугу, высвобождая из времени поиска весомую его долю. Дата публикации: 10 ноября 2003
Источник: SciTecLibrary.ru


Вы можете оставить свой комментарий по этой статье или прочитать мнения других в следующих разделах ФОРУМА:
Свернуть Защита интеллектуальной собственности и авторских прав
Диспуты по темам изобретательства. Вопросы по изобретениям, проблемы на пути изобретателей и методы их решения.
Патентование. Все о патентовании изобретений, полезных моделей, промышленных образцов и товарных знаков.
Нерешенные задачи. Здесь идет обсуждение нерешенных задач: безопорный двигатель, вечный двигатель, преодоление гравитации и пр.
Свернуть Точные науки и дисциплины
Дебаты по Теории Относительности Эйнштейна. Все кому не лень хотят опровергнуть Теорию Относительности Эйнштейна. Вам предоставляется слово для аргументации.
Физика, астрономия, математические решения. Физико-математические вопросы, наблюдения, исследования, теории и их решение.
Физика альтернативная. Новые взгляды на физические законы, теории, эксперименты, не вписывающиеся в общепринятые законы физики.
Teхника, узлы, механизмы, электроника и аппаратура. Все про технику, приборы, детали, узлы и механизмы. Электроника, компьютеры, программное обеспечение. Новые технические решения в самых разных областях.
Биология, Генетика, Все о жизни. Генетика и другие вопросы биологии. Их развитие. Медицина. Биотехнологии, агротехника и сельское хозяйство. Эволюционные теории и альтернативные им.
Химия. Вопросы по химическим технологиям, разработкам и применению химических материалов. Химические элементы и их свойства.
Геология, все о Земле и ее обитателях. Геология, метеорология, антропология, сейсмология, атмосферные явления и непознанные эффекты природы.
Свернуть Мозговой штурм
Генератор решений. Здесь Вы можете заработать реальные деньги, помогая решать фирмам, предприятиям и частным лицам те или иные технические задачи, которые перед ними стоят. Те, кто ставят задачи перед участниками должны обозначить гонорар за ее решение и перевести указанную сумму на общий счет генератора.
Головоломки. Если у Вас есть желание поломать голову над интересными логическими задачами - Вам сюда.
Гипотезы. В этой теме идет обсуждение гипотез и предположений, основанных чисто на теории и логике.
Найди ляп! Этот раздел для тех, кто хочет мысленно расслабиться. Он посвящен задачам по поискам ляпов, которые встречаются в литературе, интернете, кино и на телевидении.
Свернуть Взгляд в будущее и настоящее
Глобальные темы. Вопросы касающиеся всех. Глобальные угрозы и злободневные темы современности.
Наука и ее развитие. Все о развитии науки, направлениях и перспективах движения научной мысли и знаний.
Новая Цивилизация. Принципы социального устройства новой цивилизации. Увеличение роли созидательного интеллекта... Отдалённые перспективы развития человечества...
Вопросы без ответов. Этот раздел посвящен вопросам и проблемам, которые до сих пор не решены. Предлагайте свои решения.
Военная стратегия и тактика современных боевых действий. Об особенностях современного военного искусства. Проблемные вопросы теории и практики подготовки вооруженных сил к войне, её планирование и ведение в различных конфликтах на планете.
Свернуть Гуманитарные науки и дисциплины
Философские дискуссии. Диспуты по вопросам жизни, сознания, бытия и иных философских понятий.
Экономика. Вопросы по экономике и о путях развития России и других стран.
Социология, Политология, Психология. В этом разделе обсуждаются вопросы, как отдельных частных исследований данных наук, так и проблема соотношения этих наук с остальными.
Образование. Все об образовании: как учить, кому учить, чему учить и кого учить.
Религия и атеизм. Вопросы религий и атеистические взгляды, религиозные споры.

Хотите разместить свою статью или публикацию, чтобы ее читали все?
Как это сделать - узнайте здесь.

Назад

 
О проекте Контакты Архив старого сайта

Copyright © SciTecLibrary © 2000-2017

Агентство научно-технической информации Научно-техническая библиотека SciTecLibrary. Свид. ФС77-20137 от 23.11.2004.