Doppelte Zeilen entfernen

[guy12]

hallo zusammen ich habe eine Frage : wie kann man mit Python programm durch dictionary doppelte zeilen entfernen so dass es nur eine zeile von diesen 2 bleiben
Danke im voraus
ich werde mich sehr freuen wenn jemand mir hilfe kann

[BlackJack]

Das macht man nicht mit Wörterbüchern sondern mit dem Mengentyp: `set`.

[snafu]

Bzw mit einem Set und einer Liste, falls die Reihenfolge der Zeilen (bezogen auf deren erstes Auftreten) erhalten bleiben soll.

[Hyperion]

Bzw mit einem Set und einer Liste, falls die Reihenfolge der Zeilen (bezogen auf deren erstes Auftreten) erhalten bleiben soll.

Falls man die Zeile nicht wieder direkt in eine Datei schreibt - dann kann man sich die Liste natürlich auch sparen.

[snafu]

Bzw mit einem Set und einer Liste, falls die Reihenfolge der Zeilen (bezogen auf deren erstes Auftreten) erhalten bleiben soll.

Falls man die Zeile nicht wieder direkt in eine Datei schreibt - dann kann man sich die Liste natürlich auch sparen.

Richtig. Oder man abstrahiert das erstmal als eine kleine Generator-Funktion. Je nachdem, was man halt haben möchte.

[mutetella]

Jetzt seid doch mal nicht so unflexibel... Wenn man will, dann kann man das auch mit einem Dictionary lösen:

Code: Alles auswählen

def unique(iterable):
    iterable = list(iterable)
    lookup = dict(enumerate(iterable))
    for index in lookup:
        occurences = iterable.count(lookup[index])
        if occurences > 1:
            for _ in range(occurences - 1):
                iterable.pop(iterable.index(lookup[index]))
    return iterable

mutetella

[Hyperion]

Tse tse tse... du hättest Dir wenigstens noch die Mühe machen können, uns die Laufzeit von Deinem obfuscated "Meisterwerk" zu nennen

[mutetella]

@Hyperion
Wollte ich eigentlich gleich nachreichen, aber `timeit` läuft immer noch...

[jerch]

@mutetella: Kleiner Optimierungstipp - wenn Du die Elemente mit BogoSort schön in Reihe bringst, sparst Du bestimmt nochmal n'Viertel oder halbes n von Deinem ~O(n^4)

[mutetella]

Nachdem wir etwas ähnliches erst kürzlich in diesem Thread hatten, hat mich das jetzt doch noch gebitz'lt, wie eine sinnvolle Lösung mit einem Dictionary wohl abschneidet:

Code: Alles auswählen

def unique_with_list(test):
    result = []
    for element in test:
        if not element in result:
            result.append(element)
    return result

def unique_with_set(test):
    seen = set()
    result = list()
    for item in test:
        if item not in seen:
            result.append(item)
            seen.add(item)
    return result

def unique_with_dict(test):
    unsorted = {}
    for index, element in enumerate(test):
        unsorted.setdefault(element, index)
    return [item[0] for item in sorted(unsorted.items(), key=lambda i: i[1])]

def unique_with_dict_1(test):
    unsorted = {}
    for index, element in enumerate(test):
        unsorted.setdefault(element, index)
    result = [None for _ in xrange(len(unsorted))]
    for item in unsorted.iteritems():
        result[item[1]] = item[0]
    return result

Code: Alles auswählen

In [11]: test = [
   ....: ''.join(random.choice(string.ascii_letters) for
   ....: _ in range(3)) for _ in range(200)
   ....: ]

In [12]: timeit unique_with_list(test)
1000 loops, best of 3: 268 µs per loop

In [13]: timeit unique_with_set(test)
10000 loops, best of 3: 56.3 µs per loop

In [14]: timeit unique_with_dict(test)
10000 loops, best of 3: 141 µs per loop

In [15]: timeit unique_with_dict_1(test)
10000 loops, best of 3: 86.4 µs per loop

Natürlich lässt das hier wieder jeden kalt, weil's ja eh klar war und gar nicht anderst sein kann . Ich allerdings hätte das nicht erwartet...

mutetella

[Sirius3]

Lösung "unique_with_dict_1" ist nicht nur unpythonisch, sondern auch fehlerhaft. Index kann bis len(test)-1 gehen, result hat aber nur die Länge von unsorted. Und ja, es ist klar dass dict langsamer ist als set, da das dict extra noch sortiert werden muß.

[BlackJack]

@mutetella: Anmerkungen:

Code: Alles auswählen

    result = [None for _ in xrange(len(unsorted))]

    # =>

    result = [None] * len(unsorted)

Es fehlt auch noch die IMHO naheliegenste Variante das Wörterbuch einfach als Menge zu verwenden:

Code: Alles auswählen

def unique_with_dict_2(items):
    seen = dict()
    result = list()
    for item in items:
        if item not in seen:
            result.append(item)
            seen[item] = item
    return result

Bei der Liste hätte ich den ``not in``-Operator verwendet. Das sind zwar zwei Worte, aber das ist *ein* Operator, im Gegensatz zu ``not a in b`` wo man erst den ``in``-Operator verwendet und danach das Ergebnis mit ``not`` negiert.

[mutetella]

Lösung "unique_with_dict_1" ist nicht nur unpythonisch, ...

... sondern auch nicht wirklich ernst gemeint...

... sondern auch fehlerhaft. Index kann bis len(test)-1 gehen, result hat aber nur die Länge von unsorted.

Ja, `index` kann bis ``len(test) - 1`` gehen, aber `result` soll ja immer nur so groß wie `unsorted` sein. Oder verstehe ich Dich falsch?

Code: Alles auswählen

result = [None for _ in xrange(len(unsorted))]
 
# =>
 
result = [None] * len(unsorted)

Das bringt tatsächlich auch nochmal was...

Code: Alles auswählen

In [6]: timeit equal_items.unique_with_dict_1_lc(equal_items.test)
10000 loops, best of 3: 84.8 µs per loop

In [7]: timeit equal_items.unique_with_dict_1_mul(equal_items.test)
10000 loops, best of 3: 76.6 µs per loop

Es fehlt auch noch die IMHO naheliegenste Variante das Wörterbuch einfach als Menge zu verwenden:

Die dann tatsächlich schneller als die `set`-Variante ist:

Code: Alles auswählen

In [10]: timeit equal_items.unique_with_set(equal_items.test)
10000 loops, best of 3: 56.9 µs per loop

In [11]: timeit equal_items.unique_with_dict_2(equal_items.test) 
10000 loops, best of 3: 44.8 µs per loop

Toll!!

mutetella

[Hyperion]

Es fehlt auch noch die IMHO naheliegenste Variante das Wörterbuch einfach als Menge zu verwenden:

Die dann tatsächlich schneller als die `set`-Variante ist:

Das überrascht mich schon ein wenig - ich hätte da ja auf quasi Gleichstand getippt... (beides Hash basiert; sofern beide Implementierungen die selben Mechanismen nutzen, sollte es da doch zeitlich keinen Unterschied geben‽)

[/me]

Kürzeren Code bekommt man ja so.

Code: Alles auswählen

def unique_with_ordered_dict(test):
    return list(collections.OrderedDict.fromkeys(test))

Die Performance habe ich jetzt nicht getestet, dürfte aber relativ schlecht sein.

[BlackJack]

@Hyperion: Ich vermute mal ganz stark das liegt an der Implementierung weil bei einem ``a[x] = x`` der Compiler schon erkennen kann welche Methode hier aufgerufen wird, im Gegensatz zu ``a.add(x)`` wo wahrscheinlich tatsächlich erst einmal, und jedes mal, die `add()`-Methode vom Objekt abgefragt wird. Wenn man sich das mal als Bytecodes anschaut:

Code: Alles auswählen

In [1]: def f():
   ...:     a[x] = x
   ...:     b.add(x)
   ...: 

In [2]: import dis

In [3]: dis.dis(f)
  2           0 LOAD_GLOBAL              0 (x)
              3 LOAD_GLOBAL              1 (a)
              6 LOAD_GLOBAL              0 (x)
              9 STORE_SUBSCR        

  3          10 LOAD_GLOBAL              2 (b)
             13 LOAD_ATTR                3 (add)
             16 LOAD_GLOBAL              0 (x)
             19 CALL_FUNCTION            1
             22 POP_TOP             
             23 LOAD_CONST               0 (None)
             26 RETURN_VALUE 

Würde ich also als Implementierungsdetail ansehen: Bei anderen Implementierungen könnte die Attributzuweisung langsamer sein wenn sie nicht als Sonderfall behandelt wird, und andererseits könnte ich mir vorstellen, dass eine Implementierung den zweiten Fall auch optimieren könnte.

[EyDu]

@Hyperion: Ich vermute mal ganz stark das liegt an der Implementierung weil bei einem ``a[x] = x`` der Compiler schon erkennen kann welche Methode hier aufgerufen wird, im Gegensatz zu ``a.add(x)`` wo wahrscheinlich tatsächlich erst einmal, und jedes mal, die `add()`-Methode vom Objekt abgefragt wird.

Ja, daran sollte es liegen. Wird die Auflösung von add herausgezogen

Code: Alles auswählen

def unique_with_set_2(test):
    seen = set()
    result = list()
    add = seen.add
    for item in test:
        if item not in seen:
            result.append(item)
            add(item)
    return result

so sind die Zeiten fast identisch:

Code: Alles auswählen

In [2]: timeit unique_with_set_2(test)
10000 loops, best of 3: 40.7 µs per loop

In [3]: timeit unique_with_dict_2(test)
10000 loops, best of 3: 40.8 µs per loop

[mutetella]

@/me
`OrderedDict` hatte ich anfangs auch gleich im Sinn, war aber wie Du vermutest von der Performance unter ferner liefen...

mutetella