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

[crypto5]

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

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

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

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

Да, согласен, мне тоже уже пришла в голову эта идея.

[crypto5]

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

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

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

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

Лечится моим подходом с сортировкой: viewtopic.php?p=5757125#p5757125

[Boriskin]

Теория фальсификации Поппера рулит...

[crypto5]

Теория фальсификации Поппера рулит...

Обьяснитесь?

[Boriskin]

Это из гносеологии - эффективнее идею попробовать опровергнуть, и только если этого сделать не получается - пробовать доказать. Программа кандидатского минимума по философии.

[crypto5]

Это из гносеологии - эффективнее идею попробовать опровергнуть, и только если этого сделать не получается - пробовать доказать. Программа кандидатского минимума по философии.

Надо же, а у нас в физмат детсадике это называлось просто - найти контрпример.

[Boriskin]

Контр-пример - это когда можно сообразить на пальцах, но бывает намного сложнее/абстрактнее, но смысл тот же.

[roadman]

Исходя из того что запросы от реальной поисковой системы, то распределение по частоте будет что-то типа:
C/x, where x=> 1,2,...,N and C number queries of the most popular request.
Допустим, что мы можем позволить иметь в памяти массив целых чисел (номера запросов в файле). Один миллион елементов в памяти не должен вызвать технических затруднений (можно уменьшить до 64К если памяти много нету).
1 шаг. Запоминаем первые 1М запросов.
2 шаг. Генерируем случайное число j в диапазоне [0-N], где N - число прочитанных запросов из файла включая первые 1М
3 шаг. Заменяем j-ый елемент в 1М массиве, если j<1М, а если j>=1M, то игнорируем прочитанный запрос.
Повторяем шаги 2-3 пока не прочитаем весь файл.
Имеем 1М случайно отобранных запросов из последовательности любой длины, причем вероятность любого элемента попасть в "финал" одинакова.
Ну а быстрых способов найти 10 наиболее популярных запросов из 1М множество. Поскольку распределение запросов С/х, то при случайной выборке и достаточном числе образцов оно сохранит свой вид. На самом деле точное распределение не важно, важно чтобы оно достаточно быстро уменьшалось в пределах размера "финалистов".

[crypto5]

А чем такой подход лучше описаного варианта с кешем, или моего варианта с разбиванием файла на 1000 кусков, кроме очевидно меньшей точности?

[roadman]

Как организовать в памяти хранение не принципиально, можно и hash map, важно, что размер этого хранилища может быть маленьким и даже помещаться к кэш процессора, независимо от числа запросов в файле. А вот манипуляция с файлами процедура медленная и лучше читать файл один раз проследовательно. Это под углом, чтобы работало быстро и на log файлах с заранее неизвестными размерами.
А принципиально разницы нет, на блоках в 1000 запросов статистика уже будет близка к конечному распределению.
Как уже Berlaga намекнул, Yandex хотел увидеть какой-нибудь разумный вариант down sampling-га. И как Дорогой Леонид Ильич заметил, можно обрабатывать log файлы параллельно, поскольку вставка в хранилище в памяти будет значительно быстрее, чем чтение файлов, особенно если файлы где-нибудь на сети (HDFS).

[crypto5]

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

Близка но все же вы будете анализировать < 0.1% информации, в то время как решение с LFU кешем или разбивкой файла на куски будет учитывать всю информацию, при это мпроизводительность будет такая же если все упрется в IO.

[dotcom]

Как уже Berlaga намекнул, Yandex хотел увидеть какой-нибудь разумный вариант down sampling-га. И как Дорогой Леонид Ильич

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

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

И как Дорогой Леонид Ильич заметил, можно обрабатывать log файлы параллельно, поскольку вставка в хранилище в памяти будет значительно быстрее, чем чтение файлов, особенно если файлы где-нибудь на сети (HDFS).

Моя идея предпологала разбитие общего лога на массу кусков (тем более, что в реалии он 100% и так и так будет разбит на отдельные файлы). Далее я строил независимые мапы {full url => number}, которые потом предпологалось склеивать. Но наверное можно и дерево строить вместо мапа.

Так вот у меня вопросы к теоретикам CS
1) насколько insert в мап хуже/лучше чем в дерево. По-моему, для мапа это будет О(n), a для дерева какой-нибудь O(n * log(n))
2) насколько мап на отдельной машине (скажем 1/50 всех логов) будет меньше/больше, дерева построенного из тех же данных?
3) насколько "склеивать" с полсотни мапов сложнее чем с полсотни деревьев?

[dotcom]

Так вот у меня вопросы к теоретикам CS
1) насколько insert в мап хуже/лучше чем в дерево. По-моему, для мапа это будет О(n), a для дерева какой-нибудь O(n * log(n))
2) насколько мап на отдельной машине (скажем 1/50 всех логов) будет меньше/больше, дерева построенного из тех же данных?
3) насколько "склеивать" с полсотни мапов сложнее чем с полсотни деревьев?

Вопрос неправильно поставлен, т.к. map может быть реализован с помощью дерева. Если мы говорим про hash table имплементацию vs классическое бинарное дерево, то вставка в hash table будет O(n) в худшем случае, average - это вопрос интересный, потому что мы тут его как-то рассматривали в скроллере из 10 страниц. Теоретически, когда мы знаем распределение ключей и их кол-во, подборкой hash-function и размер bucket'ов, можно предположить, что вставка будет константой. В нашем конкретном случае можно проблема будет не в сложности вставки, а в том, что, скорее всего, придется hash map дробить заранее. Размер дерева нам будет трудно соптимизировать, потому что придется тратить место на ссылки между элементами. И, кстати, какое дерево мы строим? На больших данных, которые не влезают в память. с большим кол-вом модификаций эффективнее перейти на B-tree.
Дробить и то и другое одинаково легко.

[Medium-rare]

Вопрос неправильно поставлен, т.к. map может быть реализован с помощью дерева. Если мы говорим про hash table имплементацию vs классическое бинарное дерево, то вставка в hash table будет O(n) в худшем случае

Тот худший случай, когда размер таблицы 1 и всё новые элементы вставляются в конец списка коллизий?
Upd. Даже в этом случае собственно вставка не должна быть O(n). Помним хвост списка, и все дела. Только поиск может достичь той абсурдной сложности, при абсурдной таблице.