在Python中，从列表中删除重复项的最快algorithm是什么，以便所有元素都是唯一的*，同时保持顺序*？
例如：
>>> x = [1, 1, 2, 'a', 'a', 3] >>> unique(x) [1, 2, 'a', 3] 假设列表元素是可散列的。
澄清：结果应该保留在列表中的第一个副本。 例如，[1,2,3,2,3,1]变成[1,2,3]。
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])
使用：
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)'
对于各种其他function（我以他们的海报命名），我有以下结果（在我的第一代英特尔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是无用列表。
简介 ：直接执行套件胜过混乱的单线程:-)
这是迄今为止最快的解决scheme（针对以下input）：
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中的集合稍快。
什么是最快的取决于你的列表是多less百分比重复。 如果它几乎都是重复的，只有less数独特的项目，创build一个新的列表可能会更快。 如果它主要是独特的项目，将它们从原始列表（或副本）中删除会更快。
这里有一个修改列表的地方：
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)
遍历索引向后遍历确保删除项目不会影响迭代。
这是我find的最快的就地方法（假定有大量的重复）：
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％（与timeit.repeat同步，由psyco编译的JIT）。 它保留了任何重复的第一个实例。
repton-infinity：如果你能确认我的时间，我会很感兴趣。
强制性的基于生成器的变体：
def unique(seq): seen = set() for x in seq: if x not in seen: seen.add(x) yield x
这可能是最简单的方法：
list(OrderedDict.fromkeys(iterable))
从Python 3.5开始，OrderedDict现在在C中实现，所以这是现在最短，最干净和最快的。
取自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
一内胆：
new_list = reduce(lambda x,y: x+[y][:1-int(y in x)], my_list, [])
这是一个就地的单线：
>>> x = [1, 1, 2, 'a', 'a', 3] >>> [ item for pos,item in enumerate(x) if x.index(item)==pos ] [1, 2, 'a', 3]
这是最快的一个，比较这个冗长的讨论和这里给出的其他答案的所有内容，指的是这个基准 。 比讨论中的最快函数f8快25％。 感谢David Kirby的想法。
def uniquify(seq): seen = set() seen_add = seen.add return [x for x in seq if x not in seen and not seen_add(x)]
有些时间比较：
$ python uniqifiers_benchmark.py * f8_original 3.76 * uniquify 3.0 * terhorst 5.44 * terhorst_localref 4.08 * del_dups 4.76
你可以在Python中真正做一些很酷的事情来解决这个问题。 您可以创build一个列表理解，它将在build立时引用它自己。 如下：
# 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()]
重复的内容必须首先在列表中吗？ 只要查看元素就没有任何开销，但是添加元素会有一些额外的开销（尽pipe开销应该是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]) >>>
删除重复项并保存顺序：
这是一个快速的2class轮，利用列表理解和字典的内置function。
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中。 使用字典的内置函数和哈希值将使该过程的效率最大化。
O（n）如果字典是散列，O（nlogn）如果字典是树，并且简单，固定。 感谢马修的build议。 对不起，我不知道底层的types。
def unique(x): output = [] y = {} for item in x: y[item] = "" for item in x: if item in y: output.append(item) return output
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
这里有一些非常有效的解决scheme。 然而，对于不关心绝对最有效的O(n)解决scheme的人，我会用简单的单线程O(n^2*log(n))解决scheme：
def unique(xs): return sorted(set(xs), key=lambda x: xs.index(x))
或更有效的双线O(n*log(n))解决scheme：
def unique(xs): positions = dict((e,pos) for pos,e in reversed(list(enumerate(xs)))) return sorted(set(xs), key=lambda x: positions[x])
以下是itertools文档中的两个配方：
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 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 unique_justseen(iterable, key=None): "List unique elements, preserving order. Remember only the element just seen." # unique_justseen('AAAABBBCCDAABBB') --> ABCDAB # unique_justseen('ABBCcAD', str.lower) --> ABCAD return imap(next, imap(itemgetter(1), groupby(iterable, key)))
我没有使用python的经验，但algorithm是sorting列表，然后删除重复项（通过比较列表中的以前的项目），最后通过与旧列表比较find新列表中的位置。
较长的答案： http : //aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52560
>>> def unique(list): ... y = [] ... for x in list: ... if x not in y: ... y.append(x) ... return y
如果你从Terhost的回答中调用set（）中的空列表，你会得到一点速度提升。
更改：found = set（[]）
到：found = set（）
但是，你根本不需要这个设置。
def unique(items): keep = [] for item in items: if item not in keep: keep.append(item) return keep
使用时间我得到了这些结果：
与设置（[]） – 4.97210427363
用set（） – 4.65712377445
没有设置 – 3.44865284975
x = [] # Your list of items that includes Duplicates # Assuming that your list contains items of only immutable data types dict_x = {} dict_x = {item : item for i, item in enumerate(x) if item not in dict_x.keys()} # Average tc = O(n)* O(1) ; furthermore the dict comphrehension and generator like behaviour of enumerate adds a certain efficiency and pythonic feel to it. x = dict_x.keys() # if you want your output in list format
>>> 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]']”是正在创build的列表的“秘密名称”。
我不知道这个是不是很快，但至less很简单。
简单地说，首先将其转换为一个集合，然后再转换为一个列表
def unique(container): return list(set(container))
一通。
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
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）检索如果元素退出或不会需要不断的时间testing所有的项目也将采取theta（n），所以我们可以看到，这个解决scheme将采取theta（n）记住python字典由散列表实现
我没有做任何testing，但是一个可能的algorithm可能是创build第二个列表，并遍历第一个列表。 如果某个项目不在第二个列表中，请将其添加到第二个列表中。
x = [1, 1, 2, 'a', 'a', 3] y = [] for each in x: if each not in y: y.append(each)
