80 символов на средний запрос - это сильно врядли.Леонид Ильич Брежнев wrote:А что никого не смутило, что размер дерева для скажем среднестатистического запроса длиной в скажем 80 символов,
Code: Select all
Organic Search: Average Share by Word Count (Non-Brand)
Дорогой Леонид Ильич, мне все решения нравятся. Но суть задачи была именно в том, что массив данных большой и читать его целиком долго и дорого.Леонид Ильич Брежнев wrote:Берлага, А Вам что мое решение совсем не нравится или Вы принципиальный противник Центрального Комитета?
А я всерьез задумываюсь поставить замок, который открывается телефономstenking wrote:И ещё у вас есть место для жизни где есть дверь. И там тоже есть замок. И тоже логично предположить что он открывается ключом. А когда ключей больше чем один то они обычно организовываются в связку.
Ну так я выше (до труе) предлагал решения с экстернал сортингBerlaga wrote:Дорогой Леонид Ильич, мне все решения нравятся. Но суть задачи была именно в том, что массив данных большой и читать его целиком долго и дорого.Леонид Ильич Брежнев wrote:Берлага, А Вам что мое решение совсем не нравится или Вы принципиальный противник Центрального Комитета?
Если это миллиарды запросов, то почему их читать долго? Пол часа наверное с лаптопного ССД диска.Berlaga wrote:Дорогой Леонид Ильич, мне все решения нравятся. Но суть задачи была именно в том, что массив данных большой и читать его целиком долго и дорого.Леонид Ильич Брежнев wrote:Берлага, А Вам что мое решение совсем не нравится или Вы принципиальный противник Центрального Комитета?
Может, потому что нужно уложиться в доли секунды?crypto5 wrote:Если это миллиарды запросов, то почему их читать долго? Пол часа наверное с лаптопного ССД диска.
Может и потому, давайте спросим, было ли такое условие на интервью?АццкоМото wrote:Может, потому что нужно уложиться в доли секунды?crypto5 wrote:Если это миллиарды запросов, то почему их читать долго? Пол часа наверное с лаптопного ССД диска.
Возможно и читает, и сегодня лаптоп сломалсяА-ля как Гоголь не читает полчаса с лаптопного диска, когда я начинаю в строке поиска струячить
Было бы неплохо узнать почему. И так ли очевидно что ваше дерево влезет в память вашего компьютера.Tarasik wrote:Все таки строить дерево вхождений по буквам из каждого запроса - получится быстрей пройтись по нему (ну буквально максимум будет максимальная длина поисковой строки) чем делать семплинг\бутстреппинг 1000000 из 1000000000, его сортировку и проч. Кстати мне тоже задавали такой вопрос, я сначала предложил делать кластер или МР но правильным ответом было все же строить дерево, что я им на доске и исполнил.
Оно не влезет. Оно поместится. По аналогии с деревьями Хоффмана которые используются в сферическом вакууме для компрессии текста.crypto5 wrote:Было бы неплохо узнать почему. И так ли очевидно что ваше дерево влезет в память вашего компьютера.Tarasik wrote:Все таки строить дерево вхождений по буквам из каждого запроса - получится быстрей пройтись по нему (ну буквально максимум будет максимальная длина поисковой строки) чем делать семплинг\бутстреппинг 1000000 из 1000000000, его сортировку и проч. Кстати мне тоже задавали такой вопрос, я сначала предложил делать кластер или МР но правильным ответом было все же строить дерево, что я им на доске и исполнил.
Железная аргументацияTarasik wrote:Оно не влезет. Оно поместится. По аналогии с деревьями Хоффмана которые используются в сферическом вакууме для компрессии текста.crypto5 wrote:Было бы неплохо узнать почему. И так ли очевидно что ваше дерево влезет в память вашего компьютера.Tarasik wrote:Все таки строить дерево вхождений по буквам из каждого запроса - получится быстрей пройтись по нему (ну буквально максимум будет максимальная длина поисковой строки) чем делать семплинг\бутстреппинг 1000000 из 1000000000, его сортировку и проч. Кстати мне тоже задавали такой вопрос, я сначала предложил делать кластер или МР но правильным ответом было все же строить дерево, что я им на доске и исполнил.
Сейчас попытаюсь набросать - где бы взять миллиардный список запросов не подскажете ?Tarasik wrote:Оно не влезет. Оно поместится. По аналогии с деревьями Хоффмана которые используются в сферическом вакууме для компрессии текста.crypto5 wrote:Было бы неплохо узнать почему. И так ли очевидно что ваше дерево влезет в память вашего компьютера.Tarasik wrote:Все таки строить дерево вхождений по буквам из каждого запроса - получится быстрей пройтись по нему (ну буквально максимум будет максимальная длина поисковой строки) чем делать семплинг\бутстреппинг 1000000 из 1000000000, его сортировку и проч. Кстати мне тоже задавали такой вопрос, я сначала предложил делать кластер или МР но правильным ответом было все же строить дерево, что я им на доске и исполнил.
Вы сама беспомощность ))Tarasik wrote:Сейчас попытаюсь набросать - где бы взять миллиардный список запросов не подскажете ?Tarasik wrote:Оно не влезет. Оно поместится. По аналогии с деревьями Хоффмана которые используются в сферическом вакууме для компрессии текста.crypto5 wrote:Было бы неплохо узнать почему. И так ли очевидно что ваше дерево влезет в память вашего компьютера.Tarasik wrote:Все таки строить дерево вхождений по буквам из каждого запроса - получится быстрей пройтись по нему (ну буквально максимум будет максимальная длина поисковой строки) чем делать семплинг\бутстреппинг 1000000 из 1000000000, его сортировку и проч. Кстати мне тоже задавали такой вопрос, я сначала предложил делать кластер или МР но правильным ответом было все же строить дерево, что я им на доске и исполнил.
Я вообще не вижу здесь аналогии с кодом Хаффмана. В случае Хаффмана - дерево будет маленькое, т.к. строится на основе частот встречаемости символа.Tarasik wrote:Оно не влезет. Оно поместится. По аналогии с деревьями Хоффмана которые используются в сферическом вакууме для компрессии текста.crypto5 wrote:Было бы неплохо узнать почему. И так ли очевидно что ваше дерево влезет в память вашего компьютера.Tarasik wrote:Все таки строить дерево вхождений по буквам из каждого запроса - получится быстрей пройтись по нему (ну буквально максимум будет максимальная длина поисковой строки) чем делать семплинг\бутстреппинг 1000000 из 1000000000, его сортировку и проч. Кстати мне тоже задавали такой вопрос, я сначала предложил делать кластер или МР но правильным ответом было все же строить дерево, что я им на доске и исполнил.
В случае с кодом Хаффмана дерево на самом деле маленькое, потому что блок архивирования маленький, а так бы оно было большое ))Интеррапт wrote:Я вообще не вижу здесь аналогии с кодом Хаффмана. В случае Хаффмана - дерево будет маленькое, т.к. строится на основе частот встречаемости символа.Tarasik wrote:Оно не влезет. Оно поместится. По аналогии с деревьями Хоффмана которые используются в сферическом вакууме для компрессии текста.crypto5 wrote:Было бы неплохо узнать почему. И так ли очевидно что ваше дерево влезет в память вашего компьютера.Tarasik wrote:Все таки строить дерево вхождений по буквам из каждого запроса - получится быстрей пройтись по нему (ну буквально максимум будет максимальная длина поисковой строки) чем делать семплинг\бутстреппинг 1000000 из 1000000000, его сортировку и проч. Кстати мне тоже задавали такой вопрос, я сначала предложил делать кластер или МР но правильным ответом было все же строить дерево, что я им на доске и исполнил.
Обьясните, что тут общего и где вы видите аналогию?
Что такое "блок архивирования"? Например, если у тебя будет файл в 10 гигабайт с каким-нибудь английским текстом, то дерево будет такого же размера, как и для файла с 1 мегабайтом английского текста. А именно - будет маленьким.crypto5 wrote: В случае с кодом Хаффмана дерево на самом деле маленькое, потому что блок архивирования маленький, а так бы оно было большое ))
Да, потому что архиватор разбивает большой файл на маленькие блоки (например 8МБ), и для каждого строит отдельное дерево и потом им отдельно архивирует.Интеррапт wrote:Что такое "блок архивирования"? Например, если у тебя будет файл в 10 гигабайт с каким-нибудь английским текстом, то дерево будет такого же размера, как и для файла с 1 мегабайтом английского текста. А именно - будет маленьким.crypto5 wrote: В случае с кодом Хаффмана дерево на самом деле маленькое, потому что блок архивирования маленький, а так бы оно было большое ))
Ничего не поменяется, если построение дерева будет по гигабайтному англ тексту, а не по 8 мегабайт. На что спорим?crypto5 wrote:Да, потому что архиватор разбивает большой файл на маленькие блоки (например 8МБ), и для каждого строит отдельное дерево и потом им отдельно архивирует.Интеррапт wrote:Что такое "блок архивирования"? Например, если у тебя будет файл в 10 гигабайт с каким-нибудь английским текстом, то дерево будет такого же размера, как и для файла с 1 мегабайтом английского текста. А именно - будет маленьким.crypto5 wrote: В случае с кодом Хаффмана дерево на самом деле маленькое, потому что блок архивирования маленький, а так бы оно было большое ))
Ладно, согласен, я че то себе код Хаффмана по другому совсем представлял.Интеррапт wrote:Ничего не поменяется, если сканирование будет по гигабайту, а не по 8 мегабайт. На что спорим?crypto5 wrote:Да, потому что архиватор разбивает большой файл на маленькие блоки (например 8МБ), и для каждого строит отдельное дерево и потом им отдельно архивирует.Интеррапт wrote:Что такое "блок архивирования"? Например, если у тебя будет файл в 10 гигабайт с каким-нибудь английским текстом, то дерево будет такого же размера, как и для файла с 1 мегабайтом английского текста. А именно - будет маленьким.crypto5 wrote: В случае с кодом Хаффмана дерево на самом деле маленькое, потому что блок архивирования маленький, а так бы оно было большое ))
Так вот, возвращаясь к нашим баранам, я поэтому совсем не вижу аналогии с кодом Хаффмана и нашей задачей. Дерево при построении кода Хаффмана - крошечное, поэтому ну хоть убей, но аналогии не вижу. Но может Tarasik обьяснит, что он общего увидел.crypto5 wrote:Ладно, согласен, я че то себе код Хаффмана по другому совсем представлял.
Они имеют общего то, что в запросах многие строки полностью или частично совпадают а дерево Хафмана сжимает потому что буквы в тексте повторяются (и их соответственно можно записать меньшим количеством битов чем они занимают в натуре, а если алгоритм усложнить и записывать битами словосочетания а не только буквы то будет сжимать еще лучше). Более того, если дерево для кодирования вебзапросов кодировать минимально необходимыми битами а не юникодом (2мя байтами) на символ, то дерево вебзапросов сожмет еще лучше потому что для нас не важна последовательность запросов - мы можем их восстановить в произвольном порядке а одного дерева хафмана для восстановления текста недостаточно - нужна последовательность битов.Интеррапт wrote:Так вот, возвращаясь к нашим баранам, я поэтому совсем не вижу аналогии с кодом Хаффмана и нашей задачей. Дерево при построении кода Хаффмана - крошечное, поэтому ну хоть убей, но аналогии не вижу. Но может Tarasik обьяснит, что он общего увидел.crypto5 wrote:Ладно, согласен, я че то себе код Хаффмана по другому совсем представлял.
Пример очень плохой. Потому что вы нарисовали дерево Хаффмана, но вы не нарисовали сами данные, которые этим деревом кодироваться будут. Дерево только алгоритм кодирования символов содержит, но не содержит сами данные, которые этим деревом будут кодироваться.Tarasik wrote:пример конечно не очень хороший но достаточно для того чтоб показать что количество нодов будет меньше чем символов в наборе поисковых запросов.
Ну мне показалось что это префиксное дерево а не дерево ХоффманаИнтеррапт wrote:Пример очень плохой. Потому что вы нарисовали дерево Хаффмана, но вы не нарисовали сами данные, которые этим деревом кодироваться будут. Дерево только алгоритм кодирования символов содержит, но не содержит сами данные, которые этим деревом будут кодироваться.Tarasik wrote:пример конечно не очень хороший но достаточно для того чтоб показать что количество нодов будет меньше чем символов в наборе поисковых запросов.