Über Liste iterieren und Element entfernen

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
alan
User
Beiträge: 81
Registriert: Dienstag 10. April 2007, 11:30

Samstag 8. September 2007, 16:53

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
:wink:
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Samstag 8. September 2007, 17:05

Dann entferne nicht aus der Liste über die du iterierst, sondern hänge einfach an eine neue Liste an.
Zuletzt geändert von Leonidas am Samstag 8. September 2007, 19:31, insgesamt 1-mal geändert.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Samstag 8. September 2007, 17:13

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
User
Beiträge: 81
Registriert: Dienstag 10. April 2007, 11:30

Samstag 8. September 2007, 18:11

@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?
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Samstag 8. September 2007, 19:39

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

Samstag 8. September 2007, 20:19

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
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Sonntag 9. September 2007, 11:42

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
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Sonntag 9. September 2007, 11:46

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.
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Sonntag 9. September 2007, 11:47

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
User
Beiträge: 81
Registriert: Dienstag 10. April 2007, 11:30

Sonntag 9. September 2007, 20:40

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 :wink:

@Joghurt
Ich hätte die Kopie erstellt mit

Code: Alles auswählen

books_copy = []
books_copy.extend(books)
Macht das einen Unterschied?
BlackJack

Sonntag 9. September 2007, 22:10

Kopie: Ausser das es zwei Anweisungen sind und unüblich, macht es keinen Unterschied. Idiomatisch sind ``books_copy = books[:]`` oder ``books_copy = list(books)``.
Benutzeravatar
tromai
User
Beiträge: 92
Registriert: Mittwoch 26. April 2006, 11:20

Montag 10. September 2007, 08:14

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

Montag 10. September 2007, 08:46

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.
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Montag 10. September 2007, 18:55

alan hat geschrieben: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
Antworten