我有按降序分数排序的元素的树列表。我需要做的是使用Borda’s positional ranking来组合排名列表,使用每个列表中元素的顺序排列信息。tk,对于每个候选c和列表ti,分数b ti(c)是ti中排名低于c的候选数目。
所以borda总分是b(c)=∑b ti(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
有人能帮我实现上面的功能吗?
最佳答案
调用索引(i)需要与列表大小成比例的时间,并且由于必须为每个元素调用索引,因此它最终需要o(n^2)时间,其中n是列表大小。最好一次迭代一个列表,在这个列表中您知道索引,并将该部分分数添加到dict中的分数累加器中。
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倍加速在这种情况下,快速算法不难理解,甚至更容易读取,它只依赖于适当的辅助数据结构,并以正确的顺序通过数据。
关于python - Borda的排名,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/30258453/