python - 如何改善按排名搜索值(value)？

Question

我有一个包裹值(value):

{'1': 2, '2': 1,'6': 3, '3': 5}

这意味着:

{'1', '1', '2','6', '6', '6', '3', '3', '3', '3'}

我这样做:

1. 按键排序，所以它变成:{'1': 2, '2': 1, '3': 5,'6': 3}

2. 获取第 N 个值。所以如果我想要第三个值，它应该返回 '2'

我正在做的是:

def getNth(scores, rank):
    scores = sorted(scores.items(), key=operator.itemgetter(0))

    total = 0
    for score, cnt in scores:
        total += cnt
        if  total > rank:
            return score

我想知道我能不能快点？

Answer 1

如果您不在此处重新生成分数，您可以(根据我下面的实验)将运行时间减半:

scores = sorted(scores.items(), key=operator.itemgetter(0))

我创建了一个修改后的方法来避免这种情况:

def getNth2(scores, rank):
  total = 0
  for i in sorted(scores.keys()):
    total += scores[i]
    if  total > rank:
        return i

测量运行时间 here :

start_time = time.time()
for i in xrange(0,100000):
  for i in xrange(0,10):
    getNth(d, i)
end_time = time.time()
print 'Old Runtime:', end_time - start_time

start_time = time.time()
for i in range(0,100000):
  for i in xrange(0,10):
    getNth2(d, i)
end_time = time.time()
print 'New Runtime:', end_time - start_time

Old Runtime: 2.22607803345

New Runtime: 1.09168481827