Rails 一个算法问题:保证用户总是看到随机新的东西,并且效率还不错?

linjunhalida · 2014年06月04日 · 最后由 wildwood 回复于 2014年06月04日 · 2985 次阅读

首先网站有一堆文章 Post,对于一个 User,我希望可以随机抽一篇文章给他看, 每次抽的文章必须不一样,并且不重复。文章会不断地增加。每个文章有一个 ID,ID 是顺序产生的。

可以用直接简单的解法:记录一个 Visited: user_id, post_id,但是这样就会出现一个很大的表, 因为 user 是 10000+,post 数量级数是 1000+ 的,每次获取文章的复杂度就比较高了。

请问是否有一个算法,可以让获取文章的复杂度保持在常数级?谢谢!

就用一个表记录一下取过的文章,因为有外键和主键在,查询效率完全不用担心:

query = "id not in (select id from visited where user_id = 1)"
Post.where(querey).offset(rand(Post.where(query).count)).limit(1)

{ user_id: [post_id_1, post_id_2] }(DB 里可以用 Array 保存?) 每次都 random 这个 array,取走一个,取走后把这个 post_id 从 array 里删除,那么从取的角度来说就是 O(n),而且不会重复。 如果日后有文章增加,就需要为每个用户记录的 array 里加入这个 post_id,这里可能操作数据比较巨大,因为每个用户都要加入这个 post_id。 如果以 vistited 作标记的话,每次都要比对 unvistited 的,这样效率就没那么高

貎似我暂时想到这个方案,不知如何……

#1 楼 @quakewang 我觉得楼主的意思是因为这样会产生千万级的数据记录

4 楼 已删除

#3 楼 @imlcl visited 表只有 2 个复合主键,千万级数据也只是几十 M 大小的数据文件

#2 楼 @imlcl 觉得是不是 random 一次就可以了?

@imlcl 的方法适用 mongo 或 redis,@quakewang 的方法适合 mysql

最近看《数学之美》的时候,看到搜索引擎原理,也是用布尔代数去表示某个词是否在某个网站出现过,就是 010101...... 我觉得也可以将 某用户 是否 读过某编文章 弄成一串二进制串,例如 0101 表示 用户 没有读过第 1,3 文章,读过了第 2,4 的文章。

而增加文章的时候,将二进制串左移(实质就是后面补 0)就 ok 了。

#9 楼 @special 学习了,不过这个在搜索时会不会比较麻烦?得拆分识别二进制串,这样会不会反而降低效率了?

@vianvio

识别单从 Ruby 上来说不难吧,很轻易就可以从二进制串中取出 随机抽出 的文章用户有没有读过。 不过效率来说上面这种多了二进制 -> 字符串的操作多少浪费了空间和时间。

irb(main):005:0> 4.to_s(2)
=> "100"

irb(main):007:0> 4.to_s(2)[0]
=> "1"

#9 楼 @special 增加文章左移,实现起来坑应该不少,pg 的 hstore 或数组比较现实,真要用位的话也应该要用变长的数据类型。 不知道数据库的二进制数据类型用起来会怎么样,如 pg 的 bytea。在保存的时候,直接计算并保存到某个字节的某个位,中间填 0,但这个还要有一个文章表的 id 到序号的一个转换。当然可以直接把 id 作为序号,或者减一个 min(id)。

如果用普通的 string 类型,一个字段 256 字节,保存 2048 篇文章状态,文章多的时候加个字段(要自动做 migrate),字段名统一,这样好象也行。text 好象也可以吧。

@5swords 也是.. 用 Ruby 也是为了爽,折腾到位去确实不太 Happy。 😄

想了一下,用朴素的双主键表方法,一般情况下数据量万以下,in 操作复杂度应该是 n 级别的。不过不需要用真的 random,取搜索到的前 10 个 random 就好,那么复杂度会减低到 log(n),问题不大。

我换一个表述方式,是否有一个 random 算法,可以支持(1..n)集合中的不重复随机,并且还支持集合数据插入的?就我所知,不支持插入的随机算法是有的。

为什么一定要随机的呢?顺序的不满足你的要求么?

同时满足读写效率的随机有吗

需要 登录 后方可回复, 如果你还没有账号请 注册新账号