12

我有一个列表，我正试图从中删除重复的项目。我使用的是 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' ] .

4

8 回答 8

12

另一种非常快速的 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)]
于 2011-06-01T07:44:41.307 回答
8

使用 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
于 2011-06-01T07:11:41.747 回答
7

假设输入序列是无序的，这是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']
于 2011-06-01T07:56:52.883 回答
5

我知道这已经得到了回答，但这里有一个单行（加上导入）：

from collections import OrderedDict
def dedupe(_list):
    return OrderedDict((item,None) for item in _list).keys()

>>> dedupe(['q', 'w', 'e', 'r', 'q', 'w', 'y', 'u', 'i', 't', 'e', 'p', 't', 'y', 'e'])
['q', 'w', 'e', 'r', 'y', 'u', 'i', 't', 'p']
于 2011-08-10T22:41:54.570 回答
3

我认为这完全没问题。你会得到 O(n) 的性能，这是你所希望的最好的。

如果列表是无序的，那么您需要一个助手set来包含您已经访问过的项目，但在您的情况下，这不是必需的。

于 2011-06-01T07:04:40.493 回答
2

如果您的列表未排序，那么您的问题没有意义。例如 [1,2,1] 可能变成 [1,2] 或 [2,1]

如果您的列表很大，您可能希望使用 SLICE 将结果写回同一个列表以节省内存：

>>> x=['a', 'a', 'a', 'b', 'b', 'c', 'd']
>>> x[:]=[x[i] for i in range(len(x)) if i==0 or x[i]!=x[i-1]]
>>> x
['a', 'b', 'c', 'd']

对于内联删除，请参阅在迭代时从列表中删除项目或在迭代时从列表中删除项目而不使用 Python 中的额外内存

您可以使用的一个技巧是，如果您知道 x 已排序，并且您知道 x[i]=x[i+j] 那么您不需要检查 x[i] 和 x[i+j] 之间的任何内容（如果您不需要删除这些 j 值，您可以将所需的值复制到新列表中）

因此，如果集合中的所有内容都是唯一的，即 len(set(x))=len(x)，您无法击败 n 次操作它的最佳情况（或低于 n/2 作为最佳情况，如果您知道由于您生成的数据而提前知道 len(x)/len(set(x))>2）：

最佳算法可能会使用二分搜索来以分而治之的方法为每个最小值 i 找到最大值 j。初始分割的长度可能是 len(x)/approximated(len(set(x)))。希望它可以被执行，即使 len(x)=len(set(x)) 它仍然只使用 n 操作。

于 2011-06-01T07:28:37.427 回答
2

http://docs.python.org/2/library/itertools.html中描述了 unique_everseen 解决方案 

def unique_everseen(iterable, key=None):
    "List unique elements, preserving order. Remember all elements ever seen."
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D
    # unique_everseen('ABBCcAD', str.lower) --> A B C D
    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
于 2014-01-16T14:39:35.797 回答
0

在我看来还可以。如果您真的想使用集合，请执行以下操作：

def ordered_set (_list) :
    result = set()
    lastitem = None
    for item in _list :
        if item != lastitem :
            result.add(item)
            lastitem = item
    return sorted(tuple(result))

我不知道你会得到什么性能，你应该测试一下；可能因为方法过热而相同！

如果你真的像我一样偏执，请阅读这里：

http://wiki.python.org/moin/HowTo/Sorting/

http://wiki.python.org/moin/PythonSpeed/PerformanceTips

只记得这个（它包含答案）：

http://www.peterbe.com/plog/uniqifiers-benchmark

于 2011-06-01T07:17:45.977 回答