python - Borda’s positional ranking -

i have tree lists of elements sorted descending scores. need use borda’s positional ranking combine ranked lists using information of ordinal ranks of elements in each list.given lists t1, t2, t3 ... tk, each candidate c , list ti, score b ti (c) number of candidates ranked below c in ti. total borda score b(c) = ∑ b ti (c) candidates sorted descending borda scores.

i tied that, not give output needed:

for 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 

can me implement above function?

calling index(i) takes time proportionate list size, , because have call every element, ends taking o(n^2) time n list size. better iterate 1 list @ time know index , add part of score score accumulator in dict.

def borda_sort(lists):     scores = {}     l in lists:         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'] 

the tricky part here scanning lists in reverse; makes sure if element not in 1 of lists @ all, score increases 0 list.

compare other suggestion here:

import itertools import random  def borda_simple_sort(lists):     candidates = set(itertools.chain(*lists))     return sorted([sum([len(l) - l.index(c) - 1 l in lists if c in l], 0) c in candidates], reverse=true)     # returns scores - bit more work needed return list  # make 10 random lists of size 10000 lists = [ random.sample(range(10000), 10000) 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 

that's not typo :) 40 milliseconds vs 30 seconds, 750x speedup. fast algorithm not more difficult read in case, , may easier read, relies on appropriate auxiliary data structure, , going through data in right order.