Latched, pinned, and marked dirty

а какие? хотя бы просто название

From:

hashtable, skip list.

From:

хмм, то что он предложил - по ссылке - это не btree, а trie. если вместо trie использовать suffux trie, поиск получим O(N), где N - длина строки в которой _ищем_, т.е. в его случае, строка vodafone.com, а не число искомых паттернов. Хэш в этом случае тоже O(N), т.к. O(1) применительно к числу элементов хэша, а не размеру искомой строки. А предположив хэш с коллизиями, где нужно будет для одного хэша делать несколько сравнений с "коллизиантами", O(N) превращается в O(N*какую_то_константу).

а про скиплист я так и не понял, зачем его здесь применить :(

From:

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

скиплист тут при том, что с ним получится O(N log N), что, очевидно, лучше, чем O(N^2).

рассуждения про коллизии правильны, но не особенно релевантны, поскольку, во-первых, O(N*const) = O(N), а во-вторых, процент коллизий можно сделать сколь угодно малым, изменяя load factor.

From:

с 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 ~= средняя_длина_паттернов/минимальная_длина_паттерна, что по сути константа.

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

From:

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

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

From:

voda, eric, samsun

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

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

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

From:

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

From:

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

From:

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

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

From:

Тогда все-таки введем понятие паттерны 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)

From:

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

From:

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

From:

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

From:

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

From:

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

From:

второй предельный случай - это какой? первый - понятно, короткие паттерны. Но он не 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. Если вы настаиваете на квадрате, объясните, пожалуйста, сами, откуда он может взяться.

From:

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

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

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

From:

piggymouse.livejournal.com

Может ты ему написал это самое, по форме всё круто, а по существу издевательство?

From:

не, по существу точно всё правильно было. собственно, вот что я написал:

-----
ахуеть дайте две.

во-первых, ты сначала определись, О(от чего) ты считаешь - от длины строки или от количества подстрок.

во-вторых, О(К*М) = О(1) - этак любой алгоритм будет О(1).

в-третьих, нужно просто пройти по всем буквам этой строки уже даёт О(N^2) от длины строки.

в-четвёртых, поздравляю с открытием B-tree.

в-пятых, B-tree - это balanced tree, а не binary. у тебя оно хоть и не balanced, но таки и не binary, так что сурово звучащее словосочетание "бинарное дерево" употреблено совсем зря.

и наконец, я щас ваще will blow your mind. есть ещё более эффективные структуры, чем B-tree - например, hashtable, в которых поиск на самом деле O(1) (а не зависит от длин подстрок, как у тебя), и в то же время они не занимают много лишней памяти, как решение с массивами.

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

самое же эффективное решение O(N log N), очевидно, даcт скиплист (google://"skip list"), но придётся повозиться при написании.

From:

vasja-pupkind.livejournal.com

Во-первых, Вы обращаетесь к незнакомому собеседнику на ты, а не на Вы. Это уже как-то нехорошо. Я слышал, что в "Фидо" так было принято, но не все ж об этом знают.

Во-вторых, прописные истины и тривиальные факты (О-нотация, B-tree и его отличие от бинарного, hash-таблицы) тоже излагать не надо. Эти факты знакомы любому первокурснику любого ун-та, прослушавшему курс "Введение в Алгоритмы". А catpad все-таки выпускник Техниона.

А в-третьих, все эти Ваши советы не кажутся мне релевантными.

В итоге создается впечатления надувания щек, Вы уж простите.

From:

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

к ты-вы у катпада претензий не было. у вас есть претензии? я вроде бы вас и не называл на ты, хотя ваш ник прямо-таки взывает к такому обращению.

From:

vasja-pupkind.livejournal.com

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

Да нет, я думаю, знакомы. На всякий случай скажу, что catpad'а лично не знаю, но из постингов сложилось такое впечатление. Да и school опять же.

к ты-вы у катпада претензий не было.

Возможно, но неожиданное тыкание в сочетании с прочим (матерные выражения, обещание поразить разум хэшем" и пр.) может восприниматься как хамство.

Впрочем, дело даже и не в хэше. Просто Ваш постинг отдает неспровоцированной агрессией. Ну я даже не знаю как об'яснить ... Вроде мелочи, а чувствуется. Уитывая соотношение полезности постинга и его тона, мне например очень понятно нежелание продолжать разговор.

Я не хочу Вас обидеть, но, по-моему, так просто не принято. Вы почитайте комменты и "катпада" в журнале. Разве не видна разница в тоне ?

у вас есть претензии? я вроде бы вас и не называл на ты, хотя ваш ник прямо-таки взывает к такому обращению.

Надо же ! Ну ладно. Я необидчив.

From:

pishu

мир полон чудаками и мудаками. Вероятность встречи представителя любой категории - одна вторая.

From:

Твоя манера объяснения действительно зачастую далека от корректной и незаносчивой. Я это сам видел не раз что здесь, что в z1, что в фидо. Т.е. это или такой неудачный стиль изложения, или твое завышенное самомнение, или оба вместе.

В данном конкретном инциденте рекомендую подумать над следующими ключевыми словами: "поздравляю", "blow your mind" и "ахуеть дайте две".

From:

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

с зиваном ты просто попал пальцем в небо. там [по крайней мере, было] достаточно много достойных людей, на которых я отнюдь не смотрел сверху вниз. кроме того, именно там как раз люди отлично распознают bullshit, так что можно не беспокоиться о политической корректности (отсутствие которой ты, возможно, принимаешь за заносчивость).

насчёт фидо (не-зиван) поясни.

ахуеть дайте две - устойчивое идиоматическое выражение, выражающее исключительно удивление. никаких негативных коннотаций не несёт. подумал над "blow your mind". i don't think it's offensive. is it? would you be offended?

P.S. по крайней мере я комментирую в чужом дневнике "задрали уже писать о [нужное подставить]" :-P

From:

msh.livejournal.com

Вспоминается анекдот "может хоть ты поможешь мне, мерзкий старикашка"

From:

?

From:

Мужик приходит к психологу:
- Доктор, меня никто не любит, нет друзей, со мной не хотят общаться. Может, хоть ты мне поможешь, мерзкий, вонючий старикашка?

From:

Вкратце, я имел в виду, что информативность твоих высказываний зачастую сводится на нет формой подачи информации. Утрированный пример: доказательство теоремы Ферма (уникальный по информативности контент) на языке "падонкафф" (уродливое и неприятное по форме изложение) вряд ли будет принято широкой общественностью. Жертвы могут найтись ради уникальности контента, но по мере снижения его ценности, форма изложения становится все более важной.

From:

это почему же на языке падонкафф - неприятное? у нас, видимо, слишком мало общего, чтобы "информативно" общаться.

From:

это почему же на языке падонкафф - неприятное?

"На вкус и цвет - товарища нет".

у нас, видимо, слишком мало общего, чтобы "информативно" общаться.

Вполне возможно. Это нормально.

From: