从一个列表的列表中删除重复项

17 浏览
0 Comments

从一个列表的列表中删除重复项

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

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

我想从中删除重复元素。如果它只是一个普通的列表，我可以使用set。但不幸的是，列表是不可哈希的，不能创建列表的集合，只能创建元组的集合。所以我可以将所有列表转换为元组，然后使用集合，然后再转换回列表。但这不是快速的。

如何以最高效的方式完成这个任务？

上述列表的结果应该是：

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

我不关心保留顺序。

注意：这个问题与我的需求类似，但不完全相同。在Stack Overflow上进行了搜索，但没有找到完全相同的问题。

基准测试：

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)

"loop in"（二次方法）对于短列表来说是最快的。对于长列表来说，它比除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

0