index - python list unique count




如何在保持秩序的同時從列表中刪除重複項? (20)

5倍快速減少變體,但更複雜

>>> l = [5, 6, 6, 1, 1, 2, 2, 3, 4]
>>> reduce(lambda r, v: v in r[1] and r or (r[0].append(v) or r[1].add(v)) or r, l, ([], set()))[0]
[5, 6, 1, 2, 3, 4]

說明:

default = (list(), set())
# use list to keep order
# use set to make lookup faster

def reducer(result, item):
    if item not in result[1]:
        result[0].append(item)
        result[1].add(item)
    return result

>>> reduce(reducer, l, default)[0]
[5, 6, 1, 2, 3, 4]

有沒有一種內置的方法可以從Python中的列表中刪除重複項,同時保持順序? 我知道我可以使用一套刪除重複項,但破壞了原來的順序。 我也知道我可以像這樣推出自己的產品:

def uniq(input):
  output = []
  for x in input:
    if x not in output:
      output.append(x)
  return output

(感謝unwind這個代碼示例 。)

但是,如果可能的話,我想利用內置的或更加Pythonic的成語。

相關問題: 在Python中,從列表中刪除重複項的最快算法是什麼,以便所有元素都是唯一的, 同時保持順序


MizardX的答案提供了多種方法的好集合。

這就是我在大聲思考時想出的:

mylist = [x for i,x in enumerate(mylist) if x not in mylist[i+1:]]

編輯2016年

正如Raymond 指出的那樣 ,在OrderedDict在C中實現的python 3.5+中,列表理解方法將比OrderedDict慢(除非實際上最後需要列表 - 即使這樣,只有在輸入非常短的情況下)。 所以3.5+的最佳解決方案是OrderedDict

重要編輯2015年

正如@abarnert指出的, more_itertools庫( pip install more_itertools )包含一個unique_everseen函數,它可以解決這個問題,而列表not seen.add沒有任何不可讀的not seen.add突變 。 這也是最快的解決方案:

>>> from  more_itertools import unique_everseen
>>> items = [1, 2, 0, 1, 3, 2]
>>> list(unique_everseen(items))
[1, 2, 0, 3]

只需一個簡單的庫導入,不需要黑客入侵。 這來自itertools配方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 filterfalse(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

在Python 2.7+接受的常用成語 (它的工作原理,但並未針對速度進行優化,現在我將使用unique_everseen )為此使用collections.OrderedDict

運行時間: O(N)

>>> from collections import OrderedDict
>>> items = [1, 2, 0, 1, 3, 2]
>>> list(OrderedDict.fromkeys(items))
[1, 2, 0, 3]

這看起來比以下更好:

seen = set()
[x for x in seq if x not in seen and not seen.add(x)]

並沒有利用醜陋的黑客

not seen.add(x)

這依賴於set.add是一個始終返回None的就地方法,因此not None評估為True

但請注意,儘管它具有相同的運行時復雜度O(N),但解決方案在原始速度上更快。


一個簡單的遞歸解決方案:

def uniquefy_list(a):
    return uniquefy_list(a[1:]) if a[0] in a[1:] else [a[0]]+uniquefy_list(a[1:]) if len(a)>1 else [a[0]]

不要踢死馬(這個問題已經很老了,已經有很多很好的答案),但是這裡有一個使用熊貓的解決方案,在很多情況下它的速度非常快,而且使用起來很簡單。

import pandas as pd

my_list = range(5) + range(5)  # [0, 1, 2, 3, 4, 0, 1, 2, 3, 4]
>>> pd.Series(my_list).drop_duplicates().tolist()
# Output:
# [0, 1, 2, 3, 4]

你可以做一個醜陋的列表理解黑客。

[l[i] for i in range(len(l)) if l.index(l[i]) == i]

只需從外部模塊1添加另一個(非常高效的)這種功能的實現: iteration_utilities.unique_everseen

>>> from iteration_utilities import unique_everseen
>>> lst = [1,1,1,2,3,2,2,2,1,3,4]

>>> list(unique_everseen(lst))
[1, 2, 3, 4]

計時

我做了一些計時(Python 3.6),這些都表明它比我測試過的所有其他選擇都快,包括OrderedDict.fromkeysf7more_itertools.unique_everseen

%matplotlib notebook

from iteration_utilities import unique_everseen
from collections import OrderedDict
from more_itertools import unique_everseen as mi_unique_everseen

def f7(seq):
    seen = set()
    seen_add = seen.add
    return [x for x in seq if not (x in seen or seen_add(x))]

def iteration_utilities_unique_everseen(seq):
    return list(unique_everseen(seq))

def more_itertools_unique_everseen(seq):
    return list(mi_unique_everseen(seq))

def odict(seq):
    return list(OrderedDict.fromkeys(seq))

from simple_benchmark import benchmark

b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
              {2**i: list(range(2**i)) for i in range(1, 20)},
              'list size (no duplicates)')
b.plot()

只是為了確保我還做了更多重複測試,以檢查它是否有所作為:

import random

b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
              {2**i: [random.randint(0, 2**(i-1)) for _ in range(2**i)] for i in range(1, 20)},
              'list size (lots of duplicates)')
b.plot()

而一個只包含一個值:

b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
              {2**i: [1]*(2**i) for i in range(1, 20)},
              'list size (only duplicates)')
b.plot()

在所有這些情況下, iteration_utilities.unique_everseen函數是最快的(在我的電腦上)。

這個iteration_utilities.unique_everseen函數還可以處理輸入中不可取的值(但是,如果值可哈希,則具有O(n*n)性能而不是O(n)性能)。

>>> lst = [{1}, {1}, {2}, {1}, {3}]

>>> list(unique_everseen(lst))
[{1}, {2}, {3}]

1免責聲明:我是該軟件包的作者。


因為我正在查看dup並收集了一些相關的但不同的,相關的,有用的信息,這些信息不是其他答案的一部分,所以這裡有兩個其他可能的解決方案。

.get(True)XOR .setdefault(False)

第一個非常像被接受的seen_add但是使用字典的get(x,<default>)setdefault(x,<default>)了明顯的副作用:

# Explanation of d.get(x,True) != d.setdefault(x,False)
#
# x in d | d[x]  | A = d.get(x,True) | x in d | B = d.setdefault(x,False) | x in d | d[x]    | A xor B
# False  | None  | True          (1) | False  | False                 (2) | True   | False   | True
# True   | False | False         (3) | True   | False                 (4) | True   | False   | False
#
# Notes
# (1) x is not in the dictionary, so get(x,<default>) returns True but does __not__ add the value to the dictionary
# (2) x is not in the dictionary, so setdefault(x,<default>) adds the {x:False} and returns False
# (3) since x is in the dictionary, the <default> argument is ignored, and the value of the key is returned, which was
#     set to False in (2)
# (4) since the key is already in the dictionary, its value is returned directly and the argument is ignored
#
# A != B is how to do boolean XOR in Python
#
def sort_with_order(s):
    d = dict()
    return [x for x in s if d.get(x,True) != d.setdefault(x,False)]

如果x不在字典中, get(x,<default>)將返回<default> ,但不會將該鍵添加到字典中。 set(x,<default>)返回鍵值在字典中的值,否則將其設置為並返回<default>

除此之外: a != b是如何在python中執行異或操作

__OVERRIDING ___missing_____(受此答案啟發)

第二種技術是覆蓋__missing__方法,該方法在字典中不存在該鍵時被調用,該字典僅在使用d[k]表示法時才被調用:

class Tracker(dict):
    # returns True if missing, otherwise sets the value to False
    # so next time d[key] is called, the value False will be returned
    # and __missing__ will not be called again
    def __missing__(self, key):
        self[key] = False
        return True

t = Tracker()
unique_with_order = [x for x in samples if t[x]]

文檔

2.5版本中的新增功能:如果dict的子類定義了缺少_____()的方法,如果鍵值不存在,則d [key]操作使用鍵值作為參數調用該方法。 如果密鑰不存在,d [key]操作會返回或引發由_____缺失的_____(key)調用返回或引發的任何操作。 沒有其他操作或方法調用_____缺少_____()。 如果_____缺少_____()未定義,則引發KeyError。 _____缺少_____()必須是一種方法; 它不能是一個實例變量。 有關示例,請參閱collections.defaultdict。


在列表中彈出副本並在源列表中保留唯一身份驗證:

>>> list1 = [ 1,1,2,2,3,3 ]
>>> [ list1.pop(i) for i in range(len(list1))[::-1] if list1.count(list1[i]) > 1 ]
[1, 2, 3]

我按照相反的順序使用[::-1]作為讀取列表。


在這裡你有一些選擇: http://www.peterbe.com/plog/uniqifiers-benchmark : http://www.peterbe.com/plog/uniqifiers-benchmark

最快的一個:

def f7(seq):
    seen = set()
    seen_add = seen.add
    return [x for x in seq if not (x in seen or seen_add(x))]

為什麼將seen.add分配給seen_add而不是只調用seen.add ? Python是一種動態語言,可以解決seen.add每次迭代都比解析局部變量更昂貴。 seen.add在迭代之間可能會發生變化,並且運行時不夠聰明以排除這種情況。 為了安全起見,它必須每次檢查對象。

如果你打算在同一個數據集上使用這個函數,也許你會更好地使用一個有序集合: http://code.activestate.com/recipes/528878/ : http://code.activestate.com/recipes/528878/

O (1)每個操作的插入,刪除和成員檢查。


如果您的情況允許,您可以考慮在加載時刪除重複項:

假設你有一個循環引入數據並使用list1.append(item)...

list1 = [0, 2, 4, 9]
for x in range(0, 7):
  list1.append(x)

這給你一些重複:[0,2,4,9,0,1,2,3,4,5,6]

但是,如果你做到了:

list1 = [0, 2, 4, 9]
for x in range(0, 7)
  if x not in list1:
    list1.append(x)

你沒有得到重複,順序被保留:[0,2,4,9,1,3,5,6]


如果您經常使用pandas ,並且美學優於性能,那麼請考慮內置函數pandas.Series.drop_duplicates

    import pandas as pd
    import numpy as np

    uniquifier = lambda alist: pd.Series(alist).drop_duplicates().tolist()

    # from the chosen answer 
    def f7(seq):
        seen = set()
        seen_add = seen.add
        return [ x for x in seq if not (x in seen or seen_add(x))]

    alist = np.random.randint(low=0, high=1000, size=10000).tolist()

    print uniquifier(alist) == f7(alist)  # True

定時:

    In [104]: %timeit f7(alist)
    1000 loops, best of 3: 1.3 ms per loop
    In [110]: %timeit uniquifier(alist)
    100 loops, best of 3: 4.39 ms per loop

對於另一個很老的問題的另一個很晚的答案:

itertools食譜有一個功能,使用seen設置技術,但是:

  • 處理標準的key功能。
  • 不使用不合適的黑客。
  • 通過預先綁定seen.add優化循環,而不是查看N次。 ( f7也是這樣,但有些版本不。)
  • 通過使用ifilterfalse優化循環,因此您只需循環遍歷Python中的獨特元素,而不是所有元素。 (當然,你仍然可以在ifilterfalse裡面遍歷所有的內容,但這是C語言,而且要快得多。)

它實際上比f7更快嗎? 這取決於你的數據,所以你必須測試它並看看。 如果你最後想要一個列表, f7使用listcomp,並且在這裡沒有辦法做到這一點。 (你可以直接append而不是yielding,或者你可以將生成器提供給list函數,但是不能像listcomp中的LIST_APPEND那樣快。)無論如何,通常擠出幾微秒是不會的與具有容易理解的,可重用的,已經編寫的功能一樣重要,這些功能在需要裝飾時不需要DSU。

就像所有的食譜一樣,它也可以在more-iterools

如果你只是想要沒有key情況下,你可以簡化為:

def unique(iterable):
    seen = set()
    seen_add = seen.add
    for element in itertools.ifilterfalse(seen.__contains__, iterable):
        seen_add(element)
        yield element

您可以參考列表理解,因為它是由符號'_ [1]'構建的。
例如,下面的函數是唯一的 - 通過引用其列表理解來確定元素列表而不改變它們的順序。

def unique(my_list): 
    return [x for x in my_list if x not in locals()['_[1]']]

演示:

l1 = [1, 2, 3, 4, 1, 2, 3, 4, 5]
l2 = [x for x in l1 if x not in locals()['_[1]']]
print l2

輸出:

[1, 2, 3, 4, 5]

我的好友韋斯用列表解析給了我這個甜蜜的回答。

示例代碼:

>>> l = [3, 4, 3, 6, 4, 1, 4, 8]

>>> l = [l[i] for i in range(len(l)) if i == l.index(l[i])]

>>> l = [3, 4, 6, 1, 8]

_sorted_一個numpy數組比較有效的方法:

b = np.array([1,3,3, 8, 12, 12,12])    
numpy.hstack([b[0], [x[0] for x in zip(b[1:], b[:-1]) if x[0]!=x[1]]])

輸出:

array([ 1,  3,  8, 12])

這很快,但...

l = list(set(l))

...如果您的列表項不可排除,則不起作用。

更通用的方法是:

l = reduce(lambda x, y: x if y in x else x + [y], l, [])

它應該適用於所有情況。


這是一個O(N 2 )遞歸版本的樂趣:

def uniquify(s):
    if len(s) < 2:
        return s
    return uniquify(s[:-1]) + [s[-1]] * (s[-1] not in s[:-1])

from itertools import groupby
[ key for key,_ in groupby(sortedList)]

該列表甚至不需要排序 ,足夠的條件是將相同的值組合在一起。

編輯:我認為“維護秩序”意味著該名單實際上是有序的。 如果情況並非如此,那麼MizardX的解決方案是正確的。

社區編輯:然而,這是將“將重複的連續元素壓縮為單個元素”的最優雅的方式。


l = [1,2,2,3,3,...]
n = []
n.extend(ele for ele in l if ele not in set(n))

生成器表達式,使用集合的O(1)查找來確定是否在新列表中包含元素。





unique