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

[crypto5]

Конечно менее встечаемые поиски не будут кодироваться так эффективно но экономия все равно будет.

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

ХОтя даже если миллиард уникальных запросов то нам понадобится дерево из нод количеством равным количеству сумме количества символов в миллиарде запросов. Ну грубо 10 миллиардов. По 5 байтов на нод. 50 гигабайт. У меня на работе поместится - как раз 64 гб памяти.

У вас только указатель на нод на 64битной архитектуре 8 байт будет занимать, какие 5 байтов?

Хорошо, 256 Гб.

Можете набросать формат вашего нода в виде C структуры, которая займет 25 байт?

Тоже не так страшно. А как вы собрались это сортировать, считать count и брать топ от них на одном компьютере ? МР тоже займет неплохо времени для этого.

Я как то недавно 100ГБбайтные файлы на своем лаптопе сортировал, часа 2-3 на файл уходит. Это на старом лаптопе с 8ГБ РАМ, он сортирует блоки по 8БГ а потом их сливает. Если компьютер будет с 256ГБ, то наверное даже быстрее будет.
При этом у линукса сейчас sort многопоточный, а вам еще нужно будет попотеть что бы хорошо масштабируемое concurrent trie заимплементить.

[Интеррапт]

Зачем все эти сложности? Чем lossy counting алгоритм плох, чтобы найти эти самые top 10? На миллиардах записях даст отличную точность.

[crypto5]

Зачем все эти сложности? Чем lossy counting алгоритм плох, чтобы найти эти самые top 10? На миллиардах записях даст отличную точность.

Ну это уже две разные задачи, отличная точность и 100% точный результат.

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

Вы сама беспомощность ))
Вот тут 20 миллионов запросов, можете к каждому запросу пределать стоо раз случайный префикс и суфикс и получится 2 млрд запросов, и с ними играйтесь http://www.gregsadetsky.com/aol-data/

О, спасибо огромное. Это то что надо для эксперимента.

Оттудова не качает, если скачает то скажите как у вас это получилось и\или залейте на торрент дорогой Леонид Ильич.

Я хотел в университете скачать, так что не проверил сразу. Но да, не качается.
По второму линку все много лучше. Hачалось. 27 минут ETA.

[crypto5]

На самом деле мне кажется если разбить датасет скажем на 1000 частей, и в каждом точно посчитать топ 10к запросов, а потом слить результаты, то 10 запросов посчитаются с 100% точностью.

[Интеррапт]

Зачем все эти сложности? Чем lossy counting алгоритм плох, чтобы найти эти самые top 10? На миллиардах записях даст отличную точность.

Ну это уже две разные задачи, отличная точность и 100% точный результат.

А где там было в задаче про "отличную точность"? Может я чего-то пропустил? Berlaga вон сказал, что там вообще про sampling ответ ожидался. А lossy counting по точности sampling порвет как тузик грелку и на большом кол-ве записей (ес-но если не предполагать, что все записи встречаются с приблизительно одинаковой частотой) - выдаст именно те самые искомые top 10 скорее всего с точностью близкой к тем самым 100%. А что еще нужно для поисковых терминов?

[Интеррапт]

На самом деле мне кажется если разбить датасет скажем на 1000 частей, и в каждом точно посчитать топ 10к запросов, а потом слить результаты, то 10 запросов посчитаются с 100% точностью.

Обоснование есть по поводу "100% точности"?

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

На самом деле мне кажется если разбить датасет скажем на 1000 частей, и в каждом точно посчитать топ 10к запросов, а потом слить результаты, то 10 запросов посчитаются с 100% точностью.

Это была моя идея 5 страниц назад.

[crypto5]

На самом деле мне кажется если разбить датасет скажем на 1000 частей, и в каждом точно посчитать топ 10к запросов, а потом слить результаты, то 10 запросов посчитаются с 100% точностью.

Обоснование есть по поводу "100% точности"?

Лень сейчас думать, но думаю можно такие цифры подобрать что это будет работать.

[crypto5]

Зачем все эти сложности? Чем lossy counting алгоритм плох, чтобы найти эти самые top 10? На миллиардах записях даст отличную точность.

Ну это уже две разные задачи, отличная точность и 100% точный результат.

А где там было в задаче про "отличную точность"? Может я чего-то пропустил? Berlaga вон сказал, что там вообще про sampling ответ ожидался. А lossy counting по точности sampling порвет как тузик грелку и на большом кол-ве записей (ес-но если не предполагать, что все записи встречаются с приблизительно одинаковой частотой) - выдаст именно те самые искомые top 10 скорее всего с точностью близкой к тем самым 100%. А что еще нужно для поисковых терминов?

Берлага нам рассказал о том что у интервьюера было спрятано в кармане. Про точность в изначальном условии задачи я ничего не утверждал.
Мы с Тарасиком обсуждали точную оценку.

[Интеррапт]

Мы с Тарасиком обсуждали точную оценку.

Ну простите, если помешал вашему диалогу ))) Только вот это предложение

"На самом деле мне кажется если разбить датасет скажем на 1000 частей, и в каждом точно посчитать топ 10к запросов, а потом слить результаты, то 10 запросов посчитаются с 100% точностью."

с точной оценкой пока тоже не вяжется.

[crypto5]

Мы с Тарасиком обсуждали точную оценку.

Ну простите, если помешал вашему диалогу ))) Только вот это предложение

"На самом деле мне кажется если разбить датасет скажем на 1000 частей, и в каждом точно посчитать топ 10к запросов, а потом слить результаты, то 10 запросов посчитаются с 100% точностью."

с точной оценкой пока тоже не вяжется.

Я не настаиваю

[Boriskin]

Все таки строить дерево вхождений по буквам из каждого запроса - получится быстрей пройтись по нему (ну буквально максимум будет максимальная длина поисковой строки) чем делать семплинг\бутстреппинг 1000000 из 1000000000, его сортировку и проч. Кстати мне тоже задавали такой вопрос, я сначала предложил делать кластер или МР но правильным ответом было все же строить дерево, что я им на доске и исполнил.

Было бы неплохо узнать почему. И так ли очевидно что ваше дерево влезет в память вашего компьютера.

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

ЗЫ Не дочитал

[Boriskin]

Отлично, вам нужно 8 нодов, в которых 8 символов, и еще 7 ссылок между ними = 7 * 4 = 28 байт. Сильная компрессия получилась?

Конечно менее встечаемые поиски не будут кодироваться так эффективно но экономия все равно будет.

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

Дык этот наихудший расклад вообще ничем не лечится, разве нет?

[Boriskin]

На самом деле мне кажется если разбить датасет скажем на 1000 частей, и в каждом точно посчитать топ 10к запросов, а потом слить результаты, то 10 запросов посчитаются с 100% точностью.

Обоснование есть по поводу "100% точности"?

Лень сейчас думать, но думаю можно такие цифры подобрать что это будет работать.

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