Borda的位置排名

Question

我有三个按分数降序排列的元素列表。我需要使用Borda's positional ranking来结合排名列表，利用每个列表中元素的序号排名信息。给定列表t1，t2，t3...tk，对于每个候选人c和列表ti，得分Bti(c)是在ti中排在c下面的候选人数。因此，总Borda得分为B(c)= ∑Bti(c)。然后按Borda得分降序排列候选人。

我尝试过了，但没有得到需要的输出：

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

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

- sss

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倍。在这种情况下，快速算法并不比较难读，甚至可能更容易读懂，它只是依赖于适当的辅助数据结构，并按正确的顺序处理数据。

- Alex I

---

当我调用这段代码时，它会给我一个错误：TypeError: unhashable type: 'list'。 - sss

@user3573552：你是怎么运行它的？Python 版本？完整代码？ - Alex I

@ Alex，我看到这个关于Python的问题：如何使用列表作为字典的键。 - sss

Answer 2

这可能有效：

sorted([sum([len(l) - l.index(c) - 1 for l in [list1, list2, list3] if c in l], 0) for c in [candidate1, candidate2, candidate3]], reverse=True)

请注意，由于分数被重新排序，您将无法跟踪每个分数所属的候选人：

>>> list1 = ['a', 'c']
>>> list2 = ['b', 'd', 'a']
>>> list3 = ['b', 'a', 'c', 'd']
>>> candidates = ['a', 'b', 'c', 'd']
>>> sorted([sum([len(l) - l.index(c) - 1 for l in [list1, list2, list3] if c in l], 0) for c in candidates], reverse=True)
[5, 3, 1, 1]

在这种情况下，列表的第一个元素（获胜者）是“b”，而候选人列表中的第二个元素。

- Tomás Mena