从列表列表中删除重复项

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经常为这类问题提供最快,最强大的解决方案,非常值得熟悉! - )

编辑:正如我在评论中提到的,正常的优化工作主要集中在大型投入(大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

二次方法也不错,但sort和groupby方法更好.等等

如果(正如对性能的痴迷所表明的那样)这个操作处于推动边界应用程序的核心内部循环,那么值得尝试对其他代表性输入样本进行相同的测试,可能会检测到一些可能启发式地让你发现的简单测量选择一种或另一种方法(当然,措施必须快速).

考虑保持不同的表示也是值得的k- 为什么它必须是列表而不是一组元组？如果重复删除任务是频繁的,并且分析显示它是程序的性能瓶颈,那么始终保留一组元组并仅在需要时从中获取列表列表,例如,总体上可能更快.

Answer 2

>>> 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 3

手动完成,创建新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 4

a_list = [
          [1,2],
          [1,2],
          [2,3],
          [3,4]
]

print (list(map(list,set(map(tuple,a_list)))))

输出：[[1, 2], [3, 4], [2, 3]]

Answer 5

即使你的“长”清单也很短。另外，您选择它们​​是否符合实际数据？性能会根据这些数据的实际情况而有所不同。例如，您一遍又一遍地重复一个简短的列表以形成一个较长的列表。这意味着二次解在您的基准测试中是线性的，但实际上并非如此。

\n\n

对于实际较大的列表，设置代码是您最好的选择\xe2\x80\x94it\的线性（尽管需要空间）。sort 和 groupby 方法的复杂度为 O(n log n)，并且方法中的循环显然是二次的，因此您知道当 n 变得非常大时，这些方法将如何扩展。如果这是您正在分析的数据的真实大小，那么谁在乎呢？它很小。

\n\n

顺便说一句，如果我不形成中间列表来制作集合，也就是说，如果我替换

\n\n

kt = [tuple(i) for i in k]\nskt = set(kt)\n

\n\n

和

\n\n

skt = set(tuple(i) for i in k)\n

\n\n

真正的解决方案可能取决于更多信息：您确定列表列表确实是您需要的表示形式吗？

\n

Answer 6

元组列表和 {} 可用于删除重复项

>>> [list(tupl) for tupl in {tuple(item) for item in k }]
[[1, 2], [5, 6, 2], [3], [4]]
>>> 

Answer 7

set到目前为止，该问题的所有相关解决方案都需要set在迭代之前创建一个完整的解决方案。

通过迭代列表列表并添加到“seen”，可以使其变得懒惰，同时保留顺序set。如果在此跟踪器中未找到，则仅生成一个列表set。

这个unique_everseen食谱可以在itertools 文档中找到。它也可以在第 3 方toolz库中找到：

from toolz import unique

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

# lazy iterator
res = map(list, unique(map(tuple, k)))

print(list(res))

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

请注意，tuple转换是必要的，因为列表不可散列。