Яндекс Лабс в Palo Alto набирает С++ developers

[Мальчик-Одуванчик]

С другой стороны, каким все это боком отностится к знанию плюсов?

У них же Ресеч Лаб. Наверное, плюсы не основной требуемый скилл, главное - чтоб был умный, соображал.

Впрочем, вся история случилось больше трех лет назад, может сейчас у них все по другому...

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

[Boriskin]

Поиск слова естественно с trie решается.

А зачем ограничиваться словом? Произвольная строка и никаких дополнительных танцев...

С другой стороны, каким все это боком отностится к знанию плюсов?

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

[Леонид Ильич Брежнев]

А что никого не смутило, что размер дерева для скажем среднестатистического запроса длиной в скажем 80 символов, будет теоретически размером (если только с буквами, без цифр) в 26 в степени 80? В реалии наверное много меньше, но все равно имхо слишком много?

[dotcom]

А что никого не смутило, что размер дерева для скажем среднестатистического запроса длиной в скажем 80 символов, будет теоретически размером (если только с буквами, без цифр) в 26 в степени 80? В реалии наверное много меньше, но все равно имхо слишком много?

Если вы ко мне, то я как раз предлагал использовать граф, где узлами будут индексированные слова. А trie использовался бы только для поиска слов по словарю. На практике trie действительно будет сильно меньше 26^80. Оценки размеров словарных индексов и их сравнение было где-то даже в дебрях слайдов Сегаловича, когда он был на roadshow с презентацией Яндекса после IPO. Правда, он эти страницы быстро пролистывал перед нетехнической публикой. Для длинных несловарных выражений уже надо использовать b-tree, а не trie.

[crypto5]

А что никого не смутило, что размер дерева для скажем среднестатистического запроса длиной в скажем 80 символов, будет теоретически размером (если только с буквами, без цифр) в 26 в степени 80? В реалии наверное много меньше, но все равно имхо слишком много?

Это случится только когда в индексе будет 26^80 абсолютно разных слов ))

[Леонид Ильич Брежнев]

А что никого не смутило, что размер дерева для скажем среднестатистического запроса длиной в скажем 80 символов, будет теоретически размером (если только с буквами, без цифр) в 26 в степени 80? В реалии наверное много меньше, но все равно имхо слишком много?

Это случится только когда в индексе будет 26^80 абсолютно разных слов ))

http://a.....
http://b.....
http://c.....
....
уже на первом символе (забудем про http://) уже должно быть создано 26 бранчей, от а до z. У второго символа тоже 26, от aa до аz (и так до za ... zz). И так далее. От того что в URL два раза повторится слово mama/mama, не следует, что жизнь с таким URL будет простой, поскольку есть еще mama/papa/mama. And they should be counted differently.
Т.е. по моему мнению дерево будет разрастаться в бесконечность по мере увеличения длины URL. Правда возможно его можно тоже создавать и сохранять кусками, upload/dump на/с FS его по мере надобности.

[crypto5]

А что никого не смутило, что размер дерева для скажем среднестатистического запроса длиной в скажем 80 символов, будет теоретически размером (если только с буквами, без цифр) в 26 в степени 80? В реалии наверное много меньше, но все равно имхо слишком много?

Это случится только когда в индексе будет 26^80 абсолютно разных слов ))

http://a.....
http://b.....
http://c.....
....
уже на первом символе (забудем про http://) уже должно быть создано 26 бранчей, от а до z. У второго символа тоже 26, от aa до аz (и так до za ... zz). И так далее. От того что в URL два раза повторится слово mama/mama, не следует, что жизнь с таким URL будет простой, поскольку есть еще mama/papa/mama. And they should be counted differently.
Т.е. по моему мнению дерево будет разрастаться в бесконечность по мере увеличения длины URL. Правда возможно его можно тоже создавать и сохранять кусками, upload/dump на/с FS его по мере надобности.

Зато строки aaaaaaaaaaaaaaa и aaaaaaaaaaaaaaaaab будут использовать дерево совместно.

[Леонид Ильич Брежнев]

А что никого не смутило, что размер дерева для скажем среднестатистического запроса длиной в скажем 80 символов, будет теоретически размером (если только с буквами, без цифр) в 26 в степени 80? В реалии наверное много меньше, но все равно имхо слишком много?

Если вы ко мне, то я как раз предлагал использовать граф, где узлами будут индексированные слова. А trie использовался бы только для поиска слов по словарю. На практике trie действительно будет сильно меньше 26^80. Оценки размеров словарных индексов и их сравнение было где-то даже в дебрях слайдов Сегаловича, когда он был на roadshow с презентацией Яндекса после IPO. Правда, он эти страницы быстро пролистывал перед нетехнической публикой. Для длинных несловарных выражений уже надо использовать b-tree, а не trie.

Слова дело хорошее и сушественно уменьшит размер датаструктуры, но думается будет так же не мало разношерстных guids, ids, asins, и прочей автоматически сгенерировной фигни, которая ко всему еще была придумана так, что бы минимизировать колизии.

[Леонид Ильич Брежнев]

А что никого не смутило, что размер дерева для скажем среднестатистического запроса длиной в скажем 80 символов, будет теоретически размером (если только с буквами, без цифр) в 26 в степени 80? В реалии наверное много меньше, но все равно имхо слишком много?

Это случится только когда в индексе будет 26^80 абсолютно разных слов ))

http://a.....
http://b.....
http://c.....
....
уже на первом символе (забудем про http://) уже должно быть создано 26 бранчей, от а до z. У второго символа тоже 26, от aa до аz (и так до za ... zz). И так далее. От того что в URL два раза повторится слово mama/mama, не следует, что жизнь с таким URL будет простой, поскольку есть еще mama/papa/mama. And they should be counted differently.
Т.е. по моему мнению дерево будет разрастаться в бесконечность по мере увеличения длины URL. Правда возможно его можно тоже создавать и сохранять кусками, upload/dump на/с FS его по мере надобности.

Зато строки aaaaaaaaaaaaaaa и aaaaaaaaaaaaaaaaab будут использовать дерево совместно.

т.е. аааааааааа и аааааааааааб будет представлено, как
аааааааааа {2} -> аб {1)
отлично.

Но как только у нас попадется слово ааак, вам исходную структуры прийдется делить
ааа{3} -> ааааааа {2} -> аб {1)
....... -> к {1}

И такой работы будет имхо весьма не мало

[crypto5]

А что никого не смутило, что размер дерева для скажем среднестатистического запроса длиной в скажем 80 символов, будет теоретически размером (если только с буквами, без цифр) в 26 в степени 80? В реалии наверное много меньше, но все равно имхо слишком много?

Это случится только когда в индексе будет 26^80 абсолютно разных слов ))

http://a.....
http://b.....
http://c.....
....
уже на первом символе (забудем про http://) уже должно быть создано 26 бранчей, от а до z. У второго символа тоже 26, от aa до аz (и так до za ... zz). И так далее. От того что в URL два раза повторится слово mama/mama, не следует, что жизнь с таким URL будет простой, поскольку есть еще mama/papa/mama. And they should be counted differently.
Т.е. по моему мнению дерево будет разрастаться в бесконечность по мере увеличения длины URL. Правда возможно его можно тоже создавать и сохранять кусками, upload/dump на/с FS его по мере надобности.

Зато строки aaaaaaaaaaaaaaa и aaaaaaaaaaaaaaaaab будут использовать дерево совместно.

т.е. аааааааааа и аааааааааааб будет представлено, как
аааааааааа {2} -> аб {1)
отлично.

Но как только у нас попадется слово ааак, вам исходную структуры прийдется делить
ааа{3} -> ааааааа {2} -> аб {1)
....... -> к {1}

И такой работы будет имхо весьма не мало

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

[Леонид Ильич Брежнев]

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

Это как? Ну вот допустим у нас первая "а", я ее назвал а1
a1 => {a2, b2, ....., z2}
Но ведь на вторую а тоже нужен свой масив
a2 => {a3, b3, ....., z3}
И на вторую "b": b2 => {a32, b32, ....., z32}

[Леонид Ильич Брежнев]

Берлага, А Вам что мое решение совсем не нравится или Вы принципиальный противник Центрального Комитета?

[crypto5]

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

Это как? Ну вот допустим у нас первая "а", я ее назвал а1
a1 => {a2, b2, ....., z2}
Но ведь на вторую а тоже нужен свой масив
a2 => {a3, b3, ....., z3}
И на вторую "b": b2 => {a32, b32, ....., z32}

Если у вас второе слово ab, то для него массив для а уже создавать не нужно, он уже создан для первого слова аа. При этом слов с общим каким то префиксом очень много.

[Интеррапт]

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

Это как? Ну вот допустим у нас первая "а", я ее назвал а1
a1 => {a2, b2, ....., z2}
Но ведь на вторую а тоже нужен свой масив
a2 => {a3, b3, ....., z3}
И на вторую "b": b2 => {a32, b32, ....., z32}

Ну ес-но, если каждый запрос будет уникальный (т.е. народ только и будет делать, что искать всякие GUID). Но ведь в любом поисковике это совсем не так. Небось 99% запросов содержат слова и вполне типичные предложения.

[Леонид Ильич Брежнев]

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

Это как? Ну вот допустим у нас первая "а", я ее назвал а1
a1 => {a2, b2, ....., z2}
Но ведь на вторую а тоже нужен свой масив
a2 => {a3, b3, ....., z3}
И на вторую "b": b2 => {a32, b32, ....., z32}

Ну ес-но, если каждый запрос будет уникальный (т.е. народ только и будет делать, что искать всякие GUID). Но ведь в любом поисковике это совсем не так. Небось 99% запросов содержат слова и вполне типичные предложения.

Если мы обсуждаем стандартный язык, то принципиальной разницы в построении дерева

"privet"{2} -> "interuupt" {1}
.................-> "crypto" {1}

и

"p"{2} -> "r"{2} -> "i"{2} -> "v"{2} -> "e"{2} -> "t"{2} -> Ну и так далее

не будет

Посколько привет и правда расходятся уже на третьей букве, а привет и попа уже на 2-ой

Но граф (пардон) "попа интеррап" и (пардон) "где это попа интеррап" это два совершенно разных дерева, раз уж они расходятся на самой первой букве. Хотя и имеют общие слова

Комбинаций будет конечно не 26 в степени средней длины запроса, очевидно что какие-то последовательности букв слов не образуют ("зтруа"), но будет их много.