Как насчет использования Splay Tree с 10 узлами? Каждый раз, когда вы пытаетесь получить доступ к значению (поисковому запросу), которого нет в дереве, выбрасывайте любой лист, вставляйте вместо него значение и обращайтесь к нему.

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

править

В дереве можно также сохранить еще несколько условий поиска (то же самое касается решения, которое я предлагаю в другом ответе), чтобы не удалять узел, к которому очень скоро снова может произойти доступ. Чем больше значений хранится в нем, тем лучше результаты.

Один из способов заключается в том, что для каждого поиска вы сохраняете этот поисковый запрос и его временную метку. Таким образом, поиск первой десятки за любой период времени - это просто вопрос сравнения всех поисковых запросов за данный период времени.

Алгоритм прост, но недостатком будет большее потребление памяти и времени.

Топ-10 поисковых запросов за последний месяц

Использование эффективной для памяти индексации/структуры данных, такой как плотно упакованные тризы (из википедии о тризах) примерно определяет некоторое соотношение между требованиями к памяти и n - количеством терминов.

В случае, если требуемая память доступна (предположение 1), можно хранить точную месячную статистику и агрегировать ее каждый месяц в статистику за все время.

Здесь также есть предположение, что "последний месяц" интерпретируется как фиксированное окно. Но даже если месячное окно является скользящим, приведенная выше процедура показывает принцип (скользящее окно может быть аппроксимировано фиксированными окнами заданного размера).

Это напоминает мне round-robin database, за исключением того, что некоторые статистики рассчитываются по "всему времени" (в том смысле, что не все данные сохраняются; rrd объединяет временные периоды, игнорируя детали путем усреднения, суммирования или выбора макс/мин значений, в данной задаче теряется информация о низкочастотных элементах, что может внести ошибки).

Предположение 1

Если мы не можем иметь идеальную статистику за весь месяц, то мы должны быть в состоянии найти определенный период P, за который мы должны иметь идеальную статистику. Например, если предположить, что у нас есть идеальная статистика за некоторый период времени P, который переходит в месяц n раз.
Идеальную статистику определяет функция f(search_term) -> search_term_occurance.

Если мы можем держать в памяти все n таблиц идеальной статистики, то скользящая ежемесячная статистика может быть вычислена следующим образом:

• добавить статистику за самый новый период
• удалить статистику за самый старый период (поэтому мы должны держать n таблиц идеальной статистики)

Однако, если мы будем хранить только топ-10 на агрегированном уровне (ежемесячно), то мы сможем отбросить много данных из полной статистики за фиксированный период. Это уже дает рабочую процедуру, которая имеет фиксированные (в предположении верхней границы на идеальную таблицу статистики для периода P) требования к памяти.

Проблема с приведенной выше процедурой заключается в том, что если мы храним информацию только о 10 лучших терминах для скользящего окна (аналогично для всего времени), то статистика будет правильной для поисковых терминов, которые достигают пика за период, но может не увидеть статистику для поисковых терминов, которые постоянно просачиваются в течение времени.

Это можно компенсировать, сохраняя информацию о более чем 10 лучших терминах, например, о 100 лучших терминах, надеясь, что 10 лучших будут корректными.

Я думаю, что дальнейший анализ может быть связан с минимальным количеством вхождений, необходимым для того, чтобы запись стала частью статистики (что связано с максимальной ошибкой).

(Решая, какие записи должны стать частью статистики, можно также отслеживать тенденции; например, если линейная экстраполяция вхождений в каждом периоде P для каждого термина говорит вам, что этот термин станет значимым через месяц или два, вы можете уже сейчас начать его отслеживать. Аналогичный принцип применим для удаления поискового термина из отслеживаемого пула).

Худший случай для вышесказанного - когда у вас много почти одинаково часто встречающихся терминов, и они все время меняются (например, если отслеживать только 100 терминов, то если топ-150 терминов встречаются одинаково часто, но топ-50 чаще в первый месяц и реже спустя некоторое время, то статистика будет вестись неправильно).

Также может быть другой подход, не фиксированный по объему памяти (ну, строго говоря, как и вышеописанный), который бы определял минимальную значимость в терминах вхождений/периода (день, месяц, год, все время), для которого нужно вести статистику. Это могло бы гарантировать максимальную ошибку в каждой из статистик во время агрегирования (см. снова round robin).

Точное решение

Сначала решение, которое гарантирует правильные результаты, но требует много памяти (большая карта).

"All-time" вариант

Храните хэш-карту с запросами в качестве ключей и их количествами в качестве значений. Кроме того, храните список f 10 наиболее частых запросов на данный момент и счетчик 10-го наиболее частого запроса (порог).

Постоянно обновляйте карту по мере считывания потока запросов. Каждый раз, когда счетчик превышает текущий порог, сделайте следующее: удалите 10-й запрос из списка "Топ-10", замените его запросом, который вы только что обновили, и также обновите порог.

"Прошлый месяц" вариант

Сохраните тот же список "Топ-10" и обновите его так же, как описано выше. Также сохраните аналогичную карту, но на этот раз в качестве значений храните векторы из 30*24 = 720 отсчетов (по одному на каждый час). Каждый час для каждого ключа делайте следующее: удалите самый старый счетчик из вектора, добавьте новый (инициализированный в 0) в конец. Удалите ключ из карты, если вектор полностью нулевой. Кроме того, каждый час вы должны вычислять список "Топ-10" с нуля.

Примечание: Да, на этот раз мы храним 720 целых чисел вместо одного, но ключей гораздо меньше (вариант all-time имеет действительно длинный хвост).

Приближения

Эти приближения не гарантируют правильного решения, но занимают меньше памяти.

1. Обработать каждый N-й запрос, пропуская остальные.
2. (Только для варианта all-time) Храните в карте не более M пар ключ-значение (M должно быть настолько большим, насколько вы можете себе позволить). Это своего рода кэш LRU: каждый раз, когда вы читаете запрос, которого нет в карте, удалите наименее недавно использованный запрос с количеством 1 и замените его текущим обработанным запросом.

Можно использовать хэш-таблицу в сочетании с двоичным деревом поиска. Реализуйте словарь <термин поиска, счетчик>, который сообщает, сколько раз искался каждый термин поиска.

Очевидно, что итерировать всю хэш-таблицу каждый час, чтобы получить топ-10 - это очень плохо. Но мы говорим о Google, поэтому можно предположить, что все десять лучших терминов получат, скажем, более 10 000 просмотров (возможно, это число гораздо больше). Поэтому каждый раз, когда количество поисковых запросов превышает 10 000, вставляйте их в BST. Тогда каждый час вам придется получать из BST только первые 10, которые должны содержать относительно немного записей.

Это решает проблему топ-10 за все время.

По-настоящему сложной частью является решение проблемы, когда один термин занимает место другого в ежемесячном отчете (например, "stack overflow" может иметь 50 000 просмотров за последние два месяца, но только 10 000 за последний месяц, в то время как "amazon" может иметь 40 000 за последние два месяца, но 30 000 за последний месяц. Вы хотите, чтобы в ежемесячном отчете "amazon" стоял перед "stack overflow"). Для этого я бы сохранил для всех основных (более 10 000 поисковых запросов за все время) поисковых терминов 30-дневный список, в котором указано, сколько раз этот термин искали в каждый день. Список будет работать как очередь FIFO: вы удаляете первый день и вставляете новый каждый день (или каждый час, но тогда вам может понадобиться хранить больше информации, что означает больше памяти / места. Если память не является проблемой, сделайте это, в противном случае перейдите на "приближение", о котором они говорят).

Это похоже на хорошее начало. Затем вы можете заняться обрезкой терминов, которые имеют > 10 000 просмотров, но не имели их в течение длительного времени, и тому подобное.

Обзор оценки частоты

Существует несколько хорошо известных алгоритмов, которые могут предоставить оценки частоты для такого потока с использованием фиксированного объема памяти. Один из них - Часто, Мисра и Грайс (1982). Из списка n элементов он находит все элементы, которые встречаются более n / k раз, используя счетчики k - 1 . Это обобщение алгоритма Бойера и Мура Большинство (Fischer-Salzberg, 1982), где k равно 2.Алгоритмы Manku и Motwani LossyCounting (2002) и Metwally SpaceSaving (2005) имеют аналогичные требования к пространству, но могут обеспечить более точные оценки при определенных условиях.

Важно помнить, что эти алгоритмы могут предоставлять только оценки частоты. В частности, оценка Мисра-Гриса может занижать фактическую частоту на (n / k) пунктов.

Предположим, у вас есть алгоритм, который может положительно идентифицировать элемент только , если он встречается более чем в 50% случаев. Подайте в этот алгоритм поток из N отдельных элементов, а затем добавьте еще N - 1 копий одного элемента, x , всего 2N - 1 шт. Если алгоритм сообщает вам, что x превышает 50% от общего количества, это должно быть в первом потоке; в противном случае x не было в исходном потоке. Чтобы алгоритм сделал это определение, он должен сохранить исходный поток (или некоторую сводку, пропорциональную его длине)! Итак, мы можем доказать себе, что для такого «точного» алгоритма требуется пространство Ω ( N ).

Вместо этого описанные здесь частотные алгоритмы обеспечивают оценку, идентифицируя любой элемент, который превышает пороговое значение, а также некоторые элементы, которые опускаются ниже этого порога с определенным запасом. Например, алгоритм Большинство , использующий один счетчик, всегда будет давать результат; если какой-либо элемент превышает 50% потока, он будет найден. Но он также может дать вам элемент, который встречается только один раз.Вы бы не узнали этого, не сделав второй проход по данным (используя, опять же, один счетчик, но ища только этот элемент).

Частый алгоритм

Вот простое описание алгоритма Мисра-Гриса Частого . Demaine (2002) и другие оптимизировали алгоритм, но это дает вам суть.

Укажите пороговую долю, 1 / k ; будет найден любой элемент, который встречается более n / k раз. Создайте пустую карту (например, красно-черное дерево); ключи будут условиями поиска, а значения будут счетчиком этого термина.

1. Посмотрите на каждый элемент в потоке.
2. Если термин существует в карте, увеличьте соответствующий счетчик.
3. В противном случае, если на карте меньше, чем k - 1 записей, добавьте термин в карту со счетчиком, равным единице.
4. Однако, если карта уже имеет k - 1 записей, уменьшите счетчик в каждой записи. Если какой-либо счетчик достигнет нуля во время этого процесса, удалите его с карты.

Обратите внимание, что вы можете обрабатывать бесконечное количество данных с фиксированным объемом памяти (только карта фиксированного размера). Требуемый объем памяти зависит только от интересующего порога, а размер потока не имеет значения.

Подсчет поисков

В этом контексте, возможно, вы буферизуете один час поисков и выполняете этот процесс на данных этого часа. Если вы можете сделать второй проход по журналу поиска за этот час, вы сможете получить точное количество вхождений лучших «кандидатов», идентифицированных на первом проходе.Или, может быть, это нормально - сделать один проход и сообщить обо всех кандидатах, зная, что любой элемент, который должен быть там, включен, а любые дополнения - это просто шум, который исчезнет в следующий час.

Любые кандидаты, которые действительно превышают порог интереса, сохраняются в виде сводки. Сохраните эти сводки за месяц, отбрасывая самые старые каждый час, и вы получите хорошее приближение к наиболее распространенным поисковым запросам.

Как насчет адаптации "алгоритма замены часовых страниц" (также известного как "второй шанс")? Я могу представить, что он будет работать очень хорошо, если поисковые запросы распределены равномерно (это означает, что большинство искомых терминов появляются регулярно, а не 5 миллионов раз подряд, а потом больше никогда).

Вот визуальное представление алгоритма:

Приблизительное мышление ...

Для топ-10 за все время

• Использование коллекции хешей, в которой хранится счетчик для каждого термина (очистить термины и т. Д.))
• Сортированный массив, который содержит текущую десятку лучших, термин / счетчик добавляется к этому массиву всякий раз, когда количество терминов становится равным или большим, чем наименьшее количество в массиве

Для ежемесячных топ-10 обновляется ежечасно:

• Использование массива, проиндексированного по количеству часов, прошедших с начала по модулю 744 (количество часов в течение месяца), записи массива состоят из коллекции хэшей, в которой сохраняется счетчик для каждого термина, встречающегося в течение этого часового интервала. Запись сбрасывается всякий раз, когда счетчик часового интервала изменяется
• . Статистические данные в массиве, индексированном на часовом интервале, должны собираться всякий раз, когда текущий счетчик часового интервала изменяется (максимум один раз в час), путем копирования и выравнивания содержимого этого массива, индексированного по часам-слотам

Errr ... имеет смысл? Я не думал об этом, как в реальной жизни

Ах да, забыл упомянуть, ежечасное «копирование / выравнивание», необходимое для ежемесячной статистики, может фактически повторно использовать тот же код, что и для 10 лучших за все время, приятный побочный эффект.

случай i)

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

O (1) поиск по списку первой десятки и max O (log (n)) вставка в хеш-таблицу (при условии, что коллизии управляются самобалансирующимся двоичным деревом).

случай ii) Вместо того, чтобы поддерживать огромную хеш-таблицу и небольшой список, мы поддерживаем хеш-таблицу и отсортированный список всех элементов. Каждый раз, когда выполняется поиск, этот термин увеличивается в хэш-таблице, и в отсортированном списке термин можно проверить, чтобы увидеть, должен ли он переключаться с термином после него. Для этого может хорошо работать самобалансирующееся двоичное дерево, так как нам также нужно иметь возможность быстро запрашивать его (подробнее об этом позже).

Кроме того, мы также ведем список «часов» в форме списка FIFO (очереди). Каждый элемент «час» будет содержать список всех поисков, выполненных за этот конкретный час. Так, например, наш список часов может выглядеть так:

Time: 0 hours
      -Search Terms:
          -free stuff: 56
          -funny pics: 321
          -stackoverflow: 1234
Time: 1 hour
      -Search Terms:
          -ebay: 12
          -funny pics: 1
          -stackoverflow: 522
          -BP sucks: 92

Затем каждый час: если в списке содержится не менее 720 часов (это количество часов в 30 дней), посмотрите на первый элемент в списке, и для каждого условия поиска уменьшите этот элемент в хеш-таблице на соответствующую величину. После этого удалите этот элемент первого часа из списка.

Итак, допустим, у нас 721 час, и мы готовы взглянуть на первый час в нашем списке (выше). Мы бы уменьшили количество бесплатных вещей в хеш-таблице на 56, смешных картинок - на 321 и т. Д., а затем полностью удалит час 0 из списка, поскольку нам больше не нужно будет смотреть на него снова.

Причина, по которой мы ведем отсортированный список всех терминов, позволяющих выполнять быстрые запросы, заключается в том, что каждый час после прохождения условий поиска 720 часов назад нам необходимо следить за тем, чтобы список первой десятки оставался отсортированным. Так, например, когда мы уменьшаем «свободный материал» в хеш-таблице на 56, мы проверяем его место в списке. Поскольку это самобалансирующееся двоичное дерево, все это может быть выполнено за время O (log (n)).

Редактировать: Жертвовать точностью ради места ...

Может быть полезно также реализовать большой список в первом, как и во втором. Тогда мы могли бы применить следующую оптимизацию пространства в обоих случаях: Запустить задание cron, чтобы удалить все, кроме верхних x элементов в списке. Это сократит потребность в пространстве (и, как следствие, ускорит запросы по списку). Конечно, это дало бы приблизительный результат, но это допустимо. x можно вычислить перед развертыванием приложения на основе доступной памяти и динамически скорректировать, если становится доступным больше памяти.

иногда лучший ответ - «Я не знаю».

Я нанесу более глубокий удар. Моим первым побуждением было бы передать результаты в Q. Процесс будет постоянно обрабатывать элементы, поступающие в Q. Процесс будет поддерживать карту

term -> count

каждый раз, когда обрабатывается Q-элемент, вы просто найдите поисковый запрос и увеличьте счетчик.

В то же время я бы вел список ссылок на 10 самых популярных записей на карте.

Для записи, которая была реализована в настоящее время, проверьте, больше ли ее счетчик, чем счетчик наименьшей записи в первой десятке (если ее еще нет в списке). Если это так, замените наименьшее записью.

Думаю, это сработает. Никакая операция не требует много времени. Вам нужно будет найти способ управлять размером карты подсчета. но этого должно быть достаточно для ответа на собеседовании.

Они не ждут решения, они хотят посмотреть, сможете ли вы подумать. Вам не нужно сразу же писать решение ....

Хранить количество поисковых запросов в гигантской хэш-таблице, где при каждом новом поиске определенный элемент увеличивается на единицу. Отслеживайте 20 или около того лучших поисковых терминов; когда элемент на 11-м месте увеличивается, проверьте, не нужно ли ему поменяться позициями с #10* (не обязательно сохранять 10 лучших отсортированных; все, о чем вы заботитесь, это провести различие между 10-м и 11-м).

*_{Аналогичные проверки нужно сделать, чтобы узнать, находится ли новый поисковый запрос на 11 месте, так что этот алгоритм распространяется и на другие поисковые запросы - поэтому я немного упрощаю.}

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

Вход

Вход - это бесконечный поток английских слов или фраз (мы называем их токенами).

Выход

1. Выведем N токенов, которые мы видели до сих пор. на данный момент (из всех токенов, которые мы видели!)
2. Вывод N лучших токенов в историческом окне, скажем, за последний день или прошлой недели.

Приложением этого исследования является поиск горячих тем или трендов в Twitter или Facebook. У нас есть краулер, который ползает по сайту, генерируя поток слов, который будет поступать в систему. Затем система выводит слова или фразы с максимальной частотой либо в целом, либо в исторической перспективе. Представьте, что за последние пару недель фраза "Чемпионат мира по футболу" много раз появлялась в Twitter. Так же как и "осьминог Пауль" :).

String into Integers

Система имеет целочисленный идентификатор для каждого слова. Хотя в Интернете существует почти бесконечное количество возможных слов, но после накопления большого набора слов вероятность нахождения новых слов становится все ниже и ниже. Мы уже нашли 4 миллиона различных слов и присвоили каждому уникальный идентификатор. Весь этот набор данных может быть загружен в память в виде хэш-таблицы, занимающей примерно 300 Мб памяти. (Мы реализовали нашу собственную хэш-таблицу. Реализация Java требует огромных затрат памяти)

Каждая фраза может быть идентифицирована как массив целых чисел.

Это важно, потому что сортировка и сравнение целых чисел происходит намного быстрее, чем строк.

Архивные данные

Система хранит архивные данные для каждого токена. В основном это пары (Token, Frequency). Однако таблица, в которой хранятся эти данные, будет настолько огромной, что нам придется разделить таблицу физически. Один раз схема разбиения основана на нграммах лексемы. Если лексема состоит из одного слова, то это 1грамма. Если лексема состоит из двух слов, то это 2грамма. И так далее. Приблизительно при 4граммах мы имеем 1 миллиард записей, а размер таблицы составляет около 60 ГБ.

Обработка входящих потоков

Система будет поглощать входящие предложения, пока память не будет полностью использована (да, нам нужен MemoryManager). После получения N предложений и хранения их в памяти, система делает паузу и начинает токенизировать каждое предложение на слова и фразы. Каждый токен (слово или фраза) подсчитывается.

Для высокочастотных лексем они всегда хранятся в памяти. Для менее частых лексем они сортируются на основе идентификаторов (помните, что мы переводим строку в массив целых чисел) и сериализуются в дисковый файл.

(Однако для вашей задачи, поскольку вы считаете только слова, то всю карту частотности слов можно поместить только в память. Тщательно спроектированная структура данных будет занимать всего 300 МБ памяти для 4 миллионов различных слов. Некоторый совет: используйте ASCII char для представления строк), и это гораздо более приемлемо.

Между тем, есть еще один процесс, который активируется, как только он находит любой дисковый файл, созданный системой, и начинает его объединение. Поскольку дисковый файл отсортирован, объединение будет происходить аналогично процессу сортировки слиянием. Здесь также необходимо позаботиться об определенной конструкции, поскольку мы хотим избежать слишком большого количества случайных обращений к диску. Идея заключается в том, чтобы избежать одновременного чтения (процесс слияния)/записи (вывод системы), и позволить процессу слияния читать с одного диска и записывать на другой диск. Это похоже на реализацию блокировки.

Конец дня

В конце дня система будет иметь много часто встречающихся лексем с частотой, хранящихся в памяти, и много других менее часто встречающихся лексем, хранящихся в нескольких дисковых файлах (и каждый файл сортируется).

Система сбрасывает карту в памяти в дисковый файл (сортирует его). Теперь проблема заключается в объединении набора отсортированных дисковых файлов. Используя аналогичный процесс, в конце мы получим один отсортированный дисковый файл.

Затем, последней задачей является объединение отсортированного дискового файла в архивную базу данных. В зависимости от размера архивной базы данных, алгоритм работает следующим образом, если она достаточно велика:

   for each record in sorted disk file
        update archive database by increasing frequency
        if rowcount == 0 then put the record into a list
   end for

   for each record in the list of having rowcount == 0
        insert into archive database
   end for

Интуиция подсказывает, что через некоторое время количество вставок будет становиться все меньше и меньше. Все больше и больше операций будет приходиться только на обновление. И это обновление не будет наказываться индексом.

Надеюсь, это объяснение поможет. :)