Python-从列表列表中删除重复项

Question

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

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

我想从中删除重复的元素。如果这是正常列表，而不是我可以使用的列表set。但不幸的是，该列表不可散列，因此无法建立一组列表。只有元组。因此，我可以将所有列表转换为元组，然后使用set并返回列表。但这不是很快。

如何以最有效的方式做到这一点？

上面的结果应为：

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

我不在乎保留订单。

注意：这个问题很相似，但不是我所需要的。搜索了SO，但没有找到确切的重复项。

基准测试：

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]]
>>> import itertools
>>> k.sort()
>>> list(k for k,_ in itertools.groupby(k))
[[1, 2], [3], [4], [5, 6, 2]]

itertools通常会为此类问题提供最快，最强大的解决方案，非常值得你熟悉！！）

编辑：正如我在评论中提到的那样，正常的优化工作主要集中在大型输入（big-O方法）上，因为它要容易得多，可以提供良好的回报。但是有时（本质上是对推动性能极限界限的深层内部代码循环中的“悲剧性瓶颈”），可能需要更详细地介绍概率分布，从而确定要优化的性能指标（可能是上限或第90个百分位数比平均值或中位数更重要，具体取决于一个人的应用程序），一开始执行启发式检查，然后根据输入数据特征选择不同的算法，依此类推。

仔细测量“点”性能（特定输入的代码A与代码B）是此极其昂贵的过程的一部分，而标准库模块timeit在此方面可以提供帮助。但是，在shell提示符下使用它更容易。例如，以下是一个简短的模块，展示了此问题的一般方法，另存为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-为什么它必须首先是列表列表而不是一组元组？如果重复删除任务很频繁，并且性能分析表明它是程序的性能瓶颈，则始终保留一组元组，并仅在需要和需要时才从中获取列表列表，例如，整体上可能会更快。