python - 查找唯一号码的代码又慢又低效？

Question

我最近正在解决 codewars 上的一个代码问题，以在列表中查找唯一的数字。我的代码可以工作，但是效率非常低。我不知道为什么会这样。下面是我发布的代码:

我认为问题可能在于我每次迭代时都会复制列表(也许)。

def find_uniq(arr):
    equal_check = 0
    for i in arr:
        arr_new = arr.copy()
        arr_new.remove(i)
        if i not in arr_new:
            equal_check = i
    return equal_check

Answer 1

使用collections.Counter ，获取计数为1的:

from collections import Counter 

def find_uniq(arr):
    c = Counter(arr)
    return [number for number,count in c.most_common() if count == 1]


print(find_uniq( [1,2,3,4,2,3,4,5,6,4,5,6,7,8,9])) # [1, 7, 8, 9]

这大约需要 O(2*n)，因此 O(n) 因为 2 是常数。

<小时/>

<强> collection.defaultdict使用 int，获取计数为 1 的:

# defaultdict
from collections import Counter , defaultdict

def find_uniq(arr):
    c = defaultdict(int)
    for a in arr:
        c[a] += 1
    return [number for number,count in c.items() if count == 1]


print(find_uniq( [1,2,3,4,2,3,4,5,6,4,5,6,7,8,9])) # [1, 7, 8, 9]

这大约需要 O(2*n)，因此 O(n) 因为 2 是常数 - 由于实现内部的 C 优化，它比 Counter 稍快一些(参见 f.e Surprising results with Python timeit: Counter() vs defaultdict() vs dict() )。

<小时/>

<强> normal dicts并设置默认值或测试/添加，获取计数为1的:

# normal dict - setdefault
def find_uniq(arr):
    c = dict()
    for a in arr:
        c.setdefault(a,0)
        c[a] += 1
    return [number for number,count in c.items() if count == 1]


print(find_uniq( [1,2,3,4,2,3,4,5,6,4,5,6,7,8,9])) # [1, 7, 8, 9]

# normal dict - test and add 
def find_uniq(arr):
    c = dict()
    for a in arr:
        if a in c:
            c[a] += 1
        else:
            c[a] = 1

    return [number for number,count in c.items() if count == 1]


print(find_uniq( [1,2,3,4,2,3,4,5,6,4,5,6,7,8,9])) # [1, 7, 8, 9]

Setdefault 每次都会创建默认值 - 它比 Counter 或 defaultdict 慢，但比使用 test/add 更快。

<小时/>

<强> itertools.groupby (需要排序列表!)，获取计数为1的:

from itertools import groupby

def find_uniq(arr):
    return [k for (k,p) in groupby(sorted(arr)) if len(list(p)) == 1]

print(find_uniq( [1,2,3,4,2,3,4,5,6,4,5,6,7,8,9])) # [1, 7, 8, 9]

groupby 需要一个排序列表，单独的列表排序是 O(n * log n) ，组合起来比其他方法慢。