python - 为什么我的程序比使用 python 内置函数的程序快？

Question

好吧，我在 coderbyte 上做了一个谜题，这是谜题的内容:

让函数 SimpleMode(arr) 获取存储在 arr 中的数字数组，并返回出现最频繁的数字(众数)。例如:如果 arr 包含 [10, 4, 5, 2, 4]，则输出应为 4。如果有多个模式，则返回第一个出现在数组中的模式(即 [5, 10, 10, 6 , 5] 应该返回 5 因为它首先出现)。如果没有模式返回-1。该数组不会为空。

这是我的程序:

import time
from random import randrange

def SimpleMode(arr): 
  bestMode=0
  numTimes=0
  for x in range(len(arr)):
    if len(arr)>0:
      currentNum=arr[0]
      currentMode=0
      while currentNum in arr:
        currentMode+=1
        arr.remove(currentNum)
      if currentMode>numTimes:
        numTimes=currentMode
        bestMode=currentNum
    else: break
  if numTimes==1: bestMode=-1
  return bestMode

start_time = time.time()
numbers = [randrange(1,10) for x in range(0, 1000)]
print(SimpleMode(numbers))
print("--- %s seconds ---" % (time.time() - start_time))

这是别人写的一个更简单的程序:

import time
from random import randrange

def SimpleMode(arr): 

  best = -1
  best_count = 1

  for c in arr:
    if arr.count(c) > best_count:
      best = c
      best_count = arr.count(c)

  return best

start_time = time.time()
numbers = [randrange(1,10) for x in range(0, 1000)]
print(SimpleMode(numbers))
print("--- %s seconds ---" % (time.time() - start_time))

现在我知道使用我的计时方法取决于我的 CPU 正在做什么等等，所以这不是最准确的方法，但抛开这个我发现我的计算机需要 0.012000 秒来运行我的程序, 而第二个程序却用了 0.025001 秒。

这就是我不解的地方。我自己编写的程序花费的时间不到另一个程序花费的时间的一半，后者使用内置 python 函数并且只有一个 for 循环，而我的程序在 for 循环内有一个 while 循环。

谁能对此提供任何见解？

Answer 1

第二个程序每次迭代调用 count 两次，因为 count 是 O(n)(也就是说，它必须遍历整个数组，就像for 循环)，时间很快就会增加。

也就是说，您的程序可以进一步减少:

import collections

def SimpleMode(arr):
    if not arr:
        return -1
    counts = collections.Counter(arr)
    return max(counts, key=lambda k: (counts[k], -arr.index(k)))

此外，请注意您的初始程序会改变其输入(由于 .remove 调用，它有效地破坏了您传递给它的列表，如果您想对 做任何事情，这将很糟糕arr 在调用 SimpleMode 之后。

最后，在 Python 中，[1, 2, 3, 4] 构造称为列表，而不是数组。在 Python 中存在一个叫做数组的东西，它不是这个(大多数时候它是一个 NumPy 数组，但它也可以是 array 模块中的数组)标准库)。