android - 手机app，根据算法算出某个权重值进行排序，如何提高排序性能？

Question

如绝大多数的新闻客户端和某些社区（比较著名的如reddit），都是根据某个算法算出一个权重值，再根据这个权重值进行排序（参考：http://www.ruanyifeng.com/blog/2012/03/ranking_algorithm_reddit.html）

手机app的场景下，应该怎么样去综合提高这个排序性能呢？

• 假如单纯在数据库里面进行排序，由于order by的字段是通过算法生成，数据量一大必然低效。现在产品用的mysql还不支持函数索引
• 假如在先抽出数据，再在程序里进行排序，数据量一大，也会占用服务器不少的内存吧？好像也不是很好的办法

请有经验人士提供一些思路。

Answer 1

这问题放在 Android 的节点下，你是要在 Android 下实现权重计算？

要是在服务器的话，赞同 @zys 的方案，另外，要降低计算数量，私有以下愚见：

1. 给要计算的数据加上一个 updated_at 和 calculated_at 字段，分别表示数据最新的更新时间和最后一次用排序算法计算权重值的时间。当有新的用户投票，更新数据的 updated_at 字段。定时任务计算权重后，更新数据的 calculated_at 字段。

2. 权重计算算法里对 updated_at 和 calculated_at 作比较，当 calculated_at > updated_at 的时候，没必要重复重新计算权重值。

用这种简单的算法，可以有效的去掉很大部分已经没更新的数据，另外，假如老的数据有更新，也能列入权重的计算范围。

Answer 2

对于社区和新闻客户端来说，你不可能排序的时候带上上个月的数据，这样来讲，也没有多少。

Answer 3

我以前做过类似的事是这样处理的，将耗时的计算放在每天凌晨用定时任务去做，然后结果存在order字段或者一个排序表里，读数据的时候order by或者关联下表查询就可以了。

Answer 4

可以单独放一个表出来, 当文章可能影响权重的内容改变时, 直接更新表里的值, 应该可以承受相当大的数量了. 即便以后再增长, 可以只对一段时间内的文章进行排序, 应该不会有问题.

Answer 5

提升一个高度来回答这个问题，或许对你的思路会有帮助。
提升性能的方式无非就几种常见的思路，顺着想一下一般都会有自己的结论。

1. 提升算法的效率：权重的计算公式尽量不要有太高的复杂度可以提升运算速度。
2. 用空间换时间：权重的计算结果放到一个临时字段去记录，这样排序的时候就不用重复计算权重。
3. 避免不必要的运算：去除对结果影响不大的运算，比如一个月之前的数据不纳入排序，减少运算的数据规模。
4. 用近似值代表准确值：不要实时的去计算权重，定时去刷新权重可以有效减少运算次数。

Answer 6

楼上总结很到位。