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

樓上總結很到位。