Apakah ada built-in yang menghapus duplikat dari daftar di Python, sambil menjaga ketertiban? Saya tahu bahwa saya bisa menggunakan satu set untuk menghapus duplikat, tetapi itu merusak tatanan asli. Saya juga tahu bahwa saya dapat menggulung sendiri seperti ini:

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

(Terima kasih kepada bersantai untuk itu sampel kode .)

Tetapi saya ingin memanfaatkan idiom bawaan atau lebih Pythonic jika memungkinkan.

Pertanyaan terkait: Dengan Python, apa algoritma tercepat untuk menghapus duplikat dari daftar sehingga semua elemen unik sekaligus menjaga ketertiban ?

Di sini Anda memiliki beberapa alternatif: http://www.peterbe.com/plog/uniqifiers-benchmark

Yang tercepat:

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

Mengapa seen.addmemilih seen_addbukan hanya menelepon seen.add? Python adalah bahasa yang dinamis, dan menyelesaikan seen.addsetiap iterasi lebih mahal daripada menyelesaikan variabel lokal.seen.addbisa berubah antara iterasi, dan runtime tidak cukup pintar untuk mengesampingkan itu. Untuk memainkannya dengan aman, ia harus memeriksa objek setiap kali.

Jika Anda berencana banyak menggunakan fungsi ini pada dataset yang sama, mungkin Anda akan lebih baik dengan set yang dipesan: http://code.activestate.com/recipes/528878/

HAI (1) penyisipan, penghapusan dan cek anggota per operasi.

(Catatan tambahan kecil: seen.add()selalu kembali None, jadi di oratas hanya ada sebagai cara untuk mencoba pembaruan yang ditetapkan, dan bukan sebagai bagian integral dari tes logis.)

Edit 2016

Seperti yang ditunjukkan Raymond , dalam python 3.5+ di mana OrderedDictdiimplementasikan dalam C, pendekatan pemahaman daftar akan lebih lambat daripada OrderedDict(kecuali Anda benar-benar membutuhkan daftar di akhir - dan bahkan kemudian, hanya jika inputnya sangat pendek). Jadi solusi terbaik untuk 3.5+ adalahOrderedDict .

Edit Penting 2015

Seperti yang dicatat @abarnert , more_itertoolslibrary ( pip install more_itertools) berisi unique_everseenfungsi yang dibangun untuk menyelesaikan masalah ini tanpa mutasi yang tidak dapat dibaca ( not seen.add) dalam pemahaman daftar. Ini juga merupakan solusi tercepat:

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

Hanya satu impor perpustakaan sederhana dan tidak ada retasan. Ini berasal dari implementasi resep itertools unique_everseenyang terlihat seperti:

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

Dalam Python 2.7+yang idiom umum diterima (yang bekerja tetapi tidak dioptimalkan untuk kecepatan, saya sekarang akan menggunakan unique_everseen) untuk keperluan inicollections.OrderedDict :

Runtime: O (N)

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

Ini terlihat jauh lebih bagus daripada:

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

dan tidak memanfaatkan hack jelek :

not seen.add(x)

yang bergantung pada fakta bahwa set.addini adalah metode in-place yang selalu mengembalikan Nonesehingga not NonedievaluasiTrue .

Namun perlu dicatat bahwa solusi peretasan lebih cepat dalam kecepatan mentah meskipun memiliki kompleksitas runtime yang sama O (N).

Dalam Python 2.7 , cara baru untuk menghapus duplikat dari iterable sambil menjaganya dalam urutan asli adalah:

>>> from collections import OrderedDict
>>> list(OrderedDict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']

Dalam Python 3.5 , OrderedDict memiliki implementasi C. Pengaturan waktu saya menunjukkan bahwa ini sekarang adalah yang tercepat dan terpendek dari berbagai pendekatan untuk Python 3.5.

Dalam Python 3.6 , perintah reguler menjadi teratur dan kompak. (Fitur ini berlaku untuk CPython dan PyPy tetapi mungkin tidak ada dalam implementasi lain). Itu memberi kami cara deduksi tercepat baru sambil mempertahankan pesanan:

>>> list(dict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']

Dalam Python 3.7 , dikt reguler dijamin untuk keduanya dipesan di semua implementasi. Jadi, solusi terpendek dan tercepat adalah:

>>> list(dict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']

Tanggapan untuk @max: Setelah Anda pindah ke 3.6 atau 3.7 dan menggunakan dict biasa alih-alih OrderedDict , Anda tidak bisa benar-benar mengalahkan kinerja dengan cara lain. Kamusnya padat dan siap dikonversi ke daftar dengan hampir tanpa overhead. Daftar target adalah pra-ukuran untuk len (d) yang menyimpan semua ukuran yang terjadi dalam pemahaman daftar. Juga, karena daftar kunci internal padat, menyalin pointer hampir secepat salinan daftar.

sequence = ['1', '2', '3', '3', '6', '4', '5', '6']
unique = []
[unique.append(item) for item in sequence if item not in unique]

unik → ['1', '2', '3', '6', '4', '5']

Bukan untuk menendang kuda mati (pertanyaan ini sudah sangat tua dan sudah memiliki banyak jawaban bagus), tetapi di sini ada solusi menggunakan panda yang cukup cepat dalam banyak keadaan dan mati mudah digunakan.

import pandas as pd

my_list = [0, 1, 2, 3, 4, 1, 2, 3, 5]

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

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

Daftar itu bahkan tidak harus disortir , syarat yang memadai adalah bahwa nilai yang sama dikelompokkan bersama.

Sunting: Saya berasumsi bahwa "menjaga pesanan" menyiratkan bahwa daftar sebenarnya dipesan. Jika ini bukan masalahnya, maka solusi dari MizardX adalah yang benar.

Suntingan komunitas: Ini adalah cara paling elegan untuk "mengompres elemen duplikat berurutan menjadi satu elemen".

Saya pikir jika Anda ingin mempertahankan pesanan,

Anda dapat mencoba ini:

list1 = ['b','c','d','b','c','a','a']    
list2 = list(set(list1))    
list2.sort(key=list1.index)    
print list2

ATAU sama halnya Anda dapat melakukan ini:

list1 = ['b','c','d','b','c','a','a']  
list2 = sorted(set(list1),key=list1.index)  
print list2 

Anda juga dapat melakukan ini:

list1 = ['b','c','d','b','c','a','a']    
list2 = []    
for i in list1:    
    if not i in list2:  
        list2.append(i)`    
print list2

Dapat juga ditulis sebagai berikut:

list1 = ['b','c','d','b','c','a','a']    
list2 = []    
[list2.append(i) for i in list1 if not i in list2]    
print list2 

Dalam Python 3.7 dan di atasnya, kamus dijamin untuk mengingat urutan penyisipan kuncinya. Jawaban atas pertanyaan ini merangkum keadaan saat ini.

The OrderedDictsolusi sehingga menjadi usang dan tanpa pernyataan impor kita hanya bisa mengeluarkan:

>>> lst = [1, 2, 1, 3, 3, 2, 4]
>>> list(dict.fromkeys(lst))
[1, 2, 3, 4]

Untuk jawaban yang sangat terlambat untuk pertanyaan lain yang sangat lama:

The itertoolsresep memiliki fungsi yang melakukan ini, dengan menggunakan seenteknik set, tetapi:

• Menangani keyfungsi standar .
• Tidak menggunakan peretasan yang tidak pantas.
• Mengoptimalkan loop dengan pra-mengikat seen.addalih - alih mencari N kali. (f7 juga melakukan ini, tetapi beberapa versi tidak.)
• Mengoptimalkan loop dengan menggunakan ifilterfalse, jadi Anda hanya perlu mengulang elemen unik di Python, bukan semuanya. (Anda masih mengulanginya semua di dalam ifilterfalse, tentu saja, tapi itu dalam C, dan jauh lebih cepat.)

Apakah ini sebenarnya lebih cepat daripada f7? Tergantung pada data Anda, jadi Anda harus mengujinya dan melihatnya. Jika Anda ingin daftar pada akhirnya, f7gunakan listcomp, dan tidak ada cara untuk melakukannya di sini. (Anda bisa langsung appendbukannya yield, atau Anda bisa memberi makan generator ke dalam listfungsi, tetapi tidak ada yang bisa secepat LIST_APPEND di dalam listcomp.) Bagaimanapun, biasanya, memeras beberapa mikrodetik tidak akan menjadi seperti penting sebagai memiliki fungsi yang mudah dimengerti, dapat digunakan kembali, sudah ditulis yang tidak memerlukan DSU ketika Anda ingin menghias.

Seperti semua resep, itu juga tersedia di more-iterools .

Jika Anda hanya menginginkan no- keycase, Anda dapat menyederhanakannya sebagai:

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

Hanya untuk menambah (sangat performant) pelaksanaan fungsi suatu tersebut dari modul eksternal ¹ : 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]

Pengaturan waktu

Saya melakukan beberapa pengaturan waktu (Python 3.6) dan ini menunjukkan bahwa ini lebih cepat daripada semua alternatif lain yang saya uji, termasuk OrderedDict.fromkeys, f7dan more_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()

Dan hanya untuk memastikan saya juga melakukan tes dengan duplikat lebih banyak hanya untuk memeriksa apakah ada bedanya:

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

Dan satu yang hanya mengandung satu nilai:

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

Dalam semua kasus ini iteration_utilities.unique_everseenfungsinya adalah yang tercepat (di komputer saya).

Ini iteration_utilities.unique_everseenfungsi juga dapat menangani nilai-nilai unhashable pada input (namun dengan O(n*n)kinerja bukan O(n)kinerja ketika nilai-nilai yang hashable).

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

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

¹ Penafian: Saya pembuat paket itu.

Tanpa tipe hashable (mis. Daftar daftar), berdasarkan MizardX's:

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

Meminjam ide rekursif yang digunakan dalam mendefinisikan nubfungsi Haskell untuk daftar, ini akan menjadi pendekatan rekursif:

def unique(lst):
    return [] if lst==[] else [lst[0]] + unique(filter(lambda x: x!= lst[0], lst[1:]))

misalnya:

In [118]: unique([1,5,1,1,4,3,4])
Out[118]: [1, 5, 4, 3]

Saya mencoba untuk menumbuhkan ukuran data dan melihat kompleksitas waktu sub-linear (tidak pasti, tetapi menyarankan ini harus baik untuk data normal).

In [122]: %timeit unique(np.random.randint(5, size=(1)))
10000 loops, best of 3: 25.3 us per loop

In [123]: %timeit unique(np.random.randint(5, size=(10)))
10000 loops, best of 3: 42.9 us per loop

In [124]: %timeit unique(np.random.randint(5, size=(100)))
10000 loops, best of 3: 132 us per loop

In [125]: %timeit unique(np.random.randint(5, size=(1000)))
1000 loops, best of 3: 1.05 ms per loop

In [126]: %timeit unique(np.random.randint(5, size=(10000)))
100 loops, best of 3: 11 ms per loop

Saya juga berpikir itu menarik bahwa ini dapat dengan mudah digeneralisasikan ke keunikan oleh operasi lain. Seperti ini:

import operator
def unique(lst, cmp_op=operator.ne):
    return [] if lst==[] else [lst[0]] + unique(filter(lambda x: cmp_op(x, lst[0]), lst[1:]), cmp_op)

Misalnya, Anda bisa meneruskan fungsi yang menggunakan gagasan pembulatan ke bilangan bulat yang sama seolah-olah itu "kesetaraan" untuk tujuan keunikan, seperti ini:

def test_round(x,y):
    return round(x) != round(y)

kemudian unik (some_list, test_round) akan memberikan elemen unik dari daftar di mana keunikan tidak lagi berarti kesetaraan tradisional (yang tersirat dengan menggunakan segala jenis pendekatan berbasis set atau dict-kunci berbasis masalah ini) tetapi sebaliknya dimaksudkan untuk mengambil hanya elemen pertama yang membulatkan ke K untuk setiap kemungkinan bilangan bulat K yang mungkin membulat, misalnya:

In [6]: unique([1.2, 5, 1.9, 1.1, 4.2, 3, 4.8], test_round)
Out[6]: [1.2, 5, 1.9, 4.2, 3]

5 x lebih cepat mengurangi varian tetapi lebih canggih

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

Penjelasan:

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]

Anda dapat merujuk pemahaman daftar karena sedang dibangun oleh simbol '_ [1]'.
Misalnya, fungsi berikut unik-ifies daftar elemen tanpa mengubah urutannya dengan merujuk pemahaman daftar.

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

Demo:

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

Keluaran:

[1, 2, 3, 4, 5]

Jawaban MizardX memberikan koleksi yang baik dari berbagai pendekatan.

Inilah yang saya pikirkan sambil berpikir keras:

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

di sini adalah cara sederhana untuk melakukannya:

list1 = ["hello", " ", "w", "o", "r", "l", "d"]
sorted(set(list1 ), key=lambda x:list1.index(x))

yang memberikan output:

["hello", " ", "w", "o", "r", "l", "d"]

Anda bisa melakukan semacam hack daftar pemahaman jelek.

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

Pendekatan yang relatif efektif dengan _sorted_sebuah numpyarray:

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

Output:

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

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

Ekspresi generator yang menggunakan O (1) mencari set untuk menentukan apakah akan memasukkan elemen dalam daftar baru atau tidak.

Solusi rekursif sederhana:

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

Menghilangkan nilai duplikat secara berurutan, tetapi mempertahankan urutan item yang tersisa. Penggunaan fungsi generator tujuan umum.

# for hashable sequence
def remove_duplicates(items):
    seen = set()
    for item in items:
        if item not in seen:
            yield item
            seen.add(item)

a = [1, 5, 2, 1, 9, 1, 5, 10]
list(remove_duplicates(a))
# [1, 5, 2, 9, 10]



# for unhashable sequence
def remove_duplicates(items, key=None):
    seen = set()
    for item in items:
        val = item if key is None else key(item)
        if val not in seen:
            yield item
            seen.add(val)

a = [ {'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 1, 'y': 2}, {'x': 2, 'y': 4}]
list(remove_duplicates(a, key=lambda d: (d['x'],d['y'])))
# [{'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 2, 'y': 4}]

pengguna panda harus memeriksa pandas.unique.

>>> import pandas as pd
>>> lst = [1, 2, 1, 3, 3, 2, 4]
>>> pd.unique(lst)
array([1, 2, 3, 4])

Fungsi mengembalikan array NumPy. Jika perlu, Anda dapat mengonversinya menjadi daftar dengan tolistmetode ini.

Jika Anda membutuhkan satu liner maka mungkin ini akan membantu:

reduce(lambda x, y: x + y if y[0] not in x else x, map(lambda x: [x],lst))

... harus bekerja tetapi koreksi saya jika saya salah

Jika Anda secara rutin menggunakan pandas, dan estetika lebih disukai daripada kinerja, maka pertimbangkan fungsi bawaan 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

Pengaturan waktu:

    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

ini akan menjaga ketertiban dan berjalan dalam waktu O (n). pada dasarnya idenya adalah membuat lubang di mana pun ada duplikat ditemukan dan menenggelamkannya ke bawah. memanfaatkan pointer baca dan tulis. setiap kali duplikat ditemukan hanya pointer baca maju dan tulis pointer tetap pada entri duplikat untuk menimpa itu.

def deduplicate(l):
    count = {}
    (read,write) = (0,0)
    while read < len(l):
        if l[read] in count:
            read += 1
            continue
        count[l[read]] = True
        l[write] = l[read]
        read += 1
        write += 1
    return l[0:write]

Solusi tanpa menggunakan modul atau set yang diimpor:

text = "ask not what your country can do for you ask what you can do for your country"
sentence = text.split(" ")
noduplicates = [(sentence[i]) for i in range (0,len(sentence)) if sentence[i] not in sentence[:i]]
print(noduplicates)

Memberikan output:

['ask', 'not', 'what', 'your', 'country', 'can', 'do', 'for', 'you']

Metode di tempat

Metode ini kuadratik, karena kami memiliki pencarian linier ke dalam daftar untuk setiap elemen daftar (untuk itu kami harus menambahkan biaya menata ulang daftar karena dels).

Yang mengatakan, adalah mungkin untuk beroperasi di tempat jika kita mulai dari akhir daftar dan melanjutkan ke asal menghapus setiap istilah yang ada di sub-daftar di sebelah kirinya

Ide dalam kode ini sederhana

for i in range(len(l)-1,0,-1): 
    if l[i] in l[:i]: del l[i] 

Tes implementasi yang sederhana

In [91]: from random import randint, seed                                                                                            
In [92]: seed('20080808') ; l = [randint(1,6) for _ in range(12)] # Beijing Olympics                                                                 
In [93]: for i in range(len(l)-1,0,-1): 
    ...:     print(l) 
    ...:     print(i, l[i], l[:i], end='') 
    ...:     if l[i] in l[:i]: 
    ...:          print( ': remove', l[i]) 
    ...:          del l[i] 
    ...:     else: 
    ...:          print() 
    ...: print(l)
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5, 2]
11 2 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5]: remove 2
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5]
10 5 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4]: remove 5
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4]
9 4 [6, 5, 1, 4, 6, 1, 6, 2, 2]: remove 4
[6, 5, 1, 4, 6, 1, 6, 2, 2]
8 2 [6, 5, 1, 4, 6, 1, 6, 2]: remove 2
[6, 5, 1, 4, 6, 1, 6, 2]
7 2 [6, 5, 1, 4, 6, 1, 6]
[6, 5, 1, 4, 6, 1, 6, 2]
6 6 [6, 5, 1, 4, 6, 1]: remove 6
[6, 5, 1, 4, 6, 1, 2]
5 1 [6, 5, 1, 4, 6]: remove 1
[6, 5, 1, 4, 6, 2]
4 6 [6, 5, 1, 4]: remove 6
[6, 5, 1, 4, 2]
3 4 [6, 5, 1]
[6, 5, 1, 4, 2]
2 1 [6, 5]
[6, 5, 1, 4, 2]
1 5 [6]
[6, 5, 1, 4, 2]

In [94]:                                                                                                                             

Pendekatan zmk menggunakan pemahaman daftar yang sangat cepat, namun menjaga urutan secara alami. Untuk menerapkan string case sensitif dapat dengan mudah dimodifikasi. Ini juga mempertahankan kasus aslinya.

def DelDupes(aseq) :
    seen = set()
    return [x for x in aseq if (x.lower() not in seen) and (not seen.add(x.lower()))]

Fungsi yang terkait erat adalah:

def HasDupes(aseq) :
    s = set()
    return any(((x.lower() in s) or s.add(x.lower())) for x in aseq)

def GetDupes(aseq) :
    s = set()
    return set(x for x in aseq if ((x.lower() in s) or s.add(x.lower())))

Pemahaman daftar satu liner:

values_non_duplicated = [value for index, value in enumerate(values) if value not in values[ : index]]

Cukup tambahkan persyaratan untuk memeriksa bahwa nilai tidak pada posisi sebelumnya