python - Borda的位置排名

Question

我有按分数降序排列的元素树列表。我需要做的是使用 Borda’s positional ranking使用每个列表中元素的顺序排列信息组合排名列表。给定列表 t1、t2、t3 ... tk，对于每个候选 c 和列表 ti，得分 B ti (c) 是排名候选的数量在 ti 中低于 c。所以总的 Borda 分数是 B(c) = ∑ B ti (c)然后根据 Borda 分数降序对候选人进行排序。

我绑定(bind)了它，但它没有提供所需的输出:

for i in list1, list2, list3:
   borda = (((len(list1)-1) - list1.index(i)) + ((len(list2)-1) - list2.index(i)) + ((len(list3)-1) - list3.index(i)))
   print borda

有人可以帮我实现上面的功能吗？

Answer 1

调用 index(i) 所花费的时间与列表大小成正比，并且因为您必须为每个元素调用它，所以最终会花费 O(N^2) 时间，其中 N 是列表大小。在您知道索引的情况下一次迭代一个列表并将该部分分数添加到字典中的分数累加器中会更好。

def borda_sort(lists):
    scores = {}
    for l in lists:
        for idx, elem in enumerate(reversed(l)):
            if not elem in scores:
                scores[elem] = 0
            scores[elem] += idx
    return sorted(scores.keys(), key=lambda elem: scores[elem], reverse=True)

lists = [ ['a', 'c'], ['b', 'd', 'a'], ['b', 'a', 'c', 'd'] ]
print borda_sort(lists)
# ['b', 'a', 'c', 'd']

这里唯一棘手的部分是反向扫描列表；这确保如果一个元素根本不在列表之一中，则该列表的分数增加 0。

与此处的其他建议比较:

import itertools
import random

def borda_simple_sort(lists):
    candidates = set(itertools.chain(*lists))
    return sorted([sum([len(l) - l.index(c) - 1 for l in lists if c in l], 0) for c in candidates], reverse=True)
    # returns scores - a bit more work needed to return a list

# make 10 random lists of size 10000
lists = [ random.sample(range(10000), 10000) for x in range(10) ] 
%timeit borda_sort(lists)
10 loops, best of 3: 40.9 ms per loop

%timeit borda_simple_sort(lists)
1 loops, best of 3: 30.8 s per loop

这不是打字错误 :) 40 毫秒秒对比 30 秒，加速了 750 倍。在这种情况下，快速算法并没有明显更难阅读，甚至可能更容易阅读，它只是依赖于适当的辅助数据结构，并以正确的顺序遍历数据。