具体的业务场景是:需要使用类似 hacker news 的投票算法进行排序。
比如现在有个 aticle 模型,模型有个字段 P 代表喜欢某篇文章的人数。 T 表示距离发帖已经过去的时间(单位为小时)
我想按照 score 的值对列表进行排序,请问该如何操作?
我在网上找了好几天的资料,目前还没头绪。
刚转型的新手,接触 Rails 没多久。跪求大侠指点一二,感激不尽。 如果大侠愿意的话,我可以用淘点点请您喝顿下午茶。
已有解决方案,请见 #31 楼
超过 1 行切 JJ
Article.all.sort_by { |article| (article.p - 1) / ((Time.now - article.created_at) / 1.hour + 2) ** article.g }
给 aticle 加个 score 字段,然后开一个 worker 去给每一个 aticle 跑出这个值,存进数据库。 然后前台直接 order 这个字段。 这个方法会因为你这个 worker 的周期导致一定的延迟,不是很实时。 如果想比较快,比较实时的的得到结果。 据我所知淘宝的热门商品是用一个 hadoop 集群在后台提供支持,不过思路和上面的的方法其实差不多,都是异步的。
Article.connection.select_all('SELECT id, p, g, created_at FROM articles').to_a.sort_by { |article| (article['p'] - 1) / ((Time.now - article['created_at']) / 1.hour + 2) ** article['g'] }.each_slice(per_page).each_with_index.map { |articles, index| cache("page_#{index}") { articles['id'] } }
增加分页和缓存也不能超过 1 行代码,开发成本 10 分钟,理论估算 8 GB 内存可以处理 1000 万条记录,应该可以支撑到楼主融资请大牛吧
Acticle.select("((p-1) / POWER((TIMESTAMPDIFF(HOUR,created_at,'2014-03-02 22:32')+2), g)) as score").order("score desc")
#13 楼 @small_fish__ 标准 SQL 的函数是很少,难以实现复杂的计算,比如楼上的方法 Sqlite 就不一定支持。Rails 的哲学是用 ActiveModel 接管数据库,数据库只是底层存储,程序逻辑由 Ruby 完成。Thinking in Rails。
我们的应用有类似需求,不同的是用牛顿冷却算法,比你这个稍微复杂一点点,我们加了 2 个字段 initial_score 和 current_score 在内容创建地时候算一个原始分(根据用户等级,内容质量等),然后用 crontab 每天执行一次 sql: update xxx set current_score = initial_score * exp(timestampdiff(day, created_at, now()) * -0.12) 需要用到排序的地方就按 current_score 来排序就可以了。
hacker news 的算法因为不需要保留原始分,你只需要加一个字段,用 crontab 每小时执行一次 sql 计算既可。
缓存当然会跟实时数据不一致,以上的所有方法都会。清缓存的策略也有很多种,看需求了。
要看问题是什么?如果楼主的问题是写出高效代码,我那行代码不好。但如果楼主的问题是如何快速上线运营融资上市,我觉得我是在解决问题。
基于用户投票的排名算法(二):Reddit http://www.ruanyifeng.com/blog/2012/03/ranking_algorithm_reddit.html
Hack News:
Reddit:
从数学角度两者相差不大,但是从实际开发角度,第二种(reddit)模型要远远优于第一种模型。
第一种算法的分数是一个动态值,如果想排序有两种途径:
select * from problems order by f(current_time, othor_value) desc limit 20;
很显然,上面的排序无法利用索引。
还有一种办法是每隔一段时间去计算一次所有条目的 score 值,这样是可以利用索引排序的,但是排名不够平滑。
Reddit 的算法就完美解决了这个问题,无论什么时间,score 都是一个定植,只需要在相关因素有变动的时候去更新一下对应的 score 值。既可以利用索引,排序又平滑,并且简单。
select * from problems order by rank desc limit 20;
最后经过权衡准备参考 @hooopo 的建议改用 reddit 的算法。同时,也非常感谢@swordray @bydmm @kaka @Rei @quakewang 等大侠的回复,颇有收益。如果几位需要,欢迎在 Twitter 私信我收件地址和手机号,非常乐意请几位喝下午茶。
另,如果有朋友仍期望考虑在 rails 中实现 hacker news 算法,可参考: http://blog.chh.tw/posts/hacker-news-de-tui-wen-xi-tong-yan-suan-fa-yong-ruby-shi-zuo/ https://gist.github.com/ChiChou/8862382
Mysql 本身就有这中功能,比如一个表有 2 个 int 型属性:a,b 下面 sql:select a, b ,a + b from mytable order by a + b desc