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

Question

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

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

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

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

Answer 1

This question is placed under the Android node. Do you want to implement weight calculation under Android?

If it is on the server, I agree with @zys's plan. In addition, to reduce the number of calculations, I have the following humble opinion:

1. Add an updated_at and calculated_at fields to the data to be calculated, which respectively represent the latest update time of the data and the last time the weight value was calculated using the sorting algorithm. time . When a new user votes, update the updated_at field of the data. After the scheduled task calculates the weight, update the calculated_at field of the data.

2. In the weight calculation algorithm, updated_at and calculated_at are compared. When calculated_at > updated_at, does not need to be repeated. Calculate the weight value.

Using this simple algorithm, a large part of the data that has not been updated can be effectively removed. In addition, if the old data has been updated, it can also be included in the weight calculation range.

Answer 2

For community and news clients, you cannot bring last month’s data when sorting, so there isn’t much.

Answer 3

I have done similar things before and handled it like this. I put the time-consuming calculations in the early morning of every day and used scheduled tasks to do it. Then the results were stored in the order field or a sorting table. When reading the data, order by or related Just query the table.

Answer 4

You can put a separate table. When the content of the article that may affect the weight changes, you can directly update the values ​​​​in the table. It should be able to withstand a considerable number. Even if it grows in the future, you can only do this for articles within a period of time. Sorting, there should be no problem.

Answer 5

To answer this question at a higher level, it may be helpful to your thinking.
The ways to improve performance are nothing more than a few common ideas. If you think about it, you will usually come to your own conclusion.

1. 提升算法的效率: The weight calculation formula should not be too complex to improve the calculation speed.
2. 用空间换时间: The weight calculation result is recorded in a temporary field, so that there is no need to repeatedly calculate the weight during sorting.
3. 避免不必要的运算: Remove operations that have little impact on the results. For example, data from one month ago are not included in the sorting to reduce the data size of the operation.
4. 用近似值代表准确值: Do not calculate weights in real time. Refreshing weights regularly can effectively reduce the number of operations.

Answer 6

The summary above is very good.