做有效加权排名的算法？

Question

我需要一个算法来做Twitter帖子的快速加权排名。

每个帖子都有一些排名分数(如年龄、作者追随者数量、关键词提及次数等)。我正在寻找算法，可以快速找到前N个推文，给出每个排名得分的权重。

现在，用例是这些权重将改变，并且每次权重改变时重新计算每个tweet的排名分数是非常昂贵的。

我将有权访问推文的排序列表，每个排名分数一个。因此，我正在寻找一种算法来有效地搜索这些列表，以找到我的前N。

Answer 1

通知:提供这个答案是因为相信知识总是好的(即使它可能被用于邪恶的目的)。如果您能够获得和存储/跟踪诸如年龄、作者关注者计数、关键词提及等信息，而没有确保参与者完全了解他们的数据将如何使用，也没有获得每个参与者的明确同意(并且没有“选择加入，可以随时选择退出”)，那么您就侵犯了人们的隐私，您的严重不道德的恶意软件理应破产。多家大公司都是邪恶的，这已经够糟糕的了，而不会让事情变得更糟。

假设有一个像score = a_rank * a_weight + b_rank * b_weight + c_rank * c_weight这样的公式。

这可以被分成几个部分，比如：

 a_score = a_rank * a_weight
 b_score = b_rank * b_weight
 c_score = c_rank * c_weight
 score = a_score + b_score + c_score

如果您知道存储桶的范围，则可以将条目排序到"a_rank a_rank“中。例如，如果您有100个存储桶，并且"a_rank“可以是从"a_rank_min”到“a_rank_max”的值；则"bucket_number = (a_rank - a_rank_min) * 100 / (a_rank_max - a_rank_min)“。

从这里可以看出，特定"a_rank存储桶“中的所有条目都必须具有特定范围内的"a_score”；您可以使用"min_a_score_for_bucket = (bucketNumber * (a_rank_max - a_rank_min) / 100 + a_rank_min) * a_weight“和"max_a_score_for_bucket = ( (bucketNumber+1) * (a_rank_max - a_rank_min) / 100 + a_rank_min) * a_weight - 1”之类的公式，单独从"bucket_number“计算存储桶中所有条目的最小和最大可能的"a_score”。

下一步是建立“到目前为止得分最高的10个条目”。为此，从最高的"a_rank存储桶/秒“中选择前10个条目，并完全计算它们的分数。

一旦完成(您知道“目前为止的第10高分”)，您就可以为每个存储桶计算一个过滤器。如果假设存储桶中的所有条目都具有最大可能的a_rank (仅由存储桶编号确定)和最大可能的c_rank (由所有c_rank值的可能范围确定)，则可以计算条目得分高于“目前为止的第10高得分”所需的b_rank的最小值；同样，如果假设存储桶中的所有条目都具有最大可能的a_rank和最大可能的b_rank，则可以计算所需的c_rank的最小值。然后，可以使用"minimum needed b_rank“和"minimum needed c_rank”跳过那些不可能超过“目前为止的第十高分”的条目，而不计算这些条目的分数。

当然，每次你发现一个条目的得分高于“第10高分”，你将得到一个新的“第10高分”，并且必须重新计算存储桶的“最低所需b_rank”和“最低所需c_rank”。理想情况下，您将以“最高a_rank存储桶优先”的顺序查看存储桶，因此将只计算当前存储桶的“最小所需b_rank”和“最小所需c_rank”

在接近开始时(当您查看具有最高a_rank值的存储桶时)，它可能不会过滤掉许多条目，甚至可能会使性能变差(由于重新计算"minimum needed b_rank“和"minimum needed c_rank”值的开销)。接近末尾时(当您查看具有最低a_rank值的存储桶时)，您可以跳过整个存储桶，而无需查看其中的任何条目。

请注意：

• 所有的权重都可以改变，而不需要改变任何桶；但如果"a_rank“对分数的影响最大，那么对性能会更好。

• "a_rank“的取值范围不应改变(如果改变，则必须重新构建存储桶)；但"b_rank”和"c_rank“的取值范围可以是可变的(每次创建新条目时都会更新)

• 在查找得分最高的10个条目时，按照“最高a_rank优先”的顺序对每个存储桶进行排序(然后使用“最高b_rank优先”作为平局决定符，等等)将有助于提高性能；但在添加条目时，这也会增加开销。出于这个原因，在大多数情况下，我可能根本不会费心对存储桶中的内容进行排序。

• 如果你能为“a_rank”的每个可能值都有一个存储桶就好了；因为这几乎提供了排序的所有好处，而没有任何排序的开销。如果不能为"a_rank“的每个可能值设置一个存储桶，那么增加存储桶的数量可以帮助performance.

理论上是

• ；可以有多层"a_rank“(例如，包含"b_rank bucket”的“b_rank bucket”)。这将显著增加复杂性，并增加内存消耗；但(特别是在不进行排序的情况下)可能会显著提高性能(并可能使性能变得更差)。