crazy people

[109]

ну ни фига ж себе так, ни с того ни с сего. чуваку, открывшему для себя деревья объяснил, что такое big-O notation и порекомендовал два более эффективных алгоритма. полчаса писал, наверное; даже в гуголь сходил освежить воспоминания о скиплистах. а в ответ получил:

...я не люблю хамов.
...я не люблю самодовольных людей, которые всерьез считают себя умней всех.
А посему, всего доброго.

ну и коммент мой он стёр, конечно. а производил впечатление совершенно нормального человека. не знаю, что и думать. неужели от кого угодно можно чего угодно ожидать?

Comments

[sply.livejournal.com]

с suffix trie я что-то стромозил, тут же наоборот, ищем voda в vodafone, поэтому все-таки просто prefix trie. Сложность близка к O(N^2) будет только в худшем случае, когда паттерны плотно займут первые уровни trie (aaa, aba, aca, baa, bba ...) и плохая строка поиска типа vodvodvodafone.

Но в реальности будет что-то около O(N*F), где F сложная и путаная, но малорастущая функция - сумма произведений вероятности нахождения подстроки из входной строки в trie. По человечески ее долго расписывать. Т.е. если у нас в trie находятся voda, eric, и искомая строка www.vodafone.com, мы в trie на непопадающих символаx дальше первого уровня заглядывать и не будем.


А с хэшами так - для набора паттернов для всех подстрок каждого паттерна длиной L (вероятно, длина самого короткого паттерна) строится хэш-таблица из этих подстрок. Операция разовая и ее сложность не считаем. Далее для строки, в которой ищем эти паттерны для всех подстрок считаем хэш и ищем его попадание в хэш-таблице. Если попали, проверяем остальную часть паттерна, для которого попался хэш. Если длина всех паттернов одинакова, то O(N), если нет, то O(N*z), где z ~= средняя_длина_паттернов/минимальная_длина_паттерна, что по сути константа.

а соскиплистом все-равно не понятно

[109.livejournal.com]

я, к сожалению, не понял ваш алгоритм с хэштаблицами. можно поподробнее?

нужно, видимо, договориться о терминах. предлагаю называть строку, в которой ищутся подстроки, словом "строка" (string), искомые в ней подстроки - словом "подстроки" (substrings), а слово "паттерн" не использовать.

[sply.livejournal.com]

voda, eric, samsun

в хэш-таблицу идут хэши от voda,eric,sams(указывает на samsun)

ищем в www.vodafone.com
проверяем подстроки www., ww.v, ..., .vod, voda ... т.е. берем от них хэш и смотрим в таблице

а если искали в supersamsung, то дойдя до sams нужно будет сравнить еще и хвост" - un, отсюда появляется z

[109.livejournal.com]

во-от... количество подстрок зависит от длины строки как O(N^2) плюс средняя длина подстроки зависит от длины строки линейно, а скорость вычисления хэша зависит от длины строки, для которой вычисляется хэш, тоже линейно, так что если делать "втупую", то суммарно получится O(N^3). к счастью, для строк w, ww, www и так далее хэш можно вычислять инкрементально, что одну размерность снимает и остаётся опять O(N^2), что я и написал.

[sply.livejournal.com]

Подстроки брать не произвольной длины, а фиксированной - той, с которой занесены подстроки в хэш, т.е. длиной самой короткой из подстрок. В приведенном мной примере, длина всех подстрок-кандидатов будет 4 и число таких подстрок = N-4. Брать от них хэш - константа.

[109.livejournal.com]

я же предлагал определиться с терминами. а то у вас и то подстроки, и то подстроки.

и я опять не понимаю. есть массив подстрок для сравнения, все они разной длины. как это мы будем заносить в _хэштаблицу_ (а не в хэш, хэш - это результат вычисления хэш-функции) строки фиксированной длины, если длина у всех разная?

[sply.livejournal.com]

Тогда все-таки введем понятие паттерны P, чтобы не путаться. Пусть P1 = "voda", P2 = "eric", P3 = "samsun". Ту строку, в которой ищем любой из паттернов - T. Пусть T1 = "www.vodafone.com", T2 = "supersamsung".

Строим хэш-таблицу по паттернам:
находим наименьшую рабочую длину - длину самого короткого паттерна, L. Для наших P1..P3 получим L=4. Для всех паттернов берем их префикс длины L, получаем хэш, кладем в хэш-таблицу HT для полученного хэша весь паттерн.
Получаем что-то вида HT[Hash(Substring(P1, 0, L))] = P1 и т.п.

теперь получаем строки, в которых ищем паттерны. Получили T1. Берем из нее все подстроки S длиной L - S1 = "www.", S2 = "ww.v", .. S5 = "voda" ...

Берем от Si хэш, смотрим в HT, если есть попадание, то сравниваем Si с попавшим паттерном. Если длина паттерна равна L, значит совпадение считаем полным. Если больше L, то сравниваем оставшуюся часть паттерна (пусть k-символов) с оставшимися k-символами, следующими за Si и если тоже совпало, значит нашли полное совпадение.






появляются паттерны P - например, "voda", "eric", "samsun"

в хэш-таблицу идут хэши от voda,eric,sams(указывает на samsun)

[109.livejournal.com]

теперь понятно. что делать, если один из паттернов имеет длину 1 или 2? алгоритм тогда сильно вырождается и тормозит.

[sply.livejournal.com]

в таков виде вырождается.
но можно добавить хитрожопости, чтобы держал отдельно хэш для длинных кусков, и отдельно trie для вырожденных коротких паттернов (1-2 символа)

[109.livejournal.com]

ну по-хорошему тогда надо для каждой длины свою коллекцию держать, что приносит обратно мой аргумент про O(N^2), против которого, собственно, и была направлена эта фиксированная длина.

[sply.livejournal.com]

это не по-хорошему, это худший случай :)
если чисто на хэшах, то для подавляющего большинства случаев хватит двух таблиц, что будет O(N*2), но не O(N^2).

[109.livejournal.com]

да ну нет же. оба предельных случая с обоих сторон работают как O(N^2). а вы почему-то продолжаете утвеждать, что "в середине" оно работает, как O(N), не предоставляя доказательств.

[sply.livejournal.com]

второй предельный случай - это какой? первый - понятно, короткие паттерны. Но он не O(N^2), а O(N)

вообще, так и не понятно, откуда вы берете O(N^2). Видимо, все то же множество всех подсток T, длиной от 0 до N. Но оно здесь совершенно не нужно. Если даже и выбрать бессмысленный вариант с отдельными хэш-таблицами для каждой длины паттетна, то число таких таблиц равно кол-ву различных длин паттаров (для паттернов 'a', 'ab', 'cdef' - 3 таблицы) и число подстрок из T, которые мы будем искать в хэш-таблицах, начинающихся с позиции i (для всех 0<i<N)) будет не N, а 3. Поэтому квадрата нет, есть только O(N*3). И если длина Т составит 100, то мы проверим не 10000 подстрок, а 300. Если вы настаиваете на квадрате, объясните, пожалуйста, сами, откуда он может взяться.

[sply.livejournal.com]

нда, знак меньше не понравился, ладно


для всех i от 0 до N, для проверки в хэш-таблицах требуется только 3 подстроки - длиной 1, 2 и 4. И от N число подстрок и их длины не меняются. Т.е. O(N*(1+2+4))

Если все-таки где-то есть квадрат, укажите, пожалуйста, его в явном виде.