Непрерывный мониторинг и обновление популярности предметов

Question

Предположим, у нас есть 1000 предметов и место, где вы можете показать все десять из этих предметов за раз посетителю. Мы можем фиксировать скорость клика и элементы, которые показаны вместе.

1. Как мы можем оптимально получить самые популярные предметы (скажем 10) из этих?
2. Как мы можем постоянно обновлять популярность и показывать оптимальные пункты 10?

Редактировать: Я ищу различные подходы вместо реализаций.

Answer 1

Само реализовано:

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

Чтобы сохранить упорядоченный массив:

Это может поддерживаться с помощью самобалансирующегося бинарного дерева с лог (N) сложностью, где N представляет общее количество элементов

http://www.sitepoint.com/data-structures-2/

В качестве практического варианта :

база данных может использоваться для хранения товаров, а индекс B-дерева может быть добавлен в колонку популярности; СУБД будет нуждаться в оптимизации здесь. https://en.wikipedia.org/wiki/Database_index

Answer 2

Если вы действительно хотите сжать это, на ваш случай есть немой/простой подход (показать сверху 1%).

Эта оптимизация может произойти, потому что в среднем только 1 из 100 изменений популярности выбивает один из лучших 1%. (Предполагает случайное распределение обновлений. Конечно, с более типичным распределением степенным, это может произойти гораздо чаще.)

1. Сортировать весь первоначальный сбор,

   • Храните только 10 лучших в любой сортированной структуре данных (например, BST)
   • Храните оценку популярности № 10 (например, minVisiblePopularity)

2. затем с каждой последующей изменением популярности в коллекции, сравните с minVisiblePopularity.

   • Если новая популярность падает выше minVisiblePopularity, обновить структуру и minVisiblePopularity топ-10 соответственно.
   • (Или, если старая популярность была больше, но новая популярность меньше - например, бывший топ-10 предметов, получающих нокаут).

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