从列表中删除重复项-IT科技

摘要：问题描述：我有一个 Python 列表列表：k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]] 我想从中删除重复的元素。如果它是一个普通列表而不是列表，我可以使用set。但不幸的是，该列表不可哈希，并且不能创建列表集合。只能创建元组。所以我可以将所有列表转换为元组，然...

问题描述：

我有一个 Python 列表列表：

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

我想从中删除重复的元素。如果它是一个普通列表而不是列表，我可以使用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

解决方案 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

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

如果（正如对性能的痴迷所暗示的那样）此操作位于突破边界应用程序的核心内部循环中，那么值得在其他代表性输入样本上尝试同一组测试，可能会检测到一些简单的度量，这些度量可以启发式地让您选择其中一种方法（但当然，该度量必须很快）。

还值得考虑保留不同的表示形式k——为什么它首先必须是列表的列表而不是元组集合？例如，如果重复删除任务很频繁，并且分析显示它是程序的性能瓶颈，那么始终保留一组元组并仅在需要时从中获取列表列表，总体上可能会更快。

解决方案 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简单易懂，并且保留每个元素第一次出现的顺序应该很有用，但我猜它的复杂性是二次的，因为您正在搜索每个元素的整体。

解决方案 3：

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

我不知道它是否一定更快，但你不必使用元组和集合。

解决方案 4：

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

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

解决方案 5：

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

解决方案 6：

甚至您的“长”列表也很短。另外，您是否选择它们来匹配实际数据？性能将随着这些数据的实际样子而变化。例如，您一遍又一遍地重复一个短列表以制作一个更长的列表。这意味着二次解在您的基准测试中是线性的，但在现实中并非如此。

对于实际较大的列表，set 代码是您的最佳选择 - 它是线性的（尽管占用空间很大）。sort 和 groupby 方法是 O(n log n)，而 loop in 方法显然是二次的，因此您知道当 n 变得非常大时它们将如何扩展。如果这是您正在分析的数据的实际大小，那么谁会在乎呢？它很小。

顺便说一句，如果我不形成中间列表来制作集合，我会看到明显的加速，也就是说，如果我替换

kt = [tuple(i) for i in k]
skt = set(kt)

和

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

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

解决方案 7：

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

可以使其变得懒惰，同时保持顺序，方法是迭代列表列表并添加到“已见”中set。然后，如果在此跟踪器中未找到列表，则仅产生列表set。

此unique_everseen配方可在itertools 文档中找到。它也可在第三方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由于列表不可哈希，因此转换是必要的。

解决方案 8：

创建一个以元组为键的字典，并打印键。

创建以元组为键、以索引为值的字典
打印字典键的列表

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

dict_tuple = {tuple(item): index for index, item in enumerate(k)}

print [list(itm) for itm in dict_tuple.keys()]

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

解决方案 9：

最简单的解决方案是将列表列表转换为元组列表，然后应用dict.fromkeys()方法将其转换回列表。

例如：

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

转换为元组列表k = list(map(tuple, k))

这将给你[(1, 2), (4,), (5, 6, 2), (1, 2), (3,), (4,)]

然后执行以下操作：unique = list(dict.fromkeys(k))

你将拥有[(1, 2), (4,), (5, 6, 2), (3,)]

就这样。

解决方案 10：

这应该可行。

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

k_cleaned = []
for ele in k:
    if set(ele) not in [set(x) for x in k_cleaned]:
        k_cleaned.append(ele)
print(k_cleaned)

# output: [[1, 2], [4], [5, 6, 2], [3]]

解决方案 11：

奇怪的是，上面的答案删除了“重复项”，但如果我还想删除重复的值怎么办？以下内容应该很有用，并且不会在内存中创建新对象！

def dictRemoveDuplicates(self):
    a=[[1,'somevalue1'],[1,'somevalue2'],[2,'somevalue1'],[3,'somevalue4'],[5,'somevalue5'],[5,'somevalue1'],[5,'somevalue1'],[5,'somevalue8'],[6,'somevalue9'],[6,'somevalue0'],[6,'somevalue1'],[7,'somevalue7']]


print(a)
temp = 0
position = -1
for pageNo, item in a:
    position+=1
    if pageNo != temp:
        temp = pageNo
        continue
    else:
        a[position] = 0
        a[position - 1] = 0
a = [x for x in a if x != 0]         
print(a)

o/p 是：

[[1, 'somevalue1'], [1, 'somevalue2'], [2, 'somevalue1'], [3, 'somevalue4'], [5, 'somevalue5'], [5, 'somevalue1'], [5, 'somevalue1'], [5, 'somevalue8'], [6, 'somevalue9'], [6, 'somevalue0'], [6, 'somevalue1'], [7, 'somevalue7']]
[[2, 'somevalue1'], [3, 'somevalue4'], [7, 'somevalue7']]

解决方案 12：

有一个更简单的单行代码：

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]] # your data

new_k = [] # new list with unique values
_ = [new_k.append(i) for i in k if i not in new_k] # one-liner solution

简短而简单。请注意，如果您没有将列表推导分配给值（在这种情况下将其丢弃），它将打印[None, None]因为list.append()不返回值。

解决方案 13：

介绍一下背景，我刚开始学习 Python 并学习了理解能力。

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
dedup = [elem.split('.') for elem in set(['.'.join(str(int_elem) for int_elem in _list) for _list in k])]

解决方案 14：

如果你想保持元素的顺序完整

你可以使用dict.fromkeys()从 Python 3.7 开始的顺序不会改变：

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

[list(x) for x in dict.fromkeys(tuple(x) for x in k)]

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

如果您不关心元素的顺序那么：

[list(x) for x in set(tuple(x) for x in k)]

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

解决方案 15：

如果抱怨不是针对“不够快”本身，而是针对您提出的解决方案的“不够简洁”部分，那么在 Python 3.5+ 中，借助解包运算符和简洁的元组符号，您可以使链式数据结构转换变得非常简短（当然，这仍然是 O(n^2)，但解包仍然比直接转换稍快）：

输入：

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
k = [*map(list, {*map(tuple, k)})]

# Order-preserving alternative:
# k = [*map(list, dict.fromkeys(map(tuple, k)))]

print(k)

输出：

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

解决方案 16：

另一个可能更通用、更简单的解决方案是创建一个以对象的字符串版本为键的字典，并在最后获取 values()：

>>> dict([(unicode(a),a) for a in [["A", "A"], ["A", "A"], ["A", "B"]]]).values()
[['A', 'B'], ['A', 'A']]

问题在于，这仅适用于字符串表示形式是足够好的唯一键的对象（对于大多数本机对象而言都是如此）。

解决方案 17：

k=[[1, 2], [4], [5, 6, 2], [1, 2], [3], [5, 2], [3], [8], [9]]
kl=[]
kl.extend(x for x in k if x not in kl)
k=list(kl)
print(k)

打印结果为：

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

解决方案 18：

NumPyunique()已经提供了一个实现此操作的函数：

import numpy as np

unique_list = list(np.unique(list_with_duplicates))