>= 10,000数字列表比较的Python效率
我一直试图完成一个问题，从最近的ACM编程挑战之一，后竞争，并一直遇到一个障碍。问题状态
您的团队已被监督评审小组的竞赛主管保留。比赛要求评委给参赛者分配整数分数--分数越高越好。虽然这个事件对分数的含义有标准，但每个评委对这些标准的解释可能有所不同。比如说，100分对不同的法官来说可能意味着不同的事情。 导演的主要目标是确定哪些竞争对手应该获得最高职位的奖品。虽然每个法官的绝对分数可能不同，但主管意识到相对排名提供了所需的信息--如果两名法官对同一竞争对手排名第一、第二、第三、.然后，他们就谁应该获得奖品达成一致。 你的团队将编写一个程序，通过比较两组评委的成绩来帮助导演。该程序是读取两个整数分数的名单，按竞争对手的顺序，并确定最高的排名位置(第一位是最高的)，法官不同意。 输入到您的程序将是一系列的分数列表对。每对以一个整数开始，给出竞争对手N的数目，1
有包含N= 4和N=8的测试用例。
4. 3 8 6 2 15 37 17 3 8 80 60 40 20 10 30 50 160 100 120 80 20 60 90 135
以及预期的输出:对于每个分数对，打印一条以整数表示评委不同意的最高排名位置的线。如果法官在每一个地方都同意，打印一行，只包含“同意”一词。使用下面的格式：" case "，一个空格，一个大小写，一个冒号和一个空格，以及那个没有尾随空格的答案。
判例1:同意 案例2: 3
我的守则如下：
import sys
def calculate(competitors, scores1, scores2):
scores1sort = sorted(scores1, reverse = True)
scores2sort = sorted(scores2, reverse = True)
for x in range(len(scores1)) :
indexed1 = scores1.index(scores1sort[x])
#print ('place: ', x+1, 'Position: ',indexed1+1)
#iterating over the entire length of the sorted lists multiple times takes too long
indexed2 = scores2.index(scores2sort[x])
#print ('place: ', x+1, 'Position: ',indexed2+1)
if indexed2 != indexed1 :
print ( "Case", str(case) + ":", x+1)
return
#run both fors at the same time, compare indexed of scores1 to index of scores2
#if the position(indexed + 1) doesnt match between the two, print the place(x+1) of the disparity
#if match:
#print ("Case " + case +": " + "agree"
#else: print (Case " + case + ": " + index of disagreement
print ("Case", str(case) + ":" , "agree")
scores1 = [];
scores2 = [];
case = 1;
state = 0;
# 0 indicates number of competitors
# 1 indicates judge 1
# 2 indicates judge 2
#for line in sys.stdin:
for line in test.split("\n"):
line = line.strip().split()
if not line:
continue
if state == 0:
#if empty line, error
competitors = int(line[0])
state = 1;
else:
for y in line:
if state == 1:
scores1.append(int(y))
if len(scores1) >= competitors:
state = 2;
elif state == 2:
scores2.append(int(y))
if len(scores2) >= competitors:
state = 0;
#print (competitors, score1, scores2)
calculate(competitors, scores1, scores2);
case += 1;我的代码目前是使用一个文本文件运行的，该文本文件包含留给我们的编程竞赛的测试输入，其中包括小的测试值，但也包括一组包含10,000个竞争者的值。
我毫不怀疑，如果给出足够的时间，代码可以完成，但是编程挑战准则规定，代码必须在比当前运行时更短的时间内运行。
因此，我想问一下关于如何优化我的代码以提高执行速度的任何技巧。
回答 4
Stack Overflow用户
发布于 2014-11-29 22:11:39
现在，您的程序在二次时间内运行，因此随着N的增加，运行时间将急剧增加。您必须将内部循环中的工作降到O(n)以下才能处理较大的数据集。
此外，简单地在开始时对输入进行排序并不能帮助您，因为您丢失了两个数组中关联条目之间的映射。
像这样的事怎么样：
def calculate(N, scores1, scores2):
ranked1 = sorted(enumerate(scores1),key=lambda x: x[1], reverse=True)
ranked2 = sorted(enumerate(scores2),key=lambda x: x[1], reverse=True)
...现在有两个数组，从最高排序到最低排序，代价为O(n log )，您只需搜索ranked1i != ranked2i (最坏的情况是O(n) )的情况。
因此，总的运行时间是O(n +n log )最坏的情况。
Stack Overflow用户
发布于 2014-11-29 21:29:03
提供示例输入将有所帮助。此时，在索引方法调用和内存分配的范围内(如果在py2上运行)，似乎正在释放时间。尝试使用枚举以避免索引。
Stack Overflow用户
发布于 2014-11-29 21:41:52
不要使用list.index()函数，而是使用二进制搜索，因为列表将被排序。list.index内部执行线性搜索，至少在CPython中，源代码这里。
将O(n)搜索转换为O(log n)应该会节省足够的时间。
https://stackoverflow.com/questions/27207090
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号