从列表列表中删除重复项
我有一个Python的列表：
k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]我想要删除其中的重复元素。如果这是一个普通的列表，而不是我可以使用的列表set..。但不幸的是，列表是不可哈希的，并且不能生成列表集。仅元组。因此，我可以将所有列表转换为元组，然后使用set并返回到列表。但这并不快。
怎样才能以最有效的方式做到这一点呢？
上述列表的结果应为：
k = [[5, 6, 2], [1, 2], [3], [4]]我不关心维持秩序。
注意：此question是相似的，但不完全是我需要的。已经搜索过了，但没有找到完全相同的副本。
基准测试：
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回答 13
Stack Overflow用户
发布于 2010-02-07 01:33:58
>>> 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--为什么它必须是一个列表列表，而不是一组元组？例如，如果重复删除任务很频繁，并且分析显示它是程序的性能瓶颈，则始终保留一组元组并仅在需要时才从中获取列表列表可能会整体上更快。
Stack Overflow用户
发布于 2010-02-07 01:33:06
手动执行此操作，创建新的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对于每个元素。
Stack Overflow用户
发布于 2010-02-07 01:21:34
>>> 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]]我不知道它是否一定更快，但你不需要使用元组和集合。
https://stackoverflow.com/questions/2213923
复制相似问题