Entfernt Duplikate aus einer Liste von Listen

Habe ich eine Liste von Listen in Python:

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

Und ich wollen zum entfernen doppelter Elemente aus. War, wenn es eine normale Liste nicht Listen, ich könnte verwendet werden set. Aber schade, dass die Liste nicht hashable und nicht eine Menge von Listen. Nur von Tupeln. So kann ich alle Listen in Tupel verwenden und wieder zu Listen. Aber das ist nicht schnell.

Wie kann dies in die effizienteste Art und Weise?

Dem Ergebnis der oben genannten Liste sollten sein:

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

I don ' T care zu bewahren, um.

Hinweis: diese Frage ist ähnlich, aber nicht ganz das, was ich brauche. Gesucht SO aber nicht finden Sie genaue doppelte.


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" (quadratische Methode) am schnellsten von allen für kurze Listen. Für lange Listen, es ist schneller als alle außer groupby-Methode. Macht das Sinn?

Für kurze Liste (die in der "code"), 100000 Iterationen:

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

Für längere Liste (die in der code dupliziert 5 mal):

[set] Elapsed: 3.68700003624
[sort] Elapsed: 3.43799996376
[groupby] Elapsed: 1.03099989891
[loop in] Elapsed: 1.85900020599
Von "das ist nicht schnell", meinst du, dass Sie überschritten haben, und es ist nicht schnell genug für Ihre Anwendung ist, oder, dass Sie denken, es ist nicht schnell?
es scheint nur, wie zu viel kopieren werden die smart-Methode. sorry, Bauchgefühl. kopieren Sie die Listen Tupel, dann ins set und dann zurück auf die Liste der Listen (Kopie wieder Tupeln, Listen)
das ist nicht, wie Python funktioniert, nichts wird kopiert, nur neue Behälter für die vorhandenen Elemente ( obwohl für ints, es ist so ziemlich das gleiche )
1. die timings für die Methoden mit Sortierung sind Sie entlüftet werden, denn "k" ist der rebound, um die sortierte Variante. 2. Die Letzte Methode ist schneller, da die Art der Erzeugung der Testdaten lässt Sie mit höchstens 4 Elementen. Versuchen sth. wie K = [[int(u) für u in str(random.randrange(1, 1000))] for _ in range(100)]
behoben, danke. aber immer noch der loop-Methode ist schnell, auch wenn es nur ein Duplikat in der Liste der 10

InformationsquelleAutor zaharpopov | 2010-02-06

Schreibe einen Kommentar