Оценка скорости

From

Andrew Novikov ()

To

All

Date

2002-06-28T23:52:03Z

Area

RU.ALGORITHMS

From: "Andrew Novikov" <programmer@send-e.net>

Hello, All.

AN>  Необходим алгоритм для замены (для начала, поиска) подстроки в
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>  итд.

  Итак, я пришел к тому, что левый терминал ("%%") ищется,
например, алгоритмом Б-М. Теперь надо определить является
ли последовательность, следующая сразу за ограничителем
допустимым тегом. На ум приходят два варианта:
  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)

  Надеюсь, это не оффтопик...

With best regards, Andy Novikov.  E-mail: programmer@send-e.net


--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)