Über Liste iterieren und Element entfernen

[alan]

Hallo

Ich will über eine Liste iterieren, um jedes Element mit jedem zu vergleichen und unter bestimmten Bedingungen aus der Liste zu entfernen, hab also zwei verschachtelte for-Schleifen:

Code: Alles auswählen

iterBooks = books
for book in iterBooks:
    if book.flag:
        for book2 in iterBooks:
            if book.value == book2.value:
                # remove book
                iterBooks.remove(book) # quatsch

Mein Problem dabei ist: Ich kann schlecht die betreffenden Elemente aus der Liste löschen, die ich auch als Iterator für die beiden Schleifen verwende. Also iteriere ich über die Kopie. Aber: Da die Reihenfolge für den Vergleich keine Rolle spielt, wird unbeabsichtigerweise zweimal iterBooks.remove() ausgeführt.

Beispiel:

Code: Alles auswählen

# book ist eine Klasse
books = [book("a", True), book("b", False), book("a", True)

Hier würde zuerst beim Vergleich von books[0] mit book[2] das Element book[0] entfert und dann beim Vergleich von boos[2] mit books[0] das Element book[2] entfernt. Wirklich entfernt werden soll aber nur book[0].

Ich hoffe, dass ich mein Problem einigermaßen nachvollziehbar beschrieben habe

[Leonidas]

Dann entferne nicht aus der Liste über die du iterierst, sondern hänge einfach an eine neue Liste an.

[HWK]

Du hast ja gar keine Kopie erstellt, sondern nur einen 2. Namen für ein Objekt vergeben. book verschwindet nach remove(book) also komplett und kann nicht noch mal verglichen werden.
MfG
HWK

[alan]

@HWK
Da hast allerdings Recht

@Leonidas
Und wie schaffe ich es, dass dann doch ein Element hinzugefügt wird, und nicht keines? Eine Hilfsvariable einführen? Oder geht es eleganter?

[HWK]

Das wäre vielleicht eine Möglichkeit:

Code: Alles auswählen

new_books = []
for book in books:
    if not book.flag:
        new_books.append(book)
        continue
    for book_ in new_books:
        if book.value == book_.value:
            break
    else:
        new_books.append(book)

MfG
HWK

[BlackJack]

Das sieht von der Laufzeit alles so quadratisch aus. Effizienter wäre wahrscheinlich ein Dictionary zu benutzen. Die Reihenfolge der Bücher ändert sich dann allerdings:

Code: Alles auswählen

books = dict((book.value, book) for book in books).values()

Eventuell würde es auch Sinn machen bei den Bücherobjekten die `__cmp__()`- und die `__hash__()`-Methode zu implementieren, so dass man ein `set()` benutzen kann.

[Joghurt]

BlackJack hat natürlich recht mit der quadratischen Laufzeit und du solltest sich an seiner Lösung orientieren.

Das Problem, was du hast, nämlich das Iterieren über eine Liste, die man verändern will, löst man im allgemeinen dadurch, dass man über eine Kopie der Liste iteriert, dies kann man einfach mit dem Sliceoperator ohne Parameter, [:] erreichen. Der Code sähe dann so aus:

Code: Alles auswählen

books_copy = books[:]
for book in books_copy:
    if book.flag:
        for book2 in books_copy:
            if book.value == book2.value:
                # remove book
                books.remove(book)

Wenn man nur einmal drüber iteriert, schreibt man oft den Slice-operator direkt ins for:

Code: Alles auswählen

for foo in foos[:]:
    # mach etwas mit foos

[Joghurt]

PS: Dein Code hat noch einen Logikbug: Sobald ein Buch das Flag gesetzt hat, werden alle Bücher, die den selben Wert haben, entfernt. Also auch das Buch, das das Flag gesetzt hat.

[HWK]

Wobei wir dann aber wieder bei alans Problem wären, dass nämlich das Paar zweimal verglichen wird und somit beide Vorkommen gelöscht werden. Noch schlimmer sogar: Da auch jedes Element mit sich selbst verglichen wird, werden alle Elemente mit flag == True gelöscht.
MfG
HWK

[alan]

Wobei wir dann aber wieder bei alans Problem wären, dass nämlich das Paar zweimal verglichen wird und somit beide Vorkommen gelöscht werden. Noch schlimmer sogar: Da auch jedes Element mit sich selbst verglichen wird, werden alle Elemente mit flag == True gelöscht.
MfG
HWK

Genau, das ist mein Problem

Ich werde es mal mit BlackJacks Vorschlag probieren und schreien, wenn ichs nicht hinbekomm

@Joghurt
Ich hätte die Kopie erstellt mit

Code: Alles auswählen

books_copy = []
books_copy.extend(books)

Macht das einen Unterschied?

[BlackJack]

Kopie: Ausser das es zwei Anweisungen sind und unüblich, macht es keinen Unterschied. Idiomatisch sind ``books_copy = books[:]`` oder ``books_copy = list(books)``.

[tromai]

Wie ist das eigentlich, wenn ich über eine Liste iteriere aus der ich etwas lösche? Wenn ich da eine normale for-Schleife mache bekommt er da ja auch Probleme, oder? Zumindest greift er da bei mir nicht jedes Element an, da er mit den Indizes Probleme bekommt, wenn ich es auf konventionelle Art löse.

Ich habe das bisher dadurch gelöst, dass ich von hinten nach vorne iteriere. dann hat er da keine Probleme. Gibt es noch eine andere Möglichkeit?

[BlackJack]

Der Iterator über die Liste hat einen internen Zähler welcher Index als nächstes zurückgegeben werden soll. Und dieser Zähler bekommt nichts davon mit, wenn ein Element aus der Liste gelöscht wird und damit alle folgenden Elemente einen Index nach vorne verschoben werden.

Am besten man löscht so nicht aus Listen sondern baut eine neue, gefilterte Liste auf. Das dürfte von der Laufzeit am günstigsten sein und sieht im Quelltext im Gegensatz zu den Alternativen auch am einfachsten aus.

[HWK]

Ich hätte die Kopie erstellt mit

Code: Alles auswählen

books_copy = []
books_copy.extend(books)

Macht das einen Unterschied?

In diesem Zusammenhang sollten noch aus dem copy-Modul copy und insbesondere deepcopy (da es bei manchen Listen schon einen Unterschied macht) erwähnt werden.
MfG
HWK