在Python中，去除列表重复元素并保持顺序的最快算法是什么？

Question

举个例子：

>>> x = [1, 1, 2, 'a', 'a', 3]
>>> unique(x)
[1, 2, 'a', 3]

假设列表中的元素是可以进行哈希操作的。

说明：结果应该保留列表中的第一个重复项。比如说，列表 [1, 2, 3, 2, 3, 1] 处理后变成 [1, 2, 3]。

Answer 1

更新: 关于 Python3.7+:

>>> list(dict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']

---

^旧答案：

这是到目前为止最快的解决方案（针对以下输入）：

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 中，查找字典的速度比查找集合稍微快一点。

Answer 2

使用：

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次都是在没有重复项的列表上。

---

总结：简单直接的集合实现比那些让人困惑的单行代码更胜一筹 :-)

Answer 3

在编程中，有时候我们会遇到一些问题，特别是在使用某些工具或库的时候。比如，有人可能在使用一个叫做“库”的东西时，发现它的某些功能不太好用，或者出现了错误。

这时候，我们可以去一个叫做StackOverflow的网站上寻求帮助。这个网站就像一个大论坛，很多程序员会在这里提问和回答问题。你可以把你的问题写上去，然后其他人会给你建议或者解决方案。

在提问的时候，记得把你的问题描述清楚，最好还附上你遇到的错误信息或者代码，这样别人才能更好地理解你的问题，给出有效的帮助。

总之，遇到问题不要怕，去问问别人，很多人都乐意帮忙！

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])