Comments 8
А если сделать хэш наоборот – нечётное x и p=2ⁿ – неужели коллизий много? А то деление сразу кажется неприятной операцией...
Не совсем понял ваш комментарий, чем именно вас отталкивает деление?
Я далек от мира высшей математики, тервера и криптографии, но постараюсь ответить на ваш вопрос
Х - можно брать абсолютно любой, но q должно быть большим, и желательно очень большим. Потому что если вдруг хеш окажется больше него, чтобы не оказалось так, что он делится на него нацело, в таком случае распределение хега окажется более равномерным. Именно поэтому и упоминалась теория вероятности в разборе алгоритма:)
Знающие люди, если я вдруг не прав, то поправьте меня, пожалуйста.
Обычно процессор выполняет деление на степень двойки быстрее, чем на произвольное число. Поэтому, для максимальной эффективности такие детали должны учитываться.
Ну он же быстрее выполняет именно деление нацело, а с остатком от деления такая оптимизация будет работать?
Просто я так понимаю, что там должно идти целочисленное деление, затем умножение на полученный результат и вычитание из исходного числа. Так что не факт, что деление на степень двойки даст большой прирост по скорости на фоне такого объема операций
Да и вполне вероятно, что этот прирост будет затерт парой тройкой лишних коллизий, хотя не возьмусь утверждать наверняка, хотя опять же
Опять же, мы здесь все-таки рассматриваем именно классический алгоритм, а не модернизируем его:)
Вычисление остатка от деления на степень двойки для процессора вообще элементарная операция, просто обрезать старшие биты числа.
Для остальных чисел приходится выполнять деление по честному (одна операция возвращает сразу частное и остаток)
Для примера, что проще посчитать:
остаток от деления 123456 на 1000
или остаток от деления 123456 на 723?
Звучит резонно, но вопрос того, даст ли это прирост происводительности вкупе с ростом числа коллизий все еще открыт
Я видел интересную штуку, что можно использовать числа Мерсенна (2^n - 1), т.к. для остатка от деления можно тоже использовать шустрые побитовые операции, а еще они простые :)
Но сам я в этот вопрос сильно не забуривался
Ну, вроде вам в первом приближении рассказали :-)
Навскидку выглядит так, будто главное требование – x и q должны быть взаимно простыми. Но применимость на конкретных данных надо проверять. q=2**32 (для 32-битной машины) или 2**64 (для 64-битной) должно работать очень шустро, ведь деления не будет вообще, будет два умножения на константу (поиграв со значением X – возможно, ещё и эти умножения удастся сделать совсем уж дешёвыми, но это уже изыски), одно сложение и одно вычитание.
Что-то типа
// q = количество значений uint64_t
const uint64_t x=565; // могу объяснить выбор числа, но не уверен в том, что оно лучшее
int64_t x_pow = x**(pattern_length-1)
uint64_t hash=0;
char *p_head = buf;
char *p_tail = buf+pattern_length-1;
for(i=... /*по тексту*/) {
//hash = hash*x + buf[i+pattern_length-1] - buf[i]*x_pow
hash = hash*x + *(p_tail++) - *(p_head++)*x_pow;
// тут сравнить hash с образцом
}Обратите внимание – деление вообще ушло. Но надо проверять: вдруг такая оптимизация делает хэш не очень хорошим (можно поэкспериментировать с разными значениями x).
Ну и, конечно, надо обратить внимание на предельное удешевление операции получения символа из массива. Не уверен, что text.charCodeAt(i + pattern.length) толком соптимизируется, а если эта операция будет медленной – то скорость определяется в основном количеством обращений к массиву, и, конечно, тогда алгоритм Бойера-Мура и ему подобные порвут всех.
Но, собственно, алгоритмы с бегущим хэшем, типа данного, интересны не для поиска какой-то одной подстроки, а для поиска одной подстроки из многих. Например, почитайте, как устроен алгоритм rsync.
у себя в проектах использую 64-бит платформу - это сразу 8 байт на значение.
подстрока таким образом представляется из совокупности значений N1*8+N2*4+N3*2+N4*1 байт, где Nx - это число таких вхождений в подстроку, например для слова "обломанн" у нас будет N1=1, то есть сравнение ulong с ulong за одну операцию без вычислений хеша.
вариант с хешем может быть интереснее на длинных подстроках, но тут важно понимать сколько времени тратится на вычисление хеша и что его нужно считать для каждого байтового сдвига. проверка же 8-байтовыми словами за раз происходит весьма быстро.
будет интересно если включите такой метод поиска в ваши материалы и сравните.
PS: пардон если такой способ вы уже обсудили в прошлых статьях, я их не читал пока... но прочитаю.
Строковые алгоритмы на практике. Часть 3 — Алгоритм Рабина — Карпа