在Python中，从列表中删除重复项以使所有元素在保持顺序时都是唯一的最快的算法是什么？
例如：
>>> x = [1, 1, 2, 'a', 'a', 3] >>> unique(x) [1, 2, 'a', 3]
假设列表元素是可哈希的。
澄清：结果应保留列表中的第一个重复项。例如，[1、2、3、2、3、1]变为[1、2、3]。
解决方案
我没有使用python的经验，但是一种算法是对列表进行排序，然后删除重复项(通过与列表中的先前项目进行比较)，最后通过与旧列表进行比较在新列表中找到位置。
更长的答案：http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52560
我没有做任何测试，但是一个可能的算法可能是创建第二个列表，并遍历第一个列表。如果某个项目不在第二个列表中，则将其添加到第二个列表中。
x = [1, 1, 2, 'a', 'a', 3]
y = []
for each in x:
if each not in y:
y.append(each)
取自http://www.peterbe.com/plog/uniqifiers-benchmark
def f5(seq, idfun=None):
# order preserving
if idfun is None:
def idfun(x): return x
seen = {}
result = []
for item in seq:
marker = idfun(item)
# in old Python versions:
# if seen.has_key(marker)
# but in new ones:
if marker in seen: continue
seen[marker] = 1
result.append(item)
return result
>>> def unique(list): ... y = [] ... for x in list: ... if x not in y: ... y.append(x) ... return y
最快的速度取决于列表中重复项的百分比。如果几乎是所有重复项，而唯一项很少，则创建新列表的速度可能会更快。如果大部分都是独特的商品，则将它们从原始列表(或者副本)中删除会更快。
这是一个用于修改列表的地方：
def unique(items):
seen = set()
for i in xrange(len(items)-1, -1, -1):
it = items[i]
if it in seen:
del items[i]
else:
seen.add(it)
向后迭代索引可确保删除项目不会影响迭代。
如果dict是散列，则为O(n)；如果dict是树，则为O(nlogn)，并且简单，固定。感谢马修的建议。抱歉，我不知道底层类型。
def unique(x):
output = []
y = {}
for item in x:
y[item] = ""
for item in x:
if item in y:
output.append(item)
return output
def unique(items):
found = set([])
keep = []
for item in items:
if item not in found:
found.add(item)
keep.append(item)
return keep
print unique([1, 1, 2, 'a', 'a', 3])
我们实际上可以在Python中做一些很酷的事情来解决这个问题。我们可以创建一个列表推导，该列表推导将在构建列表时对其进行引用。如下：
# remove duplicates...
def unique(my_list):
return [x for x in my_list if x not in locals()['_[1]'].__self__]
编辑：我删除了"自我"，它可以在Mac OS X，Python 2.5.1上工作。
_ [1]是Python对新列表的"秘密"引用。上面的内容当然有点混乱，但是我们可以根据需要对其进行调整。例如，我们实际上可以编写一个返回对理解的引用的函数。它看起来更像是：
return [x for x in my_list if x not in this_list()]
>>> x=[1,1,2,'a','a',3] >>> y = [ _x for _x in x if not _x in locals()['_[1]'] ] >>> y [1, 2, 'a', 3]
" locals()['_ [1]']"是所创建列表的"秘密名称"。
单线：
new_list = reduce(lambda x,y: x+[y][:1-int(y in x)], my_list, [])
重复项是否一定必须首先位于列表中？就查找元素而言，没有任何开销，但是添加元素要多一点开销(尽管开销应该是O(1))。
>>> x = [] >>> y = set() >>> def add_to_x(val): ... if val not in y: ... x.append(val) ... y.add(val) ... print x ... print y ... >>> add_to_x(1) [1] set([1]) >>> add_to_x(1) [1] set([1]) >>> add_to_x(1) [1] set([1]) >>>
python中的has_key是O(1)。从哈希中插入和检索也是O(1)。循环遍历n个项目两次，所以O(n)。
def unique(list):
s = {}
output = []
for x in list:
count = 1
if(s.has_key(x)):
count = s[x] + 1
s[x] = count
for x in list:
count = s[x]
if(count > 0):
s[x] = 0
output.append(x)
return output
一通。
a = [1,1,'a','b','c','c']
new_list = []
prev = None
while 1:
try:
i = a.pop(0)
if i != prev:
new_list.append(i)
prev = i
except IndexError:
break
使用：
lst = [8, 8, 9, 9, 7, 15, 15, 2, 20, 13, 2, 24, 6, 11, 7, 12, 4, 10, 18, 13, 23, 11, 3, 11, 12, 10, 4, 5, 4, 22, 6, 3, 19, 14, 21, 11, 1, 5, 14, 8, 0, 1, 16, 5, 10, 13, 17, 1, 16, 17, 12, 6, 10, 0, 3, 9, 9, 3, 7, 7, 6, 6, 7, 5, 14, 18, 12, 19, 2, 8, 9, 0, 8, 4, 5]
并使用timeit模块：
$ python -m timeit -s 'import uniquetest' 'uniquetest.etchasketch(uniquetest.lst)'
依此类推，对于其他各种功能(我以其发布者的名字命名)，我得到了以下结果(在我的第一代Intel MacBook Pro上)：
Allen: 14.6 μs per loop [1] Terhorst: 26.6 μs per loop Tarle: 44.7 μs per loop ctcherry: 44.8 μs per loop Etchasketch 1 (short): 64.6 μs per loop Schinckel: 65.0 μs per loop Etchasketch 2: 71.6 μs per loop Little: 89.4 μs per loop Tyler: 179.0 μs per loop
[1]请注意，艾伦(Allen)修改了列表，我相信这会浪费时间，因为timeit模块运行代码100000次，其中99999次使用无重复列表。
简介：带集合的直接实现克服了令人困惑的单行代码：-)
我不知道这是不是很快，但至少很简单。
只需将其首先转换为集合，然后再转换为列表
def unique(container): return list(set(container))
这是我发现的最快的就地方法(假设有大量重复项)：
def unique(l):
s = set(); n = 0
for x in l:
if x not in s: s.add(x); l[n] = x; n += 1
del l[n:]
这比基于Allen的实现快10％(由psyco编译的JIT timeit.repeat计时)。它保留所有重复项的第一个实例。
repton-infinity：如果我们能确定我的时间安排，我很感兴趣。
这里有一些很棒的，有效的解决方案。但是，对于不关心绝对最有效的O(n)解决方案的任何人，我都会使用简单的单线O(n ^ 2 * log(n))解决方案：
def unique(xs):
return sorted(set(xs), key=lambda x: xs.index(x))
或者更有效的两层O(n * log(n))解决方案：
def unique(xs):
positions = dict((e,pos) for pos,e in reversed(list(enumerate(xs))))
return sorted(set(xs), key=lambda x: positions[x])
如果从Terhost的答案中的set()调用中删除空列表，则速度会有所提高。
改变：
找到=设置([])
到：
找到= set()
但是，我们根本不需要设置。
def unique(items):
keep = []
for item in items:
if item not in keep:
keep.append(item)
return keep
使用timeit我得到了以下结果：
与set([])-4.97210427363
与set()-4.65712377445
没有设置-3.44865284975
基于强制生成器的变体：
def unique(seq):
seen = set()
for x in seq:
if x not in seen:
seen.add(x)
yield x
a = [1,2,3,4,5,7,7,8,8,9,9,3,45]
def unique(l)：
ids={}
for item in l:
if not ids.has_key(item):
ids[item]=item
return ids.keys()
打印一个
打印独特的
插入元素将采用theta(n)
检索元素是否退出将花费固定时间
测试所有项目也将花费theta(n)
因此我们可以看到该解决方案将采用theta(n)
注意哈希表在python中实现的字典
这是迄今为止最快的解决方案(对于以下输入)：
def del_dups(seq):
seen = {}
pos = 0
for item in seq:
if item not in seen:
seen[item] = True
seq[pos] = item
pos += 1
del seq[pos:]
lst = [8, 8, 9, 9, 7, 15, 15, 2, 20, 13, 2, 24, 6, 11, 7, 12, 4, 10, 18,
13, 23, 11, 3, 11, 12, 10, 4, 5, 4, 22, 6, 3, 19, 14, 21, 11, 1,
5, 14, 8, 0, 1, 16, 5, 10, 13, 17, 1, 16, 17, 12, 6, 10, 0, 3, 9,
9, 3, 7, 7, 6, 6, 7, 5, 14, 18, 12, 19, 2, 8, 9, 0, 8, 4, 5]
del_dups(lst)
print(lst)
# -> [8, 9, 7, 15, 2, 20, 13, 24, 6, 11, 12, 4, 10, 18, 23, 3, 5, 22, 19, 14,
# 21, 1, 0, 16, 17]
字典查找比Python 3中的字典查找要快一些。
为此的就地衬板：
>>> x = [1, 1, 2, 'a', 'a', 3] >>> [ item for pos,item in enumerate(x) if x.index(item)==pos ] [1, 2, 'a', 3]
删除重复项并保留顺序：
这是一种快速的2层代码，利用列表理解和字典的内置功能。
x = [1, 1, 2, 'a', 'a', 3]
tmpUniq = {} # temp variable used below
results = [tmpUniq.setdefault(i,i) for i in x if i not in tmpUniq]
print results
[1, 2, 'a', 3]
dict.setdefaults()函数返回值并将其直接添加到列表推导中的temp dict中。使用内置函数和dict的散列将最大程度地提高流程效率。
