为什么单层循环比双层循环慢？

Question

这个问题是受到了另一个Stack Overflow的问题启发而产生的-如何改进去重算法？ 问题中提出的要求是：

需要返回一个已删除重复项但最多只能保留2个副本的数组的长度。

例如-[1, 1, 1, 2, 2, 3]，新数组将为[1, 1, 2, 2, 3]。因此，新长度为5。

OP提供的解决方案是-

def removeDuplicates(nums):
    if nums is None:
        return 0
    if len(nums) == 0:
        return 0
    if len(nums) == 1:
        return 1
    new_array = {}
    for num in nums:
        new_array[num] = new_array.get(num, 0) + 1
    new_length = 0
    for key in new_array:
        if new_array[key] > 2:
            new_length = new_length + 2
        else:
            new_length = new_length + new_array[key]
    return new_length

我试图想出一种解决方案，将循环的数量减少到一个循环。

def removeDuplicates1(nums):
    if nums is None:
        return 0
    if len(nums) == 0:
        return 0
    if len(nums) == 1:
        return 1
    new_array = {}
    length = 0
    for num in nums:
        n = new_array.get(num, 0)
        new_array[num] = n + 1
        if n <= 1:
            length += 1
    return length

之后，我试图比较我的解决方案和原始解决方案的时间，我认为我的解决方案应该至少比原始解决方案提供一点改进，但是timeit的结果显示，即使数组包含所有唯一元素，原始解决方案的效果总是更好。所花费的时间如下：

In [3]: l = list(range(1000))

In [4]: %timeit removeDuplicates(l)
1000 loops, best of 3: 390 s per loop

In [5]: %timeit removeDuplicates1(l)
1000 loops, best of 3: 412 s per loop

In [6]: l1 = [1] * 1000

In [7]: %timeit removeDuplicates(l1)
1000 loops, best of 3: 224 s per loop

In [9]: %timeit removeDuplicates1(l1)
1000 loops, best of 3: 304 s per loop

请问有人能解释一下为什么会出现这种情况吗？我是否忽略了什么显而易见的问题？

- Sharon Dwilif K

---

你不会称之为“去重”吗？ - a p

好吧，我只是重复使用了另一个帖子的原始发布者使用的相同名称 :) - Sharon Dwilif K

而 new_array 不是一个数组，它是一个 dict -- 另一个线程的 OP 命名不好 :/ - a p

@StevenRumbalski，它仍然比原始方法慢。- `In [19]: %timeit removeDuplicates(l) 1000次循环，3次中的最佳结果：每个循环需要373秒In [20]: %timeit rD2(l) 1000次循环，3次中的最佳结果：每个循环需要385秒。其中rD2()`是我为您的方法定义的函数。 - Sharon Dwilif K

请注意，所有时间都以微秒为单位，由于某种原因，我无法复制“mew”符号。 - Sharon Dwilif K

Answer 1

如果输入列表为list(range(x))，即没有重复项，则您的代码速度更快，但如果输入列表中有大量重复项，则您的代码速度会变慢。

我一直用以下时间记录结果：

collections.defaultdict - fastest
original proposal - next fastest (if duplicates)
your single loop proposal - slower, if there are duplicates
collections.counter - slowest

它们基本上都是相同的东西，所以它们总是在时间上接近。

defaultdict是最快的，因为原始提案基本上复制了它，但defaultdict是随Python一起安装的核心库的一部分。我想“不要重复造轮子”适用于此。

但是当您使用单个循环时，为什么您的代码会变慢？请考虑原始代码执行两个循环，因为有两个不同的要迭代的内容。首先迭代原始数据列表，然后迭代唯一项（可能较少，因为预计存在重复项）。

您的代码执行了原始代码执行的所有操作，但是对于原始数据列表中的每个元素都执行了这些操作。将其视为具有两个独立循环和一个循环计数器的循环。您仍然必须为原始列表中的所有元素执行第一个循环，因为您必须如此。但是第二个循环（您试图通过在原始循环内执行它来摆脱它）现在必须为原始数据集中的每个项目执行其代码。

通过拥有一个循环，您从中获得的收益被执行更多次而失去了，特别是对于原始数据中的重复项。

- Kenny Ostrom