Usuwanie duplikatów z listy list

Mam listę list w Pythonie:

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

I chcę usunąć z niego zduplikowane elementy. To była zwykła lista, której nie mógłbym użyć set. Niestety, ta lista nie jest haszowalna i nie może tworzyć zestawu list. Tylko krotek. Mogę więc zmienić wszystkie listy w krotki, a następnie użyć set i z powrotem do list. Ale to nie jest szybkie.

Jak można to zrobić w najbardziej efektywny sposób?

Wynik powyższej listy powinien być:

k = [[5, 6, 2], [1, 2], [3], [4]]

Nie obchodzi mnie zachowanie porządku.

Uwaga: to pytanie jest podobne, ale nie do końca to, czego potrzebuję. Przeszukano SO, ale nie znalazłem dokładnego duplikatu.

Benchmarking:

import itertools, time


class Timer(object):
    def __init__(self, name=None):
        self.name = name

    def __enter__(self):
        self.tstart = time.time()

    def __exit__(self, type, value, traceback):
        if self.name:
            print '[%s]' % self.name,
        print 'Elapsed: %s' % (time.time() - self.tstart)


k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [5, 2], [6], [8], [9]] * 5
N = 100000

print len(k)

with Timer('set'):
    for i in xrange(N):
        kt = [tuple(i) for i in k]
        skt = set(kt)
        kk = [list(i) for i in skt]


with Timer('sort'):
    for i in xrange(N):
        ks = sorted(k)
        dedup = [ks[i] for i in xrange(len(ks)) if i == 0 or ks[i] != ks[i-1]]


with Timer('groupby'):
    for i in xrange(N):
        k = sorted(k)
        dedup = list(k for k, _ in itertools.groupby(k))

with Timer('loop in'):
    for i in xrange(N):
        new_k = []
        for elem in k:
            if elem not in new_k:
                new_k.append(elem)

"loop in" (metoda kwadratowa) jest najszybszy ze wszystkich dla krótkich list. W przypadku długich list jest szybszy niż wszyscy, z wyjątkiem metody grupowej. Czy to ma sens?

Krótka lista (ta w kodzie), 100000 iteracji:

[set] Elapsed: 1.3900001049
[sort] Elapsed: 0.891000032425
[groupby] Elapsed: 0.780999898911
[loop in] Elapsed: 0.578000068665

W przypadku dłuższej listy (ta w kodzie powtórzona 5 razy):

[set] Elapsed: 3.68700003624
[sort] Elapsed: 3.43799996376
[groupby] Elapsed: 1.03099989891
[loop in] Elapsed: 1.85900020599

>>> k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
>>> import itertools
>>> k.sort()
>>> list(k for k,_ in itertools.groupby(k))
[[1, 2], [3], [4], [5, 6, 2]]

itertoolsczęsto oferuje najszybsze i najbardziej wydajne rozwiązania tego rodzaju problemów, i jest dobrze warto się zaznajomiony z! -)

Edycja : jak wspomniałem w komentarzu, normalne wysiłki optymalizacyjne koncentrują się na dużych nakładach (podejście duże-O), ponieważ jest o wiele łatwiejsze, że oferuje dobre zwroty z wysiłku. Ale czasami (zasadniczo w przypadku „tragicznie kluczowych wąskich gardeł” w głębokich wewnętrznych pętlach kodu, które przesuwają granice limitów wydajności) może zajść potrzeba bardziej szczegółowego omówienia rozkładów prawdopodobieństwa i podjęcia decyzji, które środki wydajności należy zoptymalizować (może górna granica lub 90 centyl jest ważniejszy niż średnia lub mediana, w zależności od aplikacji), przeprowadzając potencjalnie heurystyczne kontrole na początku, aby wybrać różne algorytmy w zależności od charakterystyki danych wejściowych i tak dalej.

Dokładne pomiary wydajności „punktowej” (kod A w porównaniu z kodem B dla konkretnego wejścia) są częścią tego niezwykle kosztownego procesu, a standardowy moduł biblioteki timeitpomaga w tym. Jednak łatwiej jest z niego korzystać po znaku zachęty powłoki. Na przykład, oto krótki moduł prezentujący ogólne podejście do tego problemu, zapisz go jako nodup.py:

import itertools

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

def doset(k, map=map, list=list, set=set, tuple=tuple):
  return map(list, set(map(tuple, k)))

def dosort(k, sorted=sorted, xrange=xrange, len=len):
  ks = sorted(k)
  return [ks[i] for i in xrange(len(ks)) if i == 0 or ks[i] != ks[i-1]]

def dogroupby(k, sorted=sorted, groupby=itertools.groupby, list=list):
  ks = sorted(k)
  return [i for i, _ in itertools.groupby(ks)]

def donewk(k):
  newk = []
  for i in k:
    if i not in newk:
      newk.append(i)
  return newk

# sanity check that all functions compute the same result and don't alter k
if __name__ == '__main__':
  savek = list(k)
  for f in doset, dosort, dogroupby, donewk:
    resk = f(k)
    assert k == savek
    print '%10s %s' % (f.__name__, sorted(resk))

Zwróć uwagę na kontrolę poczytalności (wykonywaną po prostu python nodup.py) i podstawową technikę podnoszenia (uczyń stałe nazwy globalne lokalnymi dla każdej funkcji dla szybkości), aby postawić wszystko na równych zasadach.

Teraz możemy przeprowadzić testy na maleńkiej liście przykładów:

$ python -mtimeit -s'import nodup' 'nodup.doset(nodup.k)'
100000 loops, best of 3: 11.7 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.dosort(nodup.k)'
100000 loops, best of 3: 9.68 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.dogroupby(nodup.k)'
100000 loops, best of 3: 8.74 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.donewk(nodup.k)'
100000 loops, best of 3: 4.44 usec per loop

potwierdzając, że podejście kwadratowe ma wystarczająco małe stałe, aby uczynić je atrakcyjnym dla małych list z kilkoma zduplikowanymi wartościami. Z krótką listą bez duplikatów:

$ python -mtimeit -s'import nodup' 'nodup.donewk([[i] for i in range(12)])'
10000 loops, best of 3: 25.4 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.dogroupby([[i] for i in range(12)])'
10000 loops, best of 3: 23.7 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.doset([[i] for i in range(12)])'
10000 loops, best of 3: 31.3 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.dosort([[i] for i in range(12)])'
10000 loops, best of 3: 25 usec per loop

podejście kwadratowe nie jest złe, ale sortowanie i grupowanie są lepsze. Itd itd.

Jeśli (jak sugeruje obsesja na punkcie wydajności) ta operacja znajduje się w rdzennej wewnętrznej pętli twojej aplikacji przesuwającej granice, warto wypróbować ten sam zestaw testów na innych reprezentatywnych próbkach wejściowych, prawdopodobnie wykrywając jakąś prostą miarę, która może heurystycznie pozwolić wybierz jedno lub drugie podejście (ale środek oczywiście musi być szybki).

Warto również rozważyć zachowanie innej reprezentacji k- dlaczego w pierwszej kolejności musi to być lista list, a nie zestaw krotek? Jeśli zadanie usuwania duplikatów jest częste, a profilowanie pokazuje, że jest to wąskie gardło wydajności programu, na przykład utrzymywanie zestawu krotek i uzyskiwanie z niego listy list tylko wtedy, gdy jest to konieczne, może być ogólnie szybsze.

Robiąc to ręcznie, tworząc nową klistę i dodając dotychczas nie znalezione wpisy:

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
new_k = []
for elem in k:
    if elem not in new_k:
        new_k.append(elem)
k = new_k
print k
# prints [[1, 2], [4], [5, 6, 2], [3]]

Proste do zrozumienia i zachowujesz kolejność pierwszego wystąpienia każdego elementu, która powinna być przydatna, ale myślę, że jest to kwadratowe pod względem złożoności, ponieważ szukasz całości new_kdla każdego elementu.

>>> k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
>>> k = sorted(k)
>>> k
[[1, 2], [1, 2], [3], [4], [4], [5, 6, 2]]
>>> dedup = [k[i] for i in range(len(k)) if i == 0 or k[i] != k[i-1]]
>>> dedup
[[1, 2], [3], [4], [5, 6, 2]]

Nie wiem, czy to koniecznie jest szybsze, ale nie musisz używać do krotek i zestawów.

Wszystkie dotychczasowe setrozwiązania tego problemu wymagają stworzenia całości setprzed iteracją.

Można to uczynić leniwym, a jednocześnie zachować porządek, iterując listę list i dodając do „widziany” set. Następnie pokaż listę tylko wtedy, gdy nie zostanie znaleziona w tym trackerze set.

Ten unique_everseenprzepis jest dostępny w itertools dokumentacji . Jest również dostępny w toolzbibliotece innej firmy :

from toolz import unique

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

# lazy iterator
res = map(list, unique(map(tuple, k)))

print(list(res))

[[1, 2], [4], [5, 6, 2], [3]]

Zwróć uwagę, że tuplekonwersja jest konieczna, ponieważ listy nie podlegają hashowaniu.

Nawet twoja „długa” lista jest dość krótka. Czy wybrałeś je tak, aby pasowały do ​​rzeczywistych danych? Wydajność będzie się różnić w zależności od tego, jak faktycznie wyglądają te dane. Na przykład, masz krótką listę powtarzaną w kółko, aby utworzyć dłuższą listę. Oznacza to, że rozwiązanie kwadratowe jest liniowe w twoich benchmarkach, ale nie w rzeczywistości.

W przypadku faktycznie dużych list najlepszym rozwiązaniem jest zestaw kod - jest liniowy (chociaż wymaga dużej przestrzeni). Metody sortowania i grupowania to O (n log n), a pętla w metodzie jest oczywiście kwadratowa, więc wiesz, jak będą się one skalować, gdy n stanie się naprawdę duże. Jeśli to jest rzeczywisty rozmiar analizowanych danych, to kogo to obchodzi? Jest malutki.

Nawiasem mówiąc, widzę zauważalne przyspieszenie, jeśli nie utworzę listy pośredniej, aby zrobić zestaw, to znaczy jeśli wymienię

kt = [tuple(i) for i in k]
skt = set(kt)

z

skt = set(tuple(i) for i in k)

Prawdziwe rozwiązanie może zależeć od większej ilości informacji: Czy jesteś pewien, że lista list jest naprawdę reprezentacją, której potrzebujesz?

Lista krotek i {} może służyć do usuwania duplikatów

>>> [list(tupl) for tupl in {tuple(item) for item in k }]
[[1, 2], [5, 6, 2], [3], [4]]
>>> 

Utwórz słownik z krotką jako kluczem i wydrukuj klucze.

• utwórz słownik z krotką jako kluczem i indeksem jako wartością
• wydrukować listę kluczy słownika

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

dict_tuple = {tuple(item): index for index, item in enumerate(k)}

print [list(itm) for itm in dict_tuple.keys()]

# prints [[1, 2], [5, 6, 2], [3], [4]]

To powinno działać.

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

k_cleaned = []
for ele in k:
    if set(ele) not in [set(x) for x in k_cleaned]:
        k_cleaned.append(ele)
print(k_cleaned)

# output: [[1, 2], [4], [5, 6, 2], [3]]

O dziwo, powyższe odpowiedzi usuwają „duplikaty”, ale co jeśli chcę usunąć również zduplikowaną wartość? Poniższe powinny być przydatne i nie tworzą nowego obiektu w pamięci!

def dictRemoveDuplicates(self):
    a=[[1,'somevalue1'],[1,'somevalue2'],[2,'somevalue1'],[3,'somevalue4'],[5,'somevalue5'],[5,'somevalue1'],[5,'somevalue1'],[5,'somevalue8'],[6,'somevalue9'],[6,'somevalue0'],[6,'somevalue1'],[7,'somevalue7']]


print(a)
temp = 0
position = -1
for pageNo, item in a:
    position+=1
    if pageNo != temp:
        temp = pageNo
        continue
    else:
        a[position] = 0
        a[position - 1] = 0
a = [x for x in a if x != 0]         
print(a)

a o / p to:

[[1, 'somevalue1'], [1, 'somevalue2'], [2, 'somevalue1'], [3, 'somevalue4'], [5, 'somevalue5'], [5, 'somevalue1'], [5, 'somevalue1'], [5, 'somevalue8'], [6, 'somevalue9'], [6, 'somevalue0'], [6, 'somevalue1'], [7, 'somevalue7']]
[[2, 'somevalue1'], [3, 'somevalue4'], [7, 'somevalue7']]

Innym, prawdopodobnie bardziej ogólnym i prostszym rozwiązaniem jest utworzenie słownika z kluczem w wersji łańcuchowej obiektów i pobranie na końcu wartości ():

>>> dict([(unicode(a),a) for a in [["A", "A"], ["A", "A"], ["A", "B"]]]).values()
[['A', 'B'], ['A', 'A']]

Problem polega na tym, że działa to tylko w przypadku obiektów, których reprezentacja w postaci łańcucha jest wystarczająco dobrym kluczem unikalnym (co jest prawdą dla większości obiektów natywnych).