即使迭代更多，为什么一个代码比其他代码更快？

我的代码很短，迭代次数少于其他次数，但仍会在codechef.com上接受其他代码时超时错误。该代码解决方案上codechef.com 的“暧昧置换”的问题为什么是这样的代码：比这个代码快即使迭代更多，为什么一个代码比其他代码更快？

def inverse(data,x): 

    temp=[] 

    for i in range(x): 
     temp.append(0) 
    for i in range(x): 
     temp[data[i]-1]=i+1 
    return temp 

def main(): 

    while 1: 
     x=input() 
     if not x: 
      return 
     data=raw_input().split(' ') 
     for i in range(len(data)): 
      data[i]=int(data[i]) 
     temp = inverse(data,x) 
     if temp==data: 
      print 'ambiguous' 
     else: 
      print 'not ambiguous' 

if __name__ == "__main__": 
    main()

：

while True: 

    output=[] 
    n= input() 
    if n==0: break 
    caseList= raw_input().split() 
    amb=1 
    for i in range(1, n+1): 
     output.append(str(caseList.index(str(i))+1)) 

    if output==caseList: 
     print ("ambiguous") 
    else: 
     print ("not ambiguous")

请帮我...

来源

2012-03-01 azuri

问题链接：http://www.codechef.com/problems/PERMUT2/ – jsbueno 2012-03-02 05:20:14

当这样一个一致的时间差出现时，我们并不是在谈论2或3倍慢的事情 - 如果一种方法通过了，另一种方法总是超时，那么这是一个巨大的时间差异 - 通常与算法复杂度。

尽管第一个代码有很大的改进空间（例如，使用xrange代替范围），但在最终数组中，结果是随机访问更新，直接由data[i] - 1计算的索引 - 而在第二个片段，您使用caseList.index(str(i))来检索每个索引。 “index”lisr方法从头开始在列表上执行线性搜索。它看起来似乎很少，但是当列表中的每个元素都是doen时，你的算法是O（N）变成O（N 2） - 这在第二种形式中将戏剧性的速度放大。

来源

2012-03-02 05:19:57 jsbueno

我认为你的第二个代码不在函数内部。

访问函数中的局部变量比访问全局变量要快得多。这意味着在全局范围内运行的代码总是可能会变慢。

来源

2012-03-01 20:32:04 Duncan

我一开始并不完全相信，但在经过快速测试后，我只能说是哇。我的快速测试表明，当地人（对我来说）比gloabls快170％。 – MitMaro 2012-03-01 20:45:00

但是这不会导致超时 - 问题在于使用“索引”方法 – jsbueno 2012-03-02 05:11:34

看起来你正在使用其他代码使用整数的字符串，这会使你放慢速度。

来源

2012-03-01 20:37:38

即使迭代更多，为什么一个代码比其他代码更快？

回答

相关问题