crypto5 wrote:
А алгоритмически - посортировать, пройтись по сортированному списку, посчитать каунты, потом еще раз пройтись и найти десять самых больших каунтов, потом еще раз пройтись, и найти запросы для этих каунтов.
дорогое решение, даже если в процессе сортировки повторения убирать и счетчик увеличивать. имхо лучше сначала кластеризовать по некот. признаку подобия. потом отсортировать только кластер с наименьшей дисперсией, если там в итоге окажется < 10 запросов, отсортировать следуюший. Так же подход будет хорош, если соответствие 2-х (одинаковых) запросов не 100%
Осталось узнать хороший принцип подобия, и хороший алгоритм кластеризации, а там может и тунели сойдутся.
Именно поэтому в гугле просят на доске код написать, что-бы туман мудрости развеять.
Зачем сохранять части а не сразу использовать хеш поиска как ключ? Для последующего поиска самых больших запросов например что бы не искать весь миллиард а скорее пройтись по П => "ПО" => "ПОЧЕМУ" нет?
Я бы все-таки дождался точного вопроса. А то диапазон решений может быть от подсчета частоты появления слова из словаря до теории, как делать map-reduce. А, может, и все сразу.
Зачем сохранять части а не сразу использовать хеш поиска как ключ? Для последующего поиска самых больших запросов например что бы не искать весь миллиард а скорее пройтись по П => "ПО" => "ПОЧЕМУ" нет?
Я совершенно не понял мысли, что означает "хеш поиска" в частности, и как именно предлагается найти 10 самых часто встречающихся запросов вообще.
Т.е. я согласен, что если заюзать trie вместо сортировки в моем алгоритме, то оно бусет работать. Вы это предлагаете?
если подразумевается "точная" (буква к букве, пробел к пробелу) идентичность 2х запросов, то кластеризуем по длине строки сначала, а там уже делаем субкластеризацию самого большого кластера.
dotcom wrote:Я бы все-таки дождался точного вопроса.
А это и был точный вопрос. Ну еще в качестве разъяснения добавили, что это массив реальных запросов к поисковой системе Яндекса за некоторый период времени, допустим одну неделю. Все.
Komissar wrote:если подразумевается "точная" (буква к букве, пробел к пробелу) идентичность 2х запросов, то кластеризуем по длине строки сначала, а там уже делаем субкластеризацию самого большого кластера.
Ну можно по многим разным признакам покластеризовать, только вы никак не сможете прикинуть какая окуратность вашего решения в конце концов получится.
dotcom wrote:Я бы все-таки дождался точного вопроса.
А это и был точный вопрос. Ну еще в качестве разъяснения добавили, что это массив реальных запросов к поисковой системе Яндекса за некоторый период времени, допустим одну неделю. Все.
Ну тогда это открытый вопрос на смекалку и общие знания.
crypto5 wrote:
Осталось узнать хороший принцип подобия, и хороший алгоритм кластеризации, а там может и тунели сойдутся.
Именно поэтому в гугле просят на доске код написать, что-бы туман мудрости развеять.
на вскидку параметры: количество символов в запросе, их распределение (частота встречаемости символа), символы рассматривать не все, ограничится например "a", "t", etc. (based on prior knowledge regarding what symbols discriminate better)
Я боюсь, что наступит день, когда технологии превзойдут простое человеческое обшение. И мир получит поколение идиотов (c)
crypto5 wrote:
Осталось узнать хороший принцип подобия, и хороший алгоритм кластеризации, а там может и тунели сойдутся.
Именно поэтому в гугле просят на доске код написать, что-бы туман мудрости развеять.
на вскидку параметры: количество символов в запросе, их распределение (частота встречаемости символа), символы рассматривать не все, ограничится например "a", "t", etc. (based on prior knowledge regarding what symbols discriminate better)
А откуда вы узнали что это именно хорошие признаки подобия? и алгоритм выдаст хорошую точность?
И не могли бы вы как то оценить, почему все ваши манипуляции будут работать быстрее моего алгоритма? Я тоже могу наповыдумывать много необычных штук, но это все будет пальцем в небо.
Задача, если мне не изменяет склероз, модификация "стандартной", удалите(найдите) дубликаты строк из ну очень большого и несортированного массива. И в зависимости от положения звезд на небе, сделать это надо с имеющимися ограничениями по объему используемой памяти или времени, или того и другого одновременно, или как-нибудь, но с "изюминкой", например, в одну строчку.
А еще вопрос - список хоть отсортирован, уже хеширован и т.п.? Как-то ведь слабо верится, что они просто тупо скидывают все запросы в один, условно говоря файл, без того, чтобы проделывать все эти манипуляции по мере поступления данных?
Интеррапт wrote:А еще вопрос - список хоть отсортирован, уже хеширован и т.п.? Как-то ведь слабо верится, что они просто тупо скидывают все запросы в один, условно говоря файл, без того, чтобы проделывать все эти манипуляции по мере поступления данных?
Интеррапт wrote:А еще вопрос - список хоть отсортирован, уже хеширован и т.п.? Как-то ведь слабо верится, что они просто тупо скидывают все запросы в один, условно говоря файл, без того, чтобы проделывать все эти манипуляции по мере поступления данных?
А что такое - хешированный список?
Не список хеширован, а элементы в нем. По большому счету, должны же как минимум сразу хеш запроса (записи) калькулировать, как это делают обычные базы данных при индексации, а не просто тупо сохранять миллиарды записей в файл, а потом с ними манипулировать.
Интеррапт wrote:А еще вопрос - список хоть отсортирован, уже хеширован и т.п.? Как-то ведь слабо верится, что они просто тупо скидывают все запросы в один, условно говоря файл, без того, чтобы проделывать все эти манипуляции по мере поступления данных?
А что такое - хешированный список?
Не список хеширован, а элементы в нем. По большому счету, должны же они сразу хеш запроса (записи) калькулировать, как это делают обычные базы данных при индексации, а не просто тупо сохранять миллиарды записей в файл, а потом с ними манипулировать.
Ну вот в разных хадупах так и делают, просто сохраняют записи в файлах, и потом их мепредьюсят, без всяких хешей.
Интеррапт wrote:Как-то ведь слабо верится, что они просто тупо скидывают все запросы в один, условно говоря файл, без того, чтобы проделывать все эти манипуляции по мере поступления данных?
Манипуляции проделываются, но не совсем в реальном времени, т.е. можно считать, что все валится в кучу.
ну тут, как всегда, вопрос в востребованности хешированных данных. На этом вся БЫГ ДАТА и построена, что, как оказалось, вся data integrity, indexing, etc - в 99% никому не нужны, потому все проще сваливать в одну помойку, а уж если потребуется, потом в той помойке что-то конкретное искать. Я вот все хочу такое же применить к моим tax-supporting documents.
Интеррапт wrote:Как-то ведь слабо верится, что они просто тупо скидывают все запросы в один, условно говоря файл, без того, чтобы проделывать все эти манипуляции по мере поступления данных?
Манипуляции проделываются, но не совсем в реальном времени, т.е. можно считать, что все валится в кучу.
Да понятное дело, что можно манипулировать как угодно, пусть даже не в реальном времени. Но определенный препроцессинг можно делать уже на этапе получения данных (пусть даже определенными бакетами). Ну вот вряд-ли просто тупо выкатят тебе миллиарды записей и скажут, а ну посчитай что тут и как. Умнее же должно это быть.
