Python：从列表中删除重复项
我有一个Python列表的列表：
k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]] 我想从中删除重复的元素。 如果它是一个正常列表而不是我可以使用的列表。 但不幸的是，这个清单是不可排除的，不能做一套清单。 只有元组。 所以我可以把所有的列表转换成元组，然后使用set并返回列表。 但是这并不快。
这怎么能以最有效的方式完成呢？
以上列表的结果应该是：
k = [[5, 6, 2], [1, 2], [3], [4]]
我不在乎维护秩序。
注： 这个问题是相似的，但不是我所需要的。 search到但没有find确切的重复。
标杆：
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经常为这类问题提供最快和最强大的解决scheme， 非常值得熟悉！ – ）
编辑 ：正如我在评论中提到的那样，正常的优化工作集中在大投入（大O方法）上，因为它更容易，它提供了很好的回报。 但是有时候（本质上是因为内部深层循环中的“严重的瓶颈”，这会推动性能极限的界限），可能需要进行更多的细节分析，提供概率分布，决定优化哪些性能指标（可能是上限或第90个百分位数比平均数或中位数更重要，取决于应用程序），在开始时执行可能的启发式检查，以根据input数据特征select不同的algorithm等等。
仔细测量“点”性能（代码A和代码B为特定input）是这个非常昂贵的过程的一部分，标准库模块时间在这里帮助。 但是，在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
确认二次方法具有足够小的常量，使其对具有less量重复值的小列表具有吸引力。 用一个没有重复的短名单：
$ 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
二次方法不错，但sorting和groupby更好。 等等
如果（正如对性能的痴迷所暗示的那样）这个操作是在你的推送边界应用程序的核心内部循环中，那么值得对其他代表性input样本进行相同的一组testing，可能会探测到一些可以启发式地让你select一个或另一个方法（但当然措施必须快）。
为k保留一个不同的表示也是值得考虑的 – 为什么它必须是列表的列表而不是一组元组呢？ 如果重复删除任务频繁，并且分析表明它是程序的性能瓶颈，那么始终保留一组元组并且只有在需要的时候才能从中获取列表，例如总体上可能会更快。
>>> 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]]
我不知道它是否一定更快，但你不必使用元组和集合。
手动做，创build一个新的k列表，并添加目前没有find的条目：
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]]
很容易理解，并且你保留每个元素的第一次出现的顺序应该是有用的，但是我想这是复杂的二次方，因为你正在为每个元素search整个new_k 。
即使你的“长”名单也很短。 另外，你是否select它们来匹配实际的数据？ 性能会随着这些数据的实际情况而变化。 例如，你有一个重复的短列表来做一个更长的列表。 这意味着二次求解在你的基准testing中是线性的，但实际上并不是这样。
对于实际大的列表，设置代码是最好的select – 它是线性的（尽pipe空间很大）。 sort和groupby方法是O（n log n），方法中的循环显然是二次的，所以你知道这些将如何变大，因为n变得非常大。 如果这是您正在分析的数据的真实大小，那么谁在乎呢？ 很小
顺便说一下，如果我没有形成一个中间列表来做这个集合，我看到一个明显的加速，也就是说，如果我replace
kt = [tuple(i) for i in k] skt = set(kt)
同
skt = set(tuple(i) for i in k)
真正的解决scheme可能取决于更多的信息：你确定清单列表真的是你需要的表示？
另一个可能更通用更简单的解决scheme是创build一个由string版本的对象键入的字典，并在最后得到values（）：
>>> dict([(unicode(a),a) for a in [["A", "A"], ["A", "A"], ["A", "B"]]]).values() [['A', 'B'], ['A', 'A']]
问题是，这只适用于string表示是足够好的唯一键的对象（对于大多数本机对象来说都是如此）。
