从列表中移除重复项

Question

我在Python中有一个列表的列表：

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

我想从中去掉重复的元素。如果这是一个普通的列表，我可以用set来处理。但不幸的是，这个列表是不可哈希的，不能直接用set来处理列表，只能用元组。所以我可以把所有的列表转换成元组，然后用set，最后再转回列表。不过这样做速度不快。

有没有更有效的方法来实现这个呢？

上面这个列表的结果应该是：

k = [[5, 6, 2], [1, 2], [3], [4]]

我不在乎保持顺序。

注意：这个问题类似，但并不是我需要的。我在StackOverflow上搜索过，但没有找到完全相同的。

---

基准测试：

import itertools, time


class Timer(object):
    def __init__(self, name=None):
        self.name = name

    def __enter__(self):
        self.tstart = time.time()

    def __exit__(self, type, value, traceback):
        if self.name:
            print '[%s]' % self.name,
        print 'Elapsed: %s' % (time.time() - self.tstart)


k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [5, 2], [6], [8], [9]] * 5
N = 100000

print len(k)

with Timer('set'):
    for i in xrange(N):
        kt = [tuple(i) for i in k]
        skt = set(kt)
        kk = [list(i) for i in skt]


with Timer('sort'):
    for i in xrange(N):
        ks = sorted(k)
        dedup = [ks[i] for i in xrange(len(ks)) if i == 0 or ks[i] != ks[i-1]]


with Timer('groupby'):
    for i in xrange(N):
        k = sorted(k)
        dedup = list(k for k, _ in itertools.groupby(k))

with Timer('loop in'):
    for i in xrange(N):
        new_k = []
        for elem in k:
            if elem not in new_k:
                new_k.append(elem)

对于短列表来说，“循环内”（二次方法）是所有方法中最快的。对于长列表，它的速度比除了groupby方法以外的所有方法都快。这有道理吗？

对于短列表（代码中的那个），进行了100000次迭代：

[set] Elapsed: 1.3900001049
[sort] Elapsed: 0.891000032425
[groupby] Elapsed: 0.780999898911
[loop in] Elapsed: 0.578000068665

对于更长的列表（代码中的那个重复了5次）：

[set] Elapsed: 3.68700003624
[sort] Elapsed: 3.43799996376
[groupby] Elapsed: 1.03099989891
[loop in] Elapsed: 1.85900020599

Answer 1

>>> k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
>>> k = sorted(k)
>>> k
[[1, 2], [1, 2], [3], [4], [4], [5, 6, 2]]
>>> dedup = [k[i] for i in range(len(k)) if i == 0 or k[i] != k[i-1]]
>>> dedup
[[1, 2], [3], [4], [5, 6, 2]]

我不确定这样做是否一定更快，但你不需要使用元组和集合。

Answer 2

手动操作的话，可以创建一个新的 k 列表，然后把到目前为止没有找到的条目添加进去：

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
new_k = []
for elem in k:
    if elem not in new_k:
        new_k.append(elem)
k = new_k
print k
# prints [[1, 2], [4], [5, 6, 2], [3]]

这样做很简单易懂，而且你可以保留每个元素第一次出现的顺序，如果这对你有用的话。不过我想这样做的效率可能不高，因为你需要为每个元素都去搜索整个 new_k 列表。

Answer 3

>>> k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
>>> import itertools
>>> k.sort()
>>> list(k for k,_ in itertools.groupby(k))
[[1, 2], [3], [4], [5, 6, 2]]

itertools 通常能提供最快和最强大的解决方案，非常值得深入了解！:-)

补充说明：正如我在评论中提到的，通常的优化工作是针对大数据量（大O表示法）进行的，因为这样做更简单，效果也比较明显。但有时候（特别是在代码的深层循环中，性能瓶颈非常关键的时候），我们需要更详细地分析，提供概率分布，决定哪些性能指标需要优化（比如上限或第90百分位数可能比平均值或中位数更重要，这取决于你的应用），在开始时进行一些启发式检查，根据输入数据的特点选择不同的算法，等等。

对“点”性能的仔细测量（比如特定输入下的代码A和代码B的比较）是这个非常耗时过程的一部分，标准库模块 timeit 在这里很有帮助。不过，在命令行中使用它会更简单。比如，这里有一个简短的模块来展示解决这个问题的一般方法，保存为 nodup.py：

import itertools

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

def doset(k, map=map, list=list, set=set, tuple=tuple):
  return map(list, set(map(tuple, k)))

def dosort(k, sorted=sorted, xrange=xrange, len=len):
  ks = sorted(k)
  return [ks[i] for i in xrange(len(ks)) if i == 0 or ks[i] != ks[i-1]]

def dogroupby(k, sorted=sorted, groupby=itertools.groupby, list=list):
  ks = sorted(k)
  return [i for i, _ in itertools.groupby(ks)]

def donewk(k):
  newk = []
  for i in k:
    if i not in newk:
      newk.append(i)
  return newk

# sanity check that all functions compute the same result and don't alter k
if __name__ == '__main__':
  savek = list(k)
  for f in doset, dosort, dogroupby, donewk:
    resk = f(k)
    assert k == savek
    print '%10s %s' % (f.__name__, sorted(resk))

注意在你运行 python nodup.py 时进行的合理性检查，以及基本的提升技术（将常量全局名称局部化到每个函数中以提高速度），这样可以让不同的代码在同样的条件下比较。

现在我们可以对这个小示例列表进行检查：

$ python -mtimeit -s'import nodup' 'nodup.doset(nodup.k)'
100000 loops, best of 3: 11.7 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.dosort(nodup.k)'
100000 loops, best of 3: 9.68 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.dogroupby(nodup.k)'
100000 loops, best of 3: 8.74 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.donewk(nodup.k)'
100000 loops, best of 3: 4.44 usec per loop

确认二次方的方法在处理小列表且重复值不多的情况下是足够快的。对于一个没有重复值的短列表：

$ python -mtimeit -s'import nodup' 'nodup.donewk([[i] for i in range(12)])'
10000 loops, best of 3: 25.4 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.dogroupby([[i] for i in range(12)])'
10000 loops, best of 3: 23.7 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.doset([[i] for i in range(12)])'
10000 loops, best of 3: 31.3 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.dosort([[i] for i in range(12)])'
10000 loops, best of 3: 25 usec per loop

二次方的方法还不错，但排序和分组的方法更好。等等等等。

如果（正如对性能的关注所暗示的）这个操作是在你性能极限应用的核心循环中，那么在其他代表性的输入样本上尝试同一组测试是值得的，可能会发现一些简单的指标，帮助你快速选择一种方法（当然，这个指标必须快速）。

还值得考虑为 k 保持不同的表示方式——为什么它必须是一个列表的列表，而不是一组元组呢？如果去重的任务很频繁，并且分析显示这是程序的性能瓶颈，那么始终保持一组元组，并在需要时才从中获取列表的列表，可能会更快。