查找列表中添加分数排名平均值的有效方法。可能是更有效的排序方式或数学方式？

Question

我正在尝试解决一个问题，我需要找到添加到列表中的一堆分数的排名平均值。

例如，如果输入是： 5个 100 200 150 170 50

那么程序应该输出2.2

还有5个分数要加

输入 100 时排名第 1

当输入 200 时，它排名第 1

输入150后排名第2

输入170后排名第2

当输入 50 时，它排名第 5

那么 (1 + 1 + 2 + 2 + 5) = 2.2

现在我有一个完美的解决方案，但它对于大型测试用例来说不够快。

games = input()
lst = []
acc = 0.0
counter = 0.0
for i in range(0, games):
    number = input()
    lst.append(number)
    lstt = sorted(lst)
    lsttt = lstt[::-1]
    acc += (lsttt.index(number) + 1)
print acc / games

现在我正在使用默认的 python 排序函数，我认为使用不同类型的排序可以使它更快。这是问题所在还是有更好的数学方法？

Answer 1

您可以使用 bisect 模块在 O(log(n)) 时间内找到插入点：

import bisect

games = input()
lst = []
acc = 0.0
counter = 0.0
for i in range(games):
    number = input()
    pos = bisect.bisect(lst, number)
    lst.insert(pos, number)  # O(log(n)) for the search, but O(n) for the insertion
    acc += len(lst) - pos
print acc / games

这是对您算法的改进，因为它是 O(n^2) 而不是 O((n^2)*log(n))。如果仍然太慢，您可能需要考虑使用树。

Answer 2

你应该使用 SortedList package here, as it provides O(log N) insertion. So, with that package overall complexity is going to be O(NlogN). Read its implementation details here: http://www.grantjenks.com/docs/sortedcontainers/implementation.html

from sortedcontainers import SortedList

def solve_sorted_list(numbers):
    lst = SortedList()
    acc = 0.0
    for n in numbers:
        pos = lst.bisect(n)
        lst.add(n)
        acc += len(lst) - pos
    return acc / len(numbers)

print solve_sorted_list([100, 200, 150, 170, 50])
#2.2

时序比较：

>>> lst = range(10**5, -1, -1)
>>> %timeit solve_bisect(lst)   #Using NPE's solution
1 loops, best of 3: 1.87 s per loop
>>> %timeit solve_sorted_list(lst)
1 loops, best of 3: 221 ms per loop
>>> lst = range(10**6, -1, -1)
>>> %timeit solve_sorted_list(lst)
1 loops, best of 3: 2.31 s per loop
>>> %timeit solve_bisect(lst)
1 loops, best of 3: 3min 52s per loop

查找列表中添加分数排名平均值的有效方法。可能是更有效的排序方式或数学方式？

Efficient way to find the average of the rank of added scores to a list. Possibly a more efficient way of sorting or a math way?

python

sorting

math

performance