python代码运行时差

Question

我在练Leetcode，想请教3个关于代码运行时间的问题。

1. 我注意到在 Leetcode 上，即使是相同的代码也会有相当的如果多次提交，运行时间不同。和差别很大，正常吗？我看到了不同之处第一次超过 26%，但第二次超过 51%。那真的是让我感到困惑，而我正试图弄清楚我在哪里以及如何很好的代码。

2. 实际代码:Leetcode p21，删除元素

这是在不创建新列表的情况下，从一个int列表中删除一个值的所有元素，并返回新列表的长度。

def removeElement(IntList, val):
    n = 0
    while n < len(IntList): 
        if IntList[n] == val:
           IntList.pop(n)   
        else:
            n += 1  
    return len(IntList)

def removeElement2(IntList, val): 
    while val in IntList:
        IntList.remove(val)
    return len(IntList)

你可以看到我写了两个可以工作的函数，第二个比第一个短得多，但不知何故第一个似乎更快。我想知道为什么。

1. 无需提交 Leetcode 即可确定一组代码是否比另一组代码快的最佳方法是什么？

谢谢，

Answer 1

有兴趣的 friend ，我尝试用timeit来评估这两个函数。结果很有意思，我发现随着列表长度变长，两个函数的效率发生了变化:

当列表很短时，第一个比第二个慢得多:

print(timeit.Timer('removeElement(nums, val)',
                   setup='from __main__ import removeElement; '
                         'nums = [1, 2, 3, 4, 2, 3, 4, 4, 5, 6, 1, 2, 3, 4];'
                         'val = 4')
      .repeat(3, 1000000))

# >>> [1.8547368030012876, 1.7035995290007122, 1.718884424000862]

print(timeit.Timer('removeElement2(nums, val)',
                   setup='from __main__ import removeElement2; '
                         'nums = [1, 2, 3, 4, 2, 3, 4, 4, 5, 6, 1, 2, 3, 4];'
                         'val = 4')
      .repeat(3, 1000000))
# >>> [0.4291627630009316, 0.4323928640005761, 0.43043123800089234]

但是，如果我创建一个非常长的列表:

print(timeit.Timer('removeElement(nums, val)',
                   setup='from __main__ import removeElement; '
                         'nums = list(range(10)) * 10000;'
                         'val = 4')
      .repeat(3, 100))

# >>> [1.5640779950008437, 1.5756833779996668, 1.6097137039996596]

print(timeit.Timer('removeElement2(nums, val)',
                   setup='from __main__ import removeElement2; '
                         'nums = list(range(10)) * 10000;'
                         'val = 4')
      .repeat(3, 100))
# >>> [11.877236265998363, 11.790503606998755, 12.056773186999635]

第二个函数现在慢多了。