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

Question

好的，我在 coderbyte 上做了一个谜题，谜题内容如下：

让函数 SimpleMode(arr) 获取存储在 arr 中的数字数组和 return 出现最频繁的数字（众数）。例如：如果 arr 包含 [10, 4, 5, 2, 4]，输出应该是 4。如果有多个模式 return，则第一个出现在数组中的模式（即 [5, 10 , 10, 6, 5] 应该 return 5 因为它先出现）。如果没有模式return -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

您的代码一次完成所有操作。
其他代码在 arr.count().

中包含隐藏的嵌套循环

Answer 2

第二个程序每次迭代调用 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 数组，但它也可以是 [=17= 中的数组） ] 标准库中的模块）。

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

Why is my program faster than the one using a python built in function?

python

time

list