Выбор структур данных для сортировки ТОП-10 товаров из миллиарда по рейтингу пользователей.

Question

Допустим, у вас есть веб-сайт базы данных фильмов, такой как IMDb / Netflix, и пользователи оценивают каждый фильм от 1 до 10 звезд.Когда пользователь оценивает фильм, я получаю id (long) и рейтинг от 1 до 10 в запросе.Класс Movie выглядит следующим образом.

class Movie
{
    long id;
    String name;
    double avgRating;     //Avg Rating of this movie
    long numberOfRatings; //how many times this movie was rated.
}

public void updateRating(long movieId, int rating)
{

    //code to update movie rating and update top 10 movie to show on page.
}

Мой вопрос состоит в том, какие структуры данных я могу выбрать для хранения огромных данных фильмов в памяти, чтобы при каждом вызове updateRating я обновлял рейтинг фильма, а также обновлял фильм Top 10и отражать на веб-странице, и пользователи всегда будут видеть последние 10 лучших фильмов.У меня много места на веб-сервере, и я могу хранить все объекты фильмов в памяти.Проблемы здесь1) Посмотрите фильм по id.2) обновить рейтинг фильма.3) выбрать новое местоположение этого фильма в отсортированной коллекции фильмов (отсортированных по рейтингу) и, если его новая позиция находится в первой десятке, показать его на веб-странице.Все эти операции должны быть выполнены в оптимальное время.

это не домашняя работа, а вопрос общего программирования и структуры данных.

Answer 1

Я бы лично использовал для этого реляционную базу данных.

1. Создайте таблицу Movie с идентификатором и полем Name, используя идентификатор в качестве первичного ключа (кластеризованного)
2. Составьте таблицу рейтинга с полями ID, UserId, MovieId и Rating.Используйте очевидные ссылки на внешние ключи.
3. Используйте ORM для создания объекта Movie на основе запроса к этим таблицам.

Но я полагаю, что если вы смотрите на него исключительно изС точки зрения структур данных и алгоритмов, я бы начал с того, что изменил ваш класс Movie на наличие действующего поля ratingSum, чтобы вы могли вычислять среднее значение на лету.Тогда я бы создал список, который максимально на десять объектов.Каждый раз, когда добавляется рейтинг, я проверяю, является ли новое среднее значение для этого фильма выше, чем наименьшее количество элементов в списке «10 лучших».Если это так, то я бы вставил его в соответствующее место в этом списке и уронил последний элемент из нижней части списка.Очевидно, что если он уже есть в списке, вам нужно беспокоиться только о переупорядочении существующих элементов, а не об их удалении.Это простой подход, который будет стоить только крошечную цену при каждом обновлении рейтингов.

(Связанный список, вероятно, даст вам наилучшую производительность для вашего «топ-10» списка, но только с 10 элементами, которые получают тольконе более, чем несколько раз в неделю, вы, вероятно, не заметите разницу.)

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

Answer 2

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

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

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

1. Если фильм входит в десятку лучших, удалите его из этого массива и перетасуйте элементы после него на одно место. Затем вставьте его в очередь приоритетов с новым рейтингом.

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

3. (В этот момент элемент находится в очереди с приоритетами в нужном месте, и в массиве из десяти лучших фильмов содержится девять элементов)

4. Используйте функцию dequeue-max в очереди с приоритетами, чтобы извлечь наиболее популярный фильм из очереди с приоритетами, а затем с помощью простой сортировки вставок вставить его в массив из десяти самых популярных фильмов.

Общая временная сложность для этого подхода (при условии, что вы используете двоичную или биномиальную кучу) составляет O (k ² + lg n), где k - количество элементов в списке первой десятки и n - общее количество фильмов. В среднем, он выполняется за O (LG N) времени, так как есть вероятность, что вам не нужно обновлять список первой десятки. В любом случае, поскольку k мало (десять), я бы предположил, что это будет работать очень быстро. Более того, он дает вам O (1) поиск любого из лучших k фильмов, что, я ожидаю, будет довольно распространенной операцией.

Надеюсь, это поможет!

Answer 3

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

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

Answer 4

Для первоначального заполнения списка 10 лучших вам нужно будет пропустить все данные.Однако после этого вы можете сохранить рейтинг фильма # 10 и каждый раз, когда голосуете, обновлять топ-10, только если рейтинг обновленного фильма больше или равен рейтингу # 10.Значение, меньшее среднего, не будет влиять на верхние 10.

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