是否有一个内置程序可以从 Python 中的列表中删除重复项,同时保留顺序?我知道我可以使用集合来删除重复项,但这会破坏原始顺序。我也知道我可以像这样滚动自己:
def uniq(input):
output = []
for x in input:
if x not in output:
output.append(x)
return output
但如果可能的话,我想利用一个内置的或更 Pythonic 的习语。
是否有一个内置程序可以从 Python 中的列表中删除重复项,同时保留顺序?我知道我可以使用集合来删除重复项,但这会破坏原始顺序。我也知道我可以像这样滚动自己:
def uniq(input):
output = []
for x in input:
if x not in output:
output.append(x)
return output
但如果可能的话,我想利用一个内置的或更 Pythonic 的习语。
在这里你有一些选择: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.add
给seen_add
而不是仅仅调用seen.add
?Python 是一种动态语言,解析seen.add
每次迭代比解析局部变量的成本更高。seen.add
可能在迭代之间发生了变化,并且运行时还不够聪明,无法排除这种情况。为了安全起见,它必须每次都检查对象。
如果您计划在同一个数据集上大量使用此函数,那么使用有序集可能会更好:http: //code.activestate.com/recipes/528878/
O (1) 每个操作的插入、删除和成员检查。
(补充一点:seen.add()
总是返回None
,所以or
上面的内容只是作为尝试更新集合的一种方式,而不是作为逻辑测试的一个组成部分。)
最佳解决方案因 Python 版本和环境限制而异:
在 PyPy 2.5.0 中首次引入,并在 CPython 3.6 中作为实现细节采用,在 Python 3.7 中成为语言保证之前,plaindict
是插入顺序的,甚至比 (也是 CPython 3.5 实现的 C) 更有效collections.OrderedDict
。因此,到目前为止,最快的解决方案也是最简单的:
>>> items = [1, 2, 0, 1, 3, 2]
>>> list(dict.fromkeys(items)) # Or [*dict.fromkeys(items)] if you prefer
[1, 2, 0, 3]
像list(set(items))
这样将所有工作推到 C 层(在 CPython 上),但由于dict
s 是插入排序的,dict.fromkeys
因此不会丢失排序。它比list(set(items))
(通常需要 50-100% 的时间)慢,但比任何其他保留顺序的解决方案要快得多(大约需要在 listcomp中使用 s 的黑客set
时间的一半)。
重要提示:(见下文)的unique_everseen
解决方案more_itertools
在惰性和支持不可散列的输入项方面具有一些独特的优势;如果您需要这些功能,这是唯一可行的解决方案。
正如 Raymond指出的那样,在用 C 实现的 CPython 3.5 中OrderedDict
,丑陋的列表理解黑客比OrderedDict.fromkeys
(除非您实际上需要最后的列表 - 即便如此,只有当输入非常短时)。因此,在性能和可读性方面,CPython 3.5 的最佳解决方案OrderedDict
相当于 3.6+ 使用 plain dict
:
>>> from collections import OrderedDict
>>> items = [1, 2, 0, 1, 3, 2]
>>> list(OrderedDict.fromkeys(items))
[1, 2, 0, 3]
在 CPython 3.4 及更早版本上,这将比其他一些解决方案慢,因此如果分析表明您需要更好的解决方案,请继续阅读。
正如@abarnert 所指出的,more_itertools
库 ( pip install more_itertools
) 包含一个unique_everseen
用于解决此问题的函数,而列表解析中没有任何不可读的( not seen.add
)突变。这也是最快的解决方案:
>>> 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') --> A B C D
# unique_everseen('ABBCcAD', str.lower) --> A B C D
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
但与itertools
配方不同的是,它支持不可散列的项目(以性能为代价;如果其中的所有元素iterable
都是不可散列的,则算法变为O(n²)
,而O(n)
如果它们都是可散列的)。
重要说明:与这里的所有其他解决方案不同,unique_everseen
可以懒惰地使用;峰值内存使用量将是相同的(最终,底层set
增长到相同的大小),但如果您不确定list
结果,您只需对其进行迭代,您将能够处理发现的独特项目,而不是等到整个输入都被删除后才处理第一个唯一项目。
你有两个选择:
将unique_everseen
配方复制并粘贴到您的代码中,并按照more_itertools
上面的示例使用它
使用丑陋的 hack 允许单个 listcomp 检查和更新 aset
以跟踪所看到的内容:
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
.
请注意,上述所有解决方案都是O(n)
(除了调用unique_everseen
不可散列项的可迭代项,即O(n²)
,而其他解决方案会立即失败 a TypeError
),因此当它们不是最热门的代码路径时,所有解决方案都具有足够的性能。使用哪一个取决于您可以依赖的语言规范/解释器/第三方模块的版本,性能是否至关重要(不要假设它是关键;通常不是),最重要的是可读性(因为如果维护此代码的人后来陷入了杀气,那么您聪明的微优化可能不值得)。
在 CPython 3.6+ (以及从Python 3.7+开始的所有其他 Python 实现)中,字典是有序的,因此从可迭代对象中删除重复项同时保持其原始顺序的方法是:
>>> list(dict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']
在 Python 3.5及更低版本(包括Python 2.7)中,使用OrderedDict
. 我的时间安排表明,这现在是 Python 3.5 各种方法中最快和最短的方法(当它获得 C 实现时;在 3.5 之前,它仍然是最清晰的解决方案,尽管不是最快的)。
>>> from collections import OrderedDict
>>> list(OrderedDict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']
不要踢死马(这个问题很老,已经有很多好的答案),但这里有一个使用 pandas 的解决方案,它在许多情况下都非常快,而且使用起来非常简单。
import pandas as pd
my_list = [0, 1, 2, 3, 4, 1, 2, 3, 5]
>>> pd.Series(my_list).drop_duplicates().tolist()
# Output:
# [0, 1, 2, 3, 4, 5]
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)]
列表甚至不必排序,充分条件是相等的值被组合在一起。
编辑:我假设“保留顺序”意味着列表实际上是有序的。如果不是这种情况,那么 MizardX 的解决方案就是正确的。
社区编辑:然而,这是“将重复的连续元素压缩为单个元素”的最优雅的方式。
我想如果你想维持秩序,
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
只是为了从外部模块添加另一个(非常高效的)实现这种功能1 : 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.6),这些表明它比我测试的所有其他替代方案更快,OrderedDict.fromkeys
包括f7
和more_itertools.unique_everseen
:
%matplotlib notebook
from iteration_utilities import unique_everseen
from collections import OrderedDict
from more_itertools import unique_everseen as mi_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))]
def iteration_utilities_unique_everseen(seq):
return list(unique_everseen(seq))
def more_itertools_unique_everseen(seq):
return list(mi_unique_everseen(seq))
def odict(seq):
return list(OrderedDict.fromkeys(seq))
from simple_benchmark import benchmark
b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
{2**i: list(range(2**i)) for i in range(1, 20)},
'list size (no duplicates)')
b.plot()
并且只是为了确保我还进行了更多重复的测试,以检查它是否有所作为:
import random
b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
{2**i: [random.randint(0, 2**(i-1)) for _ in range(2**i)] for i in range(1, 20)},
'list size (lots of duplicates)')
b.plot()
一个只包含一个值:
b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
{2**i: [1]*(2**i) for i in range(1, 20)},
'list size (only duplicates)')
b.plot()
在所有这些情况下,该iteration_utilities.unique_everseen
功能是最快的(在我的计算机上)。
此iteration_utilities.unique_everseen
函数还可以处理输入中不可散列的值(但是,当值是可散列时,具有O(n*n)
性能而不是性能)。O(n)
>>> lst = [{1}, {1}, {2}, {1}, {3}]
>>> list(unique_everseen(lst))
[{1}, {2}, {3}]
1免责声明:我是该软件包的作者。
对于另一个非常古老的问题的另一个很晚的答案:
itertools
食谱有一个功能可以做到这一点,使用setseen
技术,但是:
key
函数。seen.add
而不是查找 N 次来优化循环。(f7
也这样做,但有些版本没有。)ifilterfalse
,因此您只需遍历 Python 中的唯一元素,而不是所有元素。(当然,你仍然在里面遍历所有这些ifilterfalse
,但那是在 C 中,而且要快得多。)它实际上比 快f7
吗?这取决于您的数据,因此您必须对其进行测试并查看。如果你最后想要一个列表,请f7
使用 listcomp,这里没有办法做到这一点。(您可以直接append
而不是yield
ing,或者您可以将生成器输入到list
函数中,但是两者都不能像 listcomp 中的 LIST_APPEND 一样快。)无论如何,通常挤出几微秒不会像重要的是拥有一个易于理解、可重用、已经编写好的函数,当你想要装饰时不需要 DSU。
与所有食谱一样,它也可以在more-iterools
.
如果您只想要 no- key
case,您可以将其简化为:
def unique(iterable):
seen = set()
seen_add = seen.add
for element in itertools.ifilterfalse(seen.__contains__, iterable):
seen_add(element)
yield element
对于基于 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 倍,但更复杂
>>> 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]
这是一个简单的方法:
list1 = ["hello", " ", "w", "o", "r", "l", "d"]
sorted(set(list1 ), key=list1.index)
这给出了输出:
["hello", " ", "w", "o", "r", "l", "d"]
熊猫用户应该检查一下pandas.unique
。
>>> import pandas as pd
>>> lst = [1, 2, 1, 3, 3, 2, 4]
>>> pd.unique(lst)
array([1, 2, 3, 4])
该函数返回一个 NumPy 数组。如果需要,您可以使用该tolist
方法将其转换为列表。
您可以引用一个列表推导,因为它是由符号“_[1]”构建的。
例如,以下函数通过引用其列表推导来唯一化一个元素列表而不改变它们的顺序。
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]
借用在定义 Haskell 的nub
列表函数时使用的递归思想,这将是一种递归方法:
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]
我尝试使用它来增加数据大小并看到亚线性时间复杂度(不是确定的,但建议这对于正常数据应该没问题)。
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) 将提供列表的唯一元素,其中唯一性不再意味着传统的相等性(这是通过使用任何类型的基于集合或基于字典键的方法来解决这个问题)而是意味着采取对于元素可能舍入到的每个可能的整数 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]
如果您需要一个班轮,那么这可能会有所帮助:
reduce(lambda x, y: x + y if y[0] not in x else x, map(lambda x: [x],lst))
...应该可以,但如果我错了,请纠正我
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])
你可以做一种丑陋的列表理解黑客。
[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))
使用 O(1) 查找集合来确定是否在新列表中包含元素的生成器表达式。
一个简单的递归解决方案:
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]]
消除序列中的重复值,但保留剩余项目的顺序。使用通用生成器功能。
# for hashable sequence
def remove_duplicates(items):
seen = set()
for item in items:
if item not in seen:
yield item
seen.add(item)
a = [1, 5, 2, 1, 9, 1, 5, 10]
list(remove_duplicates(a))
# [1, 5, 2, 9, 10]
# for unhashable sequence
def remove_duplicates(items, key=None):
seen = set()
for item in items:
val = item if key is None else key(item)
if val not in seen:
yield item
seen.add(val)
a = [ {'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 1, 'y': 2}, {'x': 2, 'y': 4}]
list(remove_duplicates(a, key=lambda d: (d['x'],d['y'])))
# [{'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 2, 'y': 4}]
一个班轮列表理解:
values_non_duplicated = [value for index, value in enumerate(values) if value not in values[ : index]]
x = [1, 2, 1, 3, 1, 4]
# brute force method
arr = []
for i in x:
if not i in arr:
arr.insert(x[i],i)
# recursive method
tmp = []
def remove_duplicates(j=0):
if j < len(x):
if not x[j] in tmp:
tmp.append(x[j])
i = j+1
remove_duplicates(i)
remove_duplicates()
如果您经常使用pandas
,并且美观优于性能,请考虑内置函数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) 时间内运行。基本上这个想法是在找到重复的地方创建一个洞并将其沉入底部。使用读写指针。每当找到重复项时,只有读取指针前进,而写入指针停留在重复项上以覆盖它。
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]
不使用导入模块或集合的解决方案:
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']
这种方法是二次的,因为我们对列表中的每个元素都进行了线性查找(为此,我们必须加上重新排列列表的成本,因为del
s)。
也就是说,如果我们从列表的末尾开始向原点前进,删除其左侧子列表中存在的每个术语,则可以就地操作
代码中的这个想法很简单
for i in range(len(l)-1,0,-1):
if l[i] in l[:i]: del l[i]
一个简单的实现测试
In [91]: from random import randint, seed
In [92]: seed('20080808') ; l = [randint(1,6) for _ in range(12)] # Beijing Olympics
In [93]: for i in range(len(l)-1,0,-1):
...: print(l)
...: print(i, l[i], l[:i], end='')
...: if l[i] in l[:i]:
...: print( ': remove', l[i])
...: del l[i]
...: else:
...: print()
...: print(l)
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5, 2]
11 2 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5]: remove 2
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5]
10 5 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4]: remove 5
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4]
9 4 [6, 5, 1, 4, 6, 1, 6, 2, 2]: remove 4
[6, 5, 1, 4, 6, 1, 6, 2, 2]
8 2 [6, 5, 1, 4, 6, 1, 6, 2]: remove 2
[6, 5, 1, 4, 6, 1, 6, 2]
7 2 [6, 5, 1, 4, 6, 1, 6]
[6, 5, 1, 4, 6, 1, 6, 2]
6 6 [6, 5, 1, 4, 6, 1]: remove 6
[6, 5, 1, 4, 6, 1, 2]
5 1 [6, 5, 1, 4, 6]: remove 1
[6, 5, 1, 4, 6, 2]
4 6 [6, 5, 1, 4]: remove 6
[6, 5, 1, 4, 2]
3 4 [6, 5, 1]
[6, 5, 1, 4, 2]
2 1 [6, 5]
[6, 5, 1, 4, 2]
1 5 [6]
[6, 5, 1, 4, 2]
In [94]:
zmk 的方法使用非常快的列表理解,但自然保持顺序。为了应用于区分大小写的字符串,它可以很容易地修改。这也保留了原始案例。
def DelDupes(aseq) :
seen = set()
return [x for x in aseq if (x.lower() not in seen) and (not seen.add(x.lower()))]
密切相关的功能是:
def HasDupes(aseq) :
s = set()
return any(((x.lower() in s) or s.add(x.lower())) for x in aseq)
def GetDupes(aseq) :
s = set()
return set(x for x in aseq if ((x.lower() in s) or s.add(x.lower())))
感谢@wjandrea 的 dict.fromdict 方法理念:
def solve(arr):
return list(dict.fromkeys(arr[::-1]))[::-1]
这将反转输入和输出以正确迭代
def remove_duplicates_thenSort():
t = ['b', 'c', 'd','d','a','c','c']
t2 = []
for i,k in enumerate(t):
index = t.index(k)
if i == index:
t2.append(t[i])
return sorted(t2)
print(remove_duplicates_thenSort())