我有一个列表,我正试图从中删除重复项。我使用的是python 2.7.1,所以我可以简单地使用set()函数。然而,这会重新排列我的列表。对于我的特殊情况来说,这是不可接受的。
下面是我写的一个函数;这样做。然而,我想知道是否有更好/更快的方法。此外,如有任何评论,我们将不胜感激。
def ordered_set(list_):
newlist = []
lastitem = None
for item in list_:
if item != lastitem:
newlist.append(item)
lastitem = item
return newlist
上面的函数假设没有一个项目是无,并且这些项目是有序的(即[‘a’,‘a’、‘a’’、‘b’,‘b’、‘c’、‘d’])
上面的函数返回[‘a’,‘a’、‘a’’、‘b’,‘b’、‘c’、‘d’]为[‘a‘,‘b‘,‘c’,‘d’]。
另一个非常快速的方法与集合:
def remove_duplicates(lst):
dset = set()
# relies on the fact that dset.add() always returns None.
return [item for item in lst
if item not in dset and not dset.add(item)]
使用OrderedDict:
from collections import OrderedDict
l = ['a', 'a', 'a', 'b', 'b', 'c', 'd']
d = OrderedDict()
for x in l:
d[x] = True
# prints a b c d
for x in d:
print x,
print
假设输入序列是无序的,这里是O(N)
解决方案(在空间和时间上)。它生成一个删除了重复项的序列,同时保留与输入序列中出现的项目相同的相对顺序的唯一项目。
>>> def remove_dups_stable(s):
... seen = set()
... for i in s:
... if i not in seen:
... yield i
... seen.add(i)
>>> list(remove_dups_stable(['q', 'w', 'e', 'r', 'q', 'w', 'y', 'u', 'i', 't', 'e', 'p', 't', 'y', 'e']))
['q', 'w', 'e', 'r', 'y', 'u', 'i', 't', 'p']
我知道这个问题已经得到了回答,但这里有一句话(加上导入):
from collections import OrderedDict
def dedupe(_list):
return OrderedDict((item,None) for item in _list).keys()
>>> dedupe(['q', 'w', 'e', 'r', 'q', 'w', 'y', 'u', 'i', 't', 'e', 'p', 't', 'y', 'e'])
['q', 'w', 'e', 'r', 'y', 'u', 'i', 't', 'p']
我认为这完全可以。您可以获得O(n)性能,这是您所希望的最好性能。
如果列表是无序的,那么您需要一个助手set
来包含您已经访问过的项目,但在您的情况下,这是不必要的。
如果你的列表没有排序,那么你的问题就没有意义了。例如[1,2,1]可能变成[1,2]或[2,1]
如果您的列表很大,您可能希望使用SLICE将结果写回同一列表以节省内存:
>>> x=['a', 'a', 'a', 'b', 'b', 'c', 'd']
>>> x[:]=[x[i] for i in range(len(x)) if i==0 or x[i]!=x[i-1]]
>>> x
['a', 'b', 'c', 'd']
有关内联删除,请参阅在Python 中,在迭代时从列表中删除项目或在不使用额外内存的情况下迭代时从名单中删除项目
你可以使用的一个技巧是,如果你知道x是排序的,并且你知道x[i]=x[i+j],那么你就不需要检查x[i]和x[i+j]之间的任何东西(如果你不需要删除这些j值,你可以把你想要的值复制到一个新的列表中)
因此,如果集合中的所有内容都是唯一的,即len(set(x))=len(x),则不能击败n个运算可能有一种算法将n个比较作为最坏情况,但可以将n/2个比较作为最佳情况(或者,如果您知道由于您生成的数据,len(x)/len(set(x))>2,则低于n/2作为最佳情况):
最优算法可能使用二进制搜索来在分治型方法中为每个最小值i找到最大值j。初始除法的长度可能是len(x)/近似值(len(set(x)))。希望它可以这样执行,即使len(x)=len(set(x)),它仍然只使用n个运算。
中描述了unique_everseed解决方案http://docs.python.org/2/library/itertools.html
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 ifilterfalse(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
我觉得不错。如果你真的想使用集合,可以这样做:
def ordered_set (_list) :
result = set()
lastitem = None
for item in _list :
if item != lastitem :
result.add(item)
lastitem = item
return sorted(tuple(result))
我不知道你会得到什么样的表现,你应该测试一下;可能是因为方法过热!
如果你真的像我一样偏执,请阅读这里:
http://wiki.python.org/moin/HowTo/Sorting/
http://wiki.python.org/moin/PythonSpeed/PerformanceTips
只是记住了这个(它包含了答案):
http://www.peterbe.com/plog/uniqifiers-benchmark