如何在维护秩序的同时从列表中删除重复项?

有没有一个内置的从Python的列表中删除重复,同时保持秩序? 我知道我可以使用一组来删除重复,但是破坏了原来的顺序。 我也知道我可以像这样推出我自己的:

def uniq(input): output = [] for x in input: if x not in output: output.append(x) return output 

(感谢解放这个代码示例 。)

但是,如果可能的话,我想利用一个内置的或更多的Pythonic成语。

相关问题: 在Python中,从列表中删除重复项的最快algorithm是什么,以便所有元素都是唯一的, 同时保持顺序

在这里你有一些替代scheme: http : //www.peterbe.com/plog/uniqifiers-benchmark

最快的一个:

 def f7(seq): seen = set() seen_add = seen.add return [x for x in seq if not (x in seen or seen_add(x))] 

为什么分配seen.addseen_add而不是只调用seen.add ? Python是一种dynamic的语言,解决了seen.add每次迭代都比parsing局部variables更昂贵。 seen.add可能会在迭代之间发生变化,而且运行时间不够聪明,无法排除。 为了安全起见,每次都要检查对象。

如果你打算在同一个数据集上使用这个函数,也许你会更好的使用一个有序集合: http : //code.activestate.com/recipes/528878/

O (1)插入,删除和每个操作的成员检查。

编辑2016年

正如Raymond所指出的那样 ,在OrderedDict在C中实现的Python 3.5+中,列表理解方法将比OrderedDict慢(除非实际上最后需要列表 – 即使这样,只有当input非常短时)。 所以3.5+的最佳解决scheme是OrderedDict

重要编辑2015年

正如@abarnert所指出的那样, more_itertools库( pip install more_itertools )包含一个unique_everseen函数,它可以解决这个问题,而在列表not seen.add没有任何不可读的not seen.add突变 。 这也是最快的解决scheme:

 >>> from more_itertools import unique_everseen >>> items = [1, 2, 0, 1, 3, 2] >>> list(unique_everseen(items)) [1, 2, 0, 3] 

只是一个简单的图书馆导入,没有黑客。 这来自itertools配方unique_everseen的实现,如下所示:

 def unique_everseen(iterable, key=None): "List unique elements, preserving order. Remember all elements ever seen." # unique_everseen('AAAABBBCCDAABBB') --> ABCD # unique_everseen('ABBCcAD', str.lower) --> ABCD seen = set() seen_add = seen.add if key is None: for element in filterfalse(seen.__contains__, iterable): seen_add(element) yield element else: for element in iterable: k = key(element) if k not in seen: seen_add(k) yield element 

在Python 2.7+ 接受的常用成语 (这个工程,但没有为速度优化,我现在将使用unique_everseen )为此使用collections.OrderedDict

运行时间: O(N)

 >>> from collections import OrderedDict >>> items = [1, 2, 0, 1, 3, 2] >>> list(OrderedDict.fromkeys(items)) [1, 2, 0, 3] 

这看起来比以下更好:

 seen = set() [x for x in seq if x not in seen and not seen.add(x)] 

并没有利用丑陋的黑客

 not seen.add(x) 

这依赖于set.add是一个总是返回None的就地方法,所以not None评估为True

但是请注意,尽pipe它具有相同的运行时复杂度O(N),但是解决scheme在原始速度上更快。

 sequence = ['1', '2', '3', '3', '6', '4', '5', '6'] unique = [] [unique.append(item) for item in sequence if item not in unique] 

独特→ ['1', '2', '3', '6', '4', '5']

 from itertools import groupby [ key for key,_ in groupby(sortedList)] 

该列表甚至不必sorting ,充分的条件是相等的值被分组在一起。

编辑:我认为“保持秩序”意味着名单实际上是有序的。 如果情况并非如此,那么MizardX的解决scheme是正确的。

社区编辑:然而,这是“将重复的连续元素压缩为单个元素”的最优雅的方式。

从Python 2.7开始,在保持原始顺序的同时从迭代中移除重复的新方法是:

 >>> from collections import OrderedDict >>> list(OrderedDict.fromkeys('abracadabra')) ['a', 'b', 'r', 'c', 'd'] 

而在Python 3.5中,当OrderedDict在C中被重新实现时,这是现在最快的方法,也是最短和最干净的方法。

[更新]截至CPython 3.6,字典是紧凑的和有序的。 虽然到目前为止还没有保证sorting行为,但在Python 3.6中不会改变。 所以,你可以使用list(dict.fromkeys('abracadabra'))

我想如果你想保持秩序,

你可以试试这个:

 list1 = ['b','c','d','b','c','a','a'] list2 = list(set(list1)) list2.sort(key=list1.index) print list2 

或者类似的你可以这样做:

 list1 = ['b','c','d','b','c','a','a'] list2 = sorted(set(list1),key=list1.index) print list2 

你也可以这样做:

 list1 = ['b','c','d','b','c','a','a'] list2 = [] for i in list1: if not i in list2: list2.append(i)` print list2 

它也可以这样写:

 list1 = ['b','c','d','b','c','a','a'] list2 = [] [list2.append(i) for i in list1 if not i in list2] print list2 

另一个很老的问题的另一个很晚的答案是:

itertools食谱有一个function,使用seen设置技术,但是:

  • 处理标准的keyfunction。
  • 不使用不恰当的黑客。
  • 通过预先绑定seen.add优化循环,而不是查看N次。 ( f7也是这样,但有些版本不这样做。)
  • 通过使用ifilterfalse优化循环,所以你只需要遍历Python中的独特元素,而不是所有的元素。 (当然,你仍然可以在ifilterfalse里遍历所有的内容,但是这是C语言,而且要快得多。)

它实际上比f7更快吗? 这取决于你的数据,所以你必须testing它,看看。 如果你最后想要一个列表, f7使用listcomp,在这里没有办法做到这一点。 (你可以直接append而不是yielding,或者你可以将生成器提供给list函数,但是不能像listcomp中的LIST_APPEND那样快。)无论如何,通常挤出几微秒是不行的与具有容易理解的,可重用的,已经写好的function一样重要,当你想装饰时不需要DSU。

与所有的食谱一样,它也可以在more-iterools

如果你只是想要没有key情况下,你可以简化为:

 def unique(iterable): seen = set() seen_add = seen.add for element in itertools.ifilterfalse(seen.__contains__, iterable): seen_add(element) yield element 

对于不可散列的types(例如列表列表),基于MizardX的:

 def f7_noHash(seq) seen = set() return [ x for x in seq if str( x ) not in seen and not seen.add( str( x ) )] 

5倍快速减less变体,但更复杂

 >>> l = [5, 6, 6, 1, 1, 2, 2, 3, 4] >>> reduce(lambda r, v: v in r[1] and r or (r[0].append(v) or r[1].add(v)) or r, l, ([], set()))[0] [5, 6, 1, 2, 3, 4] 

说明:

 default = (list(), set()) # use list to keep order # use set to make lookup faster def reducer(result, item): if item not in result[1]: result[0].append(item) result[1].add(item) return result >>> reduce(reducer, l, default)[0] [5, 6, 1, 2, 3, 4] 

你可以通过符号'_ [1]'来构build列表理解。
例如,下面的函数是唯一的 – 通过引用其列表理解来确定元素列表而不改变它们的顺序。

 def unique(my_list): return [x for x in my_list if x not in locals()['_[1]']] 

演示:

 l1 = [1, 2, 3, 4, 1, 2, 3, 4, 5] l2 = [x for x in l1 if x not in locals()['_[1]']] print l2 

输出:

 [1, 2, 3, 4, 5] 

只需从外部模块1添加另一个(非常高效的)这样的function的实现: iteration_utilities.unique_everseen

 >>> from iteration_utilities import unique_everseen >>> lst = [1,1,1,2,3,2,2,2,1,3,4] >>> list(unique_everseen(lst)) [1, 2, 3, 4] 

计时

表面时间(Python 3.5)表明它比我testing的所有其他替代方法都快,包括OrderedDict.fromkeysf7more_itertools.unique_everseen

 from iteration_utilities import unique_everseen from collections import OrderedDict from more_itertools import unique_everseen as more_itertools_unique_everseen def f7(seq): seen = set() seen_add = seen.add return [x for x in seq if not (x in seen or seen_add(x))] import random # no duplicates lst = [random.random() for _ in range(10000)] # ordered by: fastest to slowest %timeit list(unique_everseen(lst)) # 100 loops, best of 3: 4.51 ms per loop %timeit f7(lst) # 100 loops, best of 3: 8.68 ms per loop %timeit list(more_itertools_unique_everseen(lst)) # 100 loops, best of 3: 10 ms per loop %timeit list(OrderedDict.fromkeys(lst)) # 100 loops, best of 3: 11.7 ms per loop # more duplicates lst = [random.randint(0, 500) for _ in range(10000)] %timeit list(unique_everseen(lst)) # 1000 loops, best of 3: 1.38 ms per loop %timeit f7(lst) # 100 loops, best of 3: 1.96 ms per loop %timeit list(OrderedDict.fromkeys(lst)) # 1000 loops, best of 3: 1.98 ms per loop %timeit list(more_itertools_unique_everseen(lst)) # 100 loops, best of 3: 2.29 ms per loop 

这个(generator-)函数还可以处理input中不可取的值(当O(n*n)性能,而不是O(n)性能,当值可哈希)。

 >>> lst = [{1}, {1}, {2}, {1}, {3}] >>> list(unique_everseen(lst)) [{1}, {2}, {3}] 

1免责声明:我是该软件包的作者。

不要踢死马(这个问题已经很老了,已经有很多很好的答案了),但是这里有一个使用pandas的解决scheme,在很多情况下这个解决scheme相当快,而且使用简单。

 import pandas as pd my_list = range(5) + range(5) # [0, 1, 2, 3, 4, 0, 1, 2, 3, 4] >>> pd.Series(my_list).drop_duplicates().tolist() # Output: # [0, 1, 2, 3, 4] 

借用用于定义Haskell列表的nub函数的recursion思想,这将是一个recursion的方法:

 def unique(lst): return [] if lst==[] else [lst[0]] + unique(filter(lambda x: x!= lst[0], lst[1:])) 

例如:

 In [118]: unique([1,5,1,1,4,3,4]) Out[118]: [1, 5, 4, 3] 

我试图扩大数据大小,并看到亚线性时间复杂性(不确定,但build议这应该是正常的数据罚款)。

 In [122]: %timeit unique(np.random.randint(5, size=(1))) 10000 loops, best of 3: 25.3 us per loop In [123]: %timeit unique(np.random.randint(5, size=(10))) 10000 loops, best of 3: 42.9 us per loop In [124]: %timeit unique(np.random.randint(5, size=(100))) 10000 loops, best of 3: 132 us per loop In [125]: %timeit unique(np.random.randint(5, size=(1000))) 1000 loops, best of 3: 1.05 ms per loop In [126]: %timeit unique(np.random.randint(5, size=(10000))) 100 loops, best of 3: 11 ms per loop 

我也觉得有趣的是,这可以通过其他操作简单地归结为唯一性。 喜欢这个:

 import operator def unique(lst, cmp_op=operator.ne): return [] if lst==[] else [lst[0]] + unique(filter(lambda x: cmp_op(x, lst[0]), lst[1:]), cmp_op) 

例如,为了唯一性的目的,你可以传入一个函数,使用四舍五入的概念到相同的整数,就像它是“相等的”一样,如下所示:

 def test_round(x,y): return round(x) != round(y) 

那么unique(some_list,test_round)将提供列表中唯一的元素,其中唯一性不再意味着传统的平等(这是通过使用任何types的基于集合或基于字典的方法来解决这个问题),而是意味着只有第一个元素可以四舍五入到K的每个可能的整数K元素可能舍去,例如:

 In [6]: unique([1.2, 5, 1.9, 1.1, 4.2, 3, 4.8], test_round) Out[6]: [1.2, 5, 1.9, 4.2, 3] 

你可以做一个丑陋的列表理解黑客。

 [l[i] for i in range(len(l)) if l.index(l[i]) == i] 
 l = [1,2,2,3,3,...] n = [] n.extend(ele for ele in l if ele not in set(n)) 

一个生成器expression式,使用集合的O(1)查找来确定是否在新列表中包含一个元素。

MizardX的答案提供了多种方法的好集合。

这就是我在大声思考的时候想到的:

 mylist = [x for i,x in enumerate(mylist) if x not in mylist[i+1:]] 

_sorted_一个numpy数组比较有效的方法:

 b = np.array([1,3,3, 8, 12, 12,12]) numpy.hstack([b[0], [x[0] for x in zip(b[1:], b[:-1]) if x[0]!=x[1]]]) 

输出:

 array([ 1, 3, 8, 12]) 

一个简单的recursion解决scheme:

 def uniquefy_list(a): return uniquefy_list(a[1:]) if a[0] in a[1:] else [a[0]]+uniquefy_list(a[1:]) if len(a)>1 else [a[0]] 

如果你需要一个class轮,那么也许这将有助于:

 reduce(lambda x, y: x + y if y[0] not in x else x, map(lambda x: [x],lst)) 

…应该工作,但纠正我,如果我错了

这很快,但…

 l = list(set(l)) 

…如果你的列表项不可哈希,那么它就不起作用。

更通用的方法是:

 l = reduce(lambda x, y: x if y in x else x + [y], l, []) 

它应该适用于所有情况。

在列表中popup副本,并在源列表中保持唯一:

 >>> list1 = [ 1,1,2,2,3,3 ] >>> [ list1.pop(i) for i in range(len(list1))[::-1] if list1.count(list1[i]) > 1 ] [1, 2, 3] 

我用[::-1]按相反顺序读取列表。

如果您的情况允许,您可以考虑在加载时删除重复项:

假设你有一个循环引入数据并使用list1.append(item)…

 list1 = [0, 2, 4, 9] for x in range(0, 7): list1.append(x) 

这给了你一些重复:[0,2,4,9,0,1,2,3,4,5,6]

但是,如果你做到了:

 list1 = [0, 2, 4, 9] for x in range(0, 7) if x not in list1: list1.append(x) 

你没有得到重复,顺序被保留:[0,2,4,9,1,3,5,6]

因为我正在查看一个副本,并收集了一些不相关的,相关的,有用的信息,而这些信息并不是其他答案的一部分,所以这里有两个可能的解决scheme。

.get(True)XOR .setdefault(False)

第一个非常类似于接受的seen_add但使用字典的get(x,<default>)setdefault(x,<default>)显式的副作用:

 # Explanation of d.get(x,True) != d.setdefault(x,False) # # x in d | d[x] | A = d.get(x,True) | x in d | B = d.setdefault(x,False) | x in d | d[x] | A xor B # False | None | True (1) | False | False (2) | True | False | True # True | False | False (3) | True | False (4) | True | False | False # # Notes # (1) x is not in the dictionary, so get(x,<default>) returns True but does __not__ add the value to the dictionary # (2) x is not in the dictionary, so setdefault(x,<default>) adds the {x:False} and returns False # (3) since x is in the dictionary, the <default> argument is ignored, and the value of the key is returned, which was # set to False in (2) # (4) since the key is already in the dictionary, its value is returned directly and the argument is ignored # # A != B is how to do boolean XOR in Python # def sort_with_order(s): d = dict() return [x for x in s if d.get(x,True) != d.setdefault(x,False)] 

如果x不在字典中, get(x,<default>)将返回<default> ,但不会将该字符添加到字典中。 set(x,<default>)返回值,如果键在字典中,否则将其设置为并返回<default>

另外: a != b是如何在python中执行异或操作

__OVERRIDING ___missing_____(受此答案启发)

第二种方法是覆盖当密钥不存在于字典中时被调用的__missing__方法,该字典仅在使用d[k]表示法时被调用:

 class Tracker(dict): # returns True if missing, otherwise sets the value to False # so next time d[key] is called, the value False will be returned # and __missing__ will not be called again def __missing__(self, key): self[key] = False return True t = Tracker() unique_with_order = [x for x in samples if t[x]] 

从文档 :

2.5版本中的新增function:如果dict的子类定义了缺less_____()的方法,如果键值不存在,则d [key]操作使用键值作为参数调用该方法。 然后,d [key]操作返回或提出由_____缺less的_____(key)调用返回或引发的任何操作,如果该键不存在的话。 没有其他操作或方法援引_____缺less_____()。 如果_____缺less_____()未定义,则引发KeyError。 _____缺less_____()必须是一种方法; 它不能是一个实例variables。 有关示例,请参阅collections.defaultdict。

这是一个O(N 2 )recursion版本的乐趣:

 def uniquify(s): if len(s) < 2: return s return uniquify(s[:-1]) + [s[-1]] * (s[-1] not in s[:-1]) 

如果你经常使用pandas ,而美学比性能更pandas.Series.drop_duplicates ,那么考虑内置函数pandas.Series.drop_duplicates

  import pandas as pd import numpy as np uniquifier = lambda alist: pd.Series(alist).drop_duplicates().tolist() # from the chosen answer def f7(seq): seen = set() seen_add = seen.add return [ x for x in seq if not (x in seen or seen_add(x))] alist = np.random.randint(low=0, high=1000, size=10000).tolist() print uniquifier(alist) == f7(alist) # True 

定时:

  In [104]: %timeit f7(alist) 1000 loops, best of 3: 1.3 ms per loop In [110]: %timeit uniquifier(alist) 100 loops, best of 3: 4.39 ms per loop 

这将保持顺序并在O(n)时间运行。 基本上这个想法是在发现重复的地方创build一个洞,然后将其下沉到底部。 利用读写指针。 每当发现重复时,只有读指针前进,写指针停留在重复条目上以覆盖它。

 def deduplicate(l): count = {} (read,write) = (0,0) while read < len(l): if l[read] in count: read += 1 continue count[l[read]] = True l[write] = l[read] read += 1 write += 1 return l[0:write] 

不使用导入的模块或设置的解决scheme:

 text = "ask not what your country can do for you ask what you can do for your country" sentence = text.split(" ") noduplicates = [(sentence[i]) for i in range (0,len(sentence)) if sentence[i] not in sentence[:i]] print(noduplicates) 

给出输出:

 ['ask', 'not', 'what', 'your', 'country', 'can', 'do', 'for', 'you'] 

这是我的2美分:

 def unique(nums): unique = [] for n in nums: if n not in unique: unique.append(n) return unique 

问候,尤里

这是聪明的方式来从Python列表中删除重复项,同时保留其顺序,你甚至可以在一行代码中完成:

 a_list = ["a", "b", "a", "c"] sorted_list = [x[0] for x in (sorted({x:a_list.index(x) for x in set(a_list)}.items(), key=lambda x: x[1]))] print sorted_list 

我的好友韦斯用列表parsing给了我这个甜蜜的回答。

示例代码:

 >>> l = [3, 4, 3, 6, 4, 1, 4, 8] >>> l = [l[i] for i in range(len(l)) if i == l.index(l[i])] >>> l = [3, 4, 6, 1, 8]