ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrew Novikov                       2:5020/400     28 Jun 2002  23:52:03
 To : All
 Subject : Оценка скорости
 -------------------------------------------------------------------------------- 
 

 Hello, All.
 
 AN>  Hеобходим алгоритм для замены (для начала, поиска) подстроки в
 AN> строке. Строка берется из файла и может быть достаточно большой
 AN> (200К). Образец имеет вид %%имя%%, например,
 AN> %%link%% заменяется на <A href="http://www.mysite.com/myprog.cgi">
 AN> %%email%%          --> <A href="mailto:support@mysite.com">
 AN> %%very_long_link%% --> <H1>Что-то там еще</H1>
 AN>  итд.
 
   Итак, я пришел к тому, что левый терминал ("%%") ищется,
 например, алгоритмом Б-М. Теперь надо определить является
 ли последовательность, следующая сразу за ограничителем
 допустимым тегом. Hа ум приходят два варианта:
   1. побайтовое сравнение символов
   2. использование хеш-функции.
 
   Предположим, есть k тегов в среднем по m символов.
 
   Первым методом необходимо выполнить k*m сравнений.
 
   Второй метод позволит один раз вычислить хеши для образцов
 (тегов). И каждый раз при обнаружении ограничителя тега необ-
 ходимо будет вычислить 1 хеш (на самом деле, k в худшем случае)
 и k раз сравнить его с образцами, при совпадении все-таки
 выполнить в среднем m сравнений символов.
   Единственной известной мне хеш-функцией, пригодной в такой
 задаче является:
 
 h(w[0, M-1]) = (2^(M-1)*w[0] + 2^(M-2)*w[1] + ... + w[M-1]*2^0) mod q
 
 где q - большое простое число. M = max(m).
 Плюсы - легкость вычисления h(w[0, M]) по h(w[0, M-1]). Может,
 существует лучший вариант? Степени двойки находятся быстро при
 помощи сдвигов.
 
   Собственно, проблема. Что быстрее:
 
  k*m раз: (char1 == char2)
 ИЛИ
  Один раз: h(M) затем k (u_int1 == u_int2) и наконец m раз
 (char1 == char2)
 
   Hадеюсь, это не оффтопик...
 
 With best regards, Andy Novikov.  E-mail: programmer@send-e.net
 --- ifmail v.2.15dev5
  * Origin: Demos online service (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Оценка скорости   Andrew Novikov   28 Jun 2002 23:52:03   Оценка скоpости   Alexander Hritonenkov   29 Jun 2002 12:42:30