在 Python 中，从列表中删除重复项以使所有元素都是唯一的*同时保留顺序*的最快算法是什么？[重复]

问题描述：

例如：

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

假设列表元素是可哈希的。

说明：结果应保留列表中的第一个重复项。例如，[1, 2, 3, 2, 3, 1] 变为 [1, 2, 3]。

解决方案 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])

解决方案 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 次是使用无重复列表。

摘要：直接使用集合来实现比使用令人困惑的单行代码要好得多 :-)

解决方案 3：

更新：在 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 中，字典查找比集合查找稍快一些。

解决方案 4：

哪个速度最快取决于列表中重复项的百分比。如果几乎都是重复项，只有少数唯一项，则创建新列表可能会更快。如果大部分都是唯一项，则从原始列表（或副本）中删除它们会更快。

以下是修改列表的方法：

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)

对索引进行向后迭代可确保删除项目不会影响迭代。

解决方案 5：

这是我发现的最快的就地方法（假设有大量重复项）：

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%，Allen 的实现基于 Allen 的实现（使用 timeit.repeat 计时，由 psyco 编译的 JIT）。它会保留任何重复项的第一个实例。

repton-infinity：如果您能确认我的时间安排，我会很感兴趣。

解决方案 6：

强制性的基于发电机的变化：

def unique(seq):
  seen = set()
  for x in seq:
    if x not in seen:
      seen.add(x)
      yield x

解决方案 7：

这可能是最简单的方法：

list(OrderedDict.fromkeys(iterable))

从 Python 3.5 开始，OrderedDict 现在用 C 实现，因此它现在是最短、最干净和最快的。

解决方案 8：

摘自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

解决方案 9：

单行：

new_list = reduce(lambda x,y: x+[y][:1-int(y in x)], my_list, [])

解决方案 10：

为此，这里有一个就地的单行代码：

>>> x = [1, 1, 2, 'a', 'a', 3]
>>> [ item for pos,item in enumerate(x) if x.index(item)==pos ]
[1, 2, 'a', 3]

解决方案 11：

这是最快的一个，比较了这次冗长的讨论中的所有内容以及这里给出的其他答案，参考这个基准。它比讨论中最快的函数快 25% f8。感谢 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

解决方案 12：

实际上，你可以在 Python 中做一些很酷的事情来解决这个问题。你可以创建一个列表推导，在构建时它会引用自身。如下所示：

   # remove duplicates...
   def unique(my_list):
       return [x for x in my_list if x not in locals()['_[1]'].__self__]

编辑：我删除了“self”，它可以在 Mac OS X、Python 2.5.1 上运行。

_[1] 是 Python 对新列表的“秘密”引用。当然，上面的代码有点混乱，但您可以根据需要对其进行调整。例如，您实际上可以编写一个返回对理解的引用的函数；它看起来更像：

return [x for x in my_list if x not in this_list()]

解决方案 13：

首先，重复项是否一定需要位于列表中？查找元素时没有开销，但添加元素时开销稍大一些（尽管开销应该是 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])
>>> 

解决方案 14：

删除重复项并保留顺序：

这是一个快速的双行代码，利用列表推导和字典的内置功能。

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() 函数返回该值并将其直接添加到列表推导中的临时字典中。使用内置函数和字典的哈希值将最大限度地提高该过程的效率。

解决方案 15：

如果 dict 是哈希表，则为 O(n)；如果 dict 是树，则为 O(nlogn)；简单，固定。感谢 Matthew 的建议。抱歉，我不知道底层类型。

def unique(x):    
  output = []
  y = {}
  for item in x:
    y[item] = ""

  for item in x:
    if item in y:
      output.append(item)

  return output

解决方案 16：

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

解决方案 17：

这里有一些很棒的、有效的解决方案。但是，对于那些不关心绝对最有效O(n)解决方案的人来说，我会选择简单的单行O(n^2*log(n))解决方案：

def unique(xs):
    return sorted(set(xs), key=lambda x: xs.index(x))

或者更有效的双线O(n*log(n))解决方案：

def unique(xs):
    positions = dict((e,pos) for pos,e in reversed(list(enumerate(xs))))
    return sorted(set(xs), key=lambda x: positions[x])

解决方案 18：

以下是来自itertools文档的两个方法：

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

def unique_justseen(iterable, key=None):
    "List unique elements, preserving order. Remember only the element just seen."
    # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B
    # unique_justseen('ABBCcAD', str.lower) --> A B C A D
    return imap(next, imap(itemgetter(1), groupby(iterable, key)))

解决方案 19：

我没有使用过 Python，但有一种算法是对列表进行排序，然后删除重复项（通过与列表中的先前项目进行比较），最后通过与旧列表进行比较找到新列表中的位置。

较长的答案：http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52560

解决方案 20：

>>> def unique(list):
...   y = []
...   for x in list:
...     if x not in y:
...       y.append(x)
...   return y

解决方案 21：

如果从 Terhost 的答案中的 set() 调用中取出空列表，速度就会稍微提高。

将： found = set([]) 更改

为： found = set()

然而，你根本不需要这个套装。

def unique(items):
    keep = []

    for item in items:
        if item not in keep:
            keep.append(item)

    return keep

使用 timeit 我得到了以下结果：

使用 set([]) -- 4.97210427363

使用 set() -- 4.65712377445

不使用 set -- 3.44865284975

解决方案 22：

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 t.c. = 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 

解决方案 23：

>>> 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]']” 是正在创建的列表的“秘密名称”。

解决方案 24：

我不知道这个是否快，但至少它很简单。

简单来说，先将其转换为集合，然后再转换为列表

def unique(container):
  return list(set(container))

解决方案 25：

一次通过。

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

解决方案 26：

我没有做过任何测试，但一种可能的算法可能是创建第二个列表，并遍历第一个列表。如果某个项目不在第二个列表中，则将其添加到第二个列表中。

x = [1, 1, 2, 'a', 'a', 3]
y = []
for each in x:
    if each not in y:
        y.append(each)

解决方案 27：

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()
print a

print unique(a)

插入元素将花费 theta(n)，检索元素是否存在将花费恒定时间，测试所有项目也将花费 theta(n)，因此我们可以看到此解决方案将花费 theta(n)。请记住，python 中的字典是通过哈希表实现的。