Ну простите, если помешал вашему диалогу ))) Только вот это предложениеcrypto5 wrote:Мы с Тарасиком обсуждали точную оценку.
Я не настаиваюИнтеррапт wrote:Ну простите, если помешал вашему диалогу ))) Только вот это предложениеcrypto5 wrote:Мы с Тарасиком обсуждали точную оценку.
"На самом деле мне кажется если разбить датасет скажем на 1000 частей, и в каждом точно посчитать топ 10к запросов, а потом слить результаты, то 10 запросов посчитаются с 100% точностью."
с точной оценкой пока тоже не вяжется.
Ну если прикинуть, что в реале дерево строится по мере поступления запросов, то бишь не с ноля, то можно понять, что в реале дерево лучче, так как не требует никакого оверхеда для обновления при поступлении новых запросов.crypto5 wrote:Было бы неплохо узнать почему. И так ли очевидно что ваше дерево влезет в память вашего компьютера.Tarasik wrote:Все таки строить дерево вхождений по буквам из каждого запроса - получится быстрей пройтись по нему (ну буквально максимум будет максимальная длина поисковой строки) чем делать семплинг\бутстреппинг 1000000 из 1000000000, его сортировку и проч. Кстати мне тоже задавали такой вопрос, я сначала предложил делать кластер или МР но правильным ответом было все же строить дерево, что я им на доске и исполнил.
Дык этот наихудший расклад вообще ничем не лечится, разве нет?crypto5 wrote:Ну да, и если вдруг окажется что таких запросов миллиард вся ваша схема накрылась медным тазом.Tarasik wrote:Конечно менее встечаемые поиски не будут кодироваться так эффективно но экономия все равно будет.crypto5 wrote:Отлично, вам нужно 8 нодов, в которых 8 символов, и еще 7 ссылок между ними = 7 * 4 = 28 байт. Сильная компрессия получилась?
Методом от обратного лехко придумывается датасет, на котором самый частый запрос на всех данных не попадет в результирующий список. Более того, можно сделать так, что и все 10 не попадут...crypto5 wrote:Лень сейчас думать, но думаю можно такие цифры подобрать что это будет работать.Интеррапт wrote:Обоснование есть по поводу "100% точности"?crypto5 wrote:На самом деле мне кажется если разбить датасет скажем на 1000 частей, и в каждом точно посчитать топ 10к запросов, а потом слить результаты, то 10 запросов посчитаются с 100% точностью.
Да, согласен, мне тоже уже пришла в голову эта идея.Boriskin wrote:Методом от обратного лехко придумывается датасет, на котором самый частый запрос на всех данных не попадет в результирующий список. Более того, можно сделать так, что и все 10 не попадут...crypto5 wrote:Лень сейчас думать, но думаю можно такие цифры подобрать что это будет работать.Интеррапт wrote:Обоснование есть по поводу "100% точности"?crypto5 wrote:На самом деле мне кажется если разбить датасет скажем на 1000 частей, и в каждом точно посчитать топ 10к запросов, а потом слить результаты, то 10 запросов посчитаются с 100% точностью.
Лечится моим подходом с сортировкой: viewtopic.php?p=5757125#p5757125Boriskin wrote:Дык этот наихудший расклад вообще ничем не лечится, разве нет?crypto5 wrote:Ну да, и если вдруг окажется что таких запросов миллиард вся ваша схема накрылась медным тазом.Tarasik wrote:Конечно менее встечаемые поиски не будут кодироваться так эффективно но экономия все равно будет.crypto5 wrote:Отлично, вам нужно 8 нодов, в которых 8 символов, и еще 7 ссылок между ними = 7 * 4 = 28 байт. Сильная компрессия получилась?
Обьяснитесь?Boriskin wrote:Теория фальсификации Поппера рулит...
Надо же, а у нас в физмат детсадике это называлось просто - найти контрпример.Boriskin wrote:Это из гносеологии - эффективнее идею попробовать опровергнуть, и только если этого сделать не получается - пробовать доказать. Программа кандидатского минимума по философии.
Близка но все же вы будете анализировать < 0.1% информации, в то время как решение с LFU кешем или разбивкой файла на куски будет учитывать всю информацию, при это мпроизводительность будет такая же если все упрется в IO.roadman wrote:
А принципиально разницы нет, на блоках в 1000 запросов статистика уже будет близка к конечному распределению.
Из чего вы взяли, что Яндекс намекнул, и где условие задачи по оптимизации по скорости? Даунсэмплинг очевидно теряет точность. Миллиарды запросов уже хранятся где-то на большом диске, так что рассчитывать на реал-тайм нам уже изначально не приходится.roadman wrote: Как уже Berlaga намекнул, Yandex хотел увидеть какой-нибудь разумный вариант down sampling-га. И как Дорогой Леонид Ильич
Моя идея предпологала разбитие общего лога на массу кусков (тем более, что в реалии он 100% и так и так будет разбит на отдельные файлы). Далее я строил независимые мапы {full url => number}, которые потом предпологалось склеивать. Но наверное можно и дерево строить вместо мапа.roadman wrote:И как Дорогой Леонид Ильич заметил, можно обрабатывать log файлы параллельно, поскольку вставка в хранилище в памяти будет значительно быстрее, чем чтение файлов, особенно если файлы где-нибудь на сети (HDFS).
Вопрос неправильно поставлен, т.к. map может быть реализован с помощью дерева. Если мы говорим про hash table имплементацию vs классическое бинарное дерево, то вставка в hash table будет O(n) в худшем случае, average - это вопрос интересный, потому что мы тут его как-то рассматривали в скроллере из 10 страниц.Леонид Ильич Брежнев wrote: Так вот у меня вопросы к теоретикам CS
1) насколько insert в мап хуже/лучше чем в дерево. По-моему, для мапа это будет О(n), a для дерева какой-нибудь O(n * log(n))
2) насколько мап на отдельной машине (скажем 1/50 всех логов) будет меньше/больше, дерева построенного из тех же данных?
3) насколько "склеивать" с полсотни мапов сложнее чем с полсотни деревьев?
Теоретически, когда мы знаем распределение ключей и их кол-во, подборкой hash-function и размер bucket'ов, можно предположить, что вставка будет константой. В нашем конкретном случае можно проблема будет не в сложности вставки, а в том, что, скорее всего, придется hash map дробить заранее. Размер дерева нам будет трудно соптимизировать, потому что придется тратить место на ссылки между элементами. И, кстати, какое дерево мы строим? На больших данных, которые не влезают в память. с большим кол-вом модификаций эффективнее перейти на B-tree.
Тот худший случай, когда размер таблицы 1 и всё новые элементы вставляются в конец списка коллизий?dotcom wrote:Вопрос неправильно поставлен, т.к. map может быть реализован с помощью дерева. Если мы говорим про hash table имплементацию vs классическое бинарное дерево, то вставка в hash table будет O(n) в худшем случае
О каком "мап" идет речь?Леонид Ильич Брежнев wrote: 2) насколько мап на отдельной машине (скажем 1/50 всех логов) будет меньше/больше, дерева построенного из тех же данных?
Ну какой-нибудь HashMap/HashTable, если в терминах джавы.Интеррапт wrote:О каком "мап" идет речь?Леонид Ильич Брежнев wrote: 2) насколько мап на отдельной машине (скажем 1/50 всех логов) будет меньше/больше, дерева построенного из тех же данных?
В классической таблице без дубликатов еще нужно проходить по списку что бы убедится что элемент уже не вставлен.Medium-rare wrote: Upd. Даже в этом случае собственно вставка не должна быть O(n). Помним хвост списка, и все дела. Только поиск может достичь той абсурдной сложности, при абсурдной таблице.
Речь идет про rehash. Да, можно организовать таблицу так, чтобы rehash с потерей чего-то другого. Да, это не O(n) в общем случае.Medium-rare wrote: Тот худший случай, когда размер таблицы 1 и всё новые элементы вставляются в конец списка коллизий?
Upd. Даже в этом случае собственно вставка не должна быть O(n). Помним хвост списка, и все дела. Только поиск может достичь той абсурдной сложности, при абсурдной таблице.
Это да... верно.crypto5 wrote: В классической таблице без дубликатов еще нужно проходить по списку что бы убедится что элемент уже не вставлен.
А, увеличение таблицы x2, understood. Не real-time решение.dotcom wrote: Речь идет про rehash. Да, можно организовать таблицу так, чтобы rehash с потерей чего-то другого. Да, это не O(n) в общем случае.