Python 2.7 中的有序集合

Question

我有一个列表，想要去掉里面重复的项目。我使用的是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

这个函数假设列表里的项目都不会是None，而且项目是有顺序的（比如说['a', 'a', 'a', 'b', 'b', 'c', 'd']）。

这个函数的输出是['a', 'a', 'a', 'b', 'b', 'c', 'd']，而它想要的结果是['a', 'b', 'c', 'd']。

Answer 1

假设输入的序列是无序的，这里有一个时间和空间复杂度都是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']

Answer 2

另一种非常快速的方法是使用集合（set）：

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

Answer 3

使用一个有序字典（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