从列表列表中删除重复项

我有一个Python列表列表：

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

我想从中删除重复的元素。如果它是一个普通列表而不是我可以使用的列表set。但不幸的是，该列表不可散列，并且无法创建列表集。仅元组。所以我可以将所有列表转换为元组，然后使用 set 并返回列表。但这并不快。

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

上面列表的结果应该是：

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

我不在乎维持秩序。

Note: 这个问题类似，但不完全是我需要的。搜索过，但没有找到完全相同的重复项。

基准测试：

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

>>> 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通常为此类问题提供最快、最强大的解决方案，并且well值得深入熟悉！-)

Edit：正如我在评论中提到的，正常的优化工作集中在大输入（大 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-- 为什么它首先必须是列表的列表而不是一组元组？例如，如果重复删除任务很频繁，并且分析表明它是程序的性能瓶颈，则始终保留一组元组并仅在需要时从其中获取列表列表，总体上可能会更快。