Блог

Допустим, вы запускаете веб-сайт базы данных фильмов, такой как IMDb / Netflix, и пользователи оценивают каждый фильм от 1 до 10 звезд. Когда пользователь оценивает фильм, я получаю идентификатор (длинный) и рейтинг от 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.
}
  

Мой вопрос в том, какие структуры данных я могу выбрать для хранения огромных данных о фильмах в памяти, чтобы при каждом вызове обновления я обновлял рейтинг фильма, а также обновлял Top 10 movie и отражал на веб-странице, и пользователи всегда будут видеть последние 10 лучших фильмов. У меня много места на веб-сервере, и я могу хранить все объекты movies в памяти. Проблемы здесь заключаются в

1) Найдите фильм по идентификатору.
2) обновите рейтинг фильма.
3) выберите новое местоположение этого фильма в отсортированной коллекции фильмов (отсортированных по рейтингам), и если его новая позиция находится в первой топ-10, покажите ее на веб-странице.

Все эти операции должны выполняться в наилучшее оптимальное время.

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

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

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

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

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

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

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

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

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

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

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

3. (На данный момент элемент теперь находится в очереди приоритетов в нужном месте, а массив top ten movies содержит девять элементов)

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

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

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

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

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

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

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