在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

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

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

这是迄今为止最快的解决方案（对于以下输入）：

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中的字典查找要快一些。