选择数据结构,根据用户评级从TOP项目中排序TOP 10项目

Question

假设你正在运行一个像IMDb/Netflix这样的电影数据库网站,用户可以评价1-10星级的每部电影.当用户评价电影时,我在请求中得到id(长)并且评分为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调用时,我更新电影评级以及更新前10部电影并反映在网页上,用户将始终看到最新的前10部电影.我在Web服务器上有很多空间,我可以将所有电影对象保存在内存中.这里的挑战是

1)通过id查找电影.
2)更新电影评级.
3)在已分类的电影集中选择此电影的新位置(按评级排序),如果其新位置位于前10位,则在网页上显示.


所有这些操作都应在最佳的最佳时间内完成.

这不是一个家庭作业,而是一般的编程和数据结构问题.

Answer 1

我个人会为此使用关系数据库.

1. 使用ID作为主键创建具有ID和名称字段的Movie表(群集)
2. 制作一个带有ID,UserId,MovieId和Rating字段的评级表.使用明显的外键引用.
3. 使用ORM根据这些表中的查询构造Movie对象.

但我想如果你纯粹从数据结构和算法的角度来看它,我首先要改变你的Movie类,使其具有一个运行的ratingSum字段,这样你就可以动态计算平均值.然后我创建一个最多可以输出十个对象的列表.无论何时添加评级,我都会检查该电影的新平均值是否高于"前10名"列表中最少的项目.如果是,那么我将它插入该列表中的适当位置,并将最后一项放在列表底部.显然,如果它已经在列表中,那么您只需要担心重新排序现有项而不是删除一项.这是一种简单的方法,每次更新时只需要很小的成本.

(链接列表可能会为您的"前10名"列表提供最佳性能,但只有10个项目最多只能每周重新排列几次,您可能不会注意到差异.)

显然,你必须拥有快速查找时间的集合中的所有电影(如Hashtable)才能通过ID找到它们.当然,有了无数项目,你将很难将所有这些都融入到记忆中.因此关系数据库.