Was ist die pythonischste Art, ein zufälliges Element aus einer Liste zu entfernen?

88

Angenommen, ich habe eine Liste xmit unbekannter Länge, aus der ich zufällig ein Element entfernen möchte, damit die Liste das Element danach nicht mehr enthält. Was ist der pythonischste Weg, dies zu tun?

Ich kann es eine ziemlich unhandliche combincation der Verwendung pop, random.randintund len, und würde gerne kürzere oder schönere Lösungen sehen:

import random
x = [1,2,3,4,5,6]
x.pop(random.randint(0,len(x)-1))

Ich versuche, nacheinander zufällige Elemente aus einer Liste zu entfernen. (dh ein Element nach dem Zufallsprinzip einfügen und in ein Wörterbuch verschieben, ein anderes Element nach dem Zufallsprinzip einfügen und in ein anderes Wörterbuch verschieben, ...)

Beachten Sie, dass ich Python 2.6 verwende und über die Suchfunktion keine Lösungen gefunden habe.

Henrik
quelle
3
Ich bin kein großer Pythonist, aber das sieht für mich sicher ziemlich gut aus.
Matt Ball
Ich habe eine detaillierte Analyse der Zeitkomplexität durchgeführt. Siehe meine Antwort irgendwo in der Zukunft. SHUFFLE ist NICHT EFFIZIENT! Sie können es aber trotzdem verwenden, wenn Sie die Reihenfolge der Artikel irgendwie ändern müssen. Wenn Sie von pop (0) betroffen sind, verwenden Sie die in meiner Analyse erwähnte Warteschlange.
Nikil Swami
O (2) Zeitkomplexität für die Antwort ive geschrieben. Wickeln Sie es in eine Funktion für den schnellen Gebrauch. Bitte beachten Sie, dass jede andere list.pop (n) als list.pop (-1) O (n) nimmt.
Nikil Swami

Antworten:

95

Was Sie zu tun scheinen, sieht in erster Linie nicht sehr pythonisch aus. Sie sollten keine Inhalte aus der Mitte einer Liste entfernen, da Listen in allen mir bekannten Python-Implementierungen als Arrays implementiert sind. Dies ist also eine O(n)Operation.

Wenn Sie diese Funktionalität wirklich als Teil eines Algorithmus benötigen, sollten Sie eine Datenstruktur wie die überprüfen, die ein blisteffizientes Löschen aus der Mitte unterstützt.

In reinem Python können Sie, wenn Sie keinen Zugriff auf die verbleibenden Elemente benötigen, zuerst die Liste mischen und dann darüber iterieren:

lst = [1,2,3]
random.shuffle(lst)
for x in lst:
  # ...

Wenn Sie den Rest wirklich brauchen (was meiner Meinung nach ein bisschen nach Code riecht), können Sie dies zumindest pop()am Ende der Liste tun (was schnell ist!):

while lst:
  x = lst.pop()
  # do something with the element      

Im Allgemeinen können Sie Ihre Programme häufig eleganter ausdrücken, wenn Sie einen funktionaleren Stil verwenden, anstatt den Status zu ändern (wie Sie es mit der Liste tun).

Niklas B.
quelle
3
Eine bessere (schnellere) Idee wäre es also random.shuffle(x)und dann x.pop()? Ich verstehe nicht, wie man das "funktional" macht?
Henrik
1
@Henrik: Wenn Sie zwei Sammlungen haben (z. B. eine Liste von Wörterbüchern und eine Liste von Zufallszahlen) und diese gleichzeitig iterieren möchten, können zipSie eine Liste von (Diktat-, Zahlen-) Paaren abrufen. Sie haben etwas über mehrere Wörterbücher gesagt, von denen Sie jedes mit einer Zufallszahl verknüpfen möchten. zipist perfekt dafür
Niklas B.
2
Ich soll einen Beitrag hinzufügen, wenn ich abstimme. Es gibt Zeiten, in denen Sie ein Element aus der Mitte einer Liste entfernen müssen ... Ich muss es jetzt tun. Keine Wahl: Ich habe eine geordnete Liste, ich muss einen Artikel in der Mitte entfernen. Es ist scheiße, aber die einzige andere Möglichkeit besteht darin, ein umfangreiches Code-Refactoring für eine halb seltene Operation durchzuführen. Das Problem ist die Implementierung von [], die für solche Operationen effizient sein SOLLTE, aber nicht.
Mark Gerolimatos
5
@ NiklasB. Das OP verwendete Zufall als Beispiel (ehrlich gesagt hätte es weggelassen werden sollen, es trübte das Problem). "Tu das nicht" ist unzureichend. Eine bessere Antwort wäre gewesen, eine Python-Datenstruktur vorzuschlagen, die solche Operationen unterstützt und gleichzeitig eine AUSREICHENDE Zugriffsgeschwindigkeit bietet (eindeutig nicht so gut wie eine Arra ... er ... -Liste). In Python 2 konnte ich keinen finden. Wenn ich das tue, werde ich damit antworten. Beachten Sie, dass ich aufgrund eines Browser-Missgeschicks nicht in der Lage war, meinem ursprünglichen Kommentar einen sekundären Kommentar hinzuzufügen. Danke, dass du mich ehrlich gehalten hast :)
Mark Gerolimatos
1
@MarkGerolimatos Es gibt keine Datenstruktur mit effizientem Direktzugriff und Einfügen / Löschen in der Standardbibliothek. Sie möchten wahrscheinlich so etwas wie pypi.python.org/pypi/blist verwenden. Ich würde immer noch argumentieren, dass dies in vielen Anwendungsfällen vermieden werden kann
Niklas B.
50

Sie werden nicht viel besser als das, aber hier ist eine leichte Verbesserung:

x.pop(random.randrange(len(x)))

Dokumentation zu random.randrange():

random.randrange ([start], stop [, step]) Gibt
ein zufällig ausgewähltes Element von zurück range(start, stop, step). Dies entspricht choice(range(start, stop, step))einem Bereichsobjekt, erstellt es jedoch nicht.

Andrew Clark
quelle
14

So entfernen Sie ein einzelnes Element mit zufälligem Index aus einer Liste, wenn die Reihenfolge der übrigen Listenelemente keine Rolle spielt:

import random

L = [1,2,3,4,5,6]
i = random.randrange(len(L)) # get random index
L[i], L[-1] = L[-1], L[i]    # swap with the last element
x = L.pop()                  # pop last element O(1)

Der Swap wird verwendet, um das O (n) -Verhalten beim Löschen aus der Mitte einer Liste zu vermeiden.

jfs
quelle
9

Hier ist eine weitere Alternative: Warum mischen Sie nicht zuerst die Liste und beginnen dann, Elemente davon zu platzieren, bis keine Elemente mehr übrig sind? so was:

import random

x = [1,2,3,4,5,6]
random.shuffle(x)

while x:
    p = x.pop()
    # do your stuff with p
Óscar López
quelle
3
@ NiklasB. weil wir Elemente aus der Liste entfernen. Wenn es nicht unbedingt notwendig ist, Elemente zu entfernen, stimme ich Ihnen zu:[for p in x]
Óscar López
Da dies die Liste ändert und Sie nur die Hälfte der Elemente jetzt und die andere Hälfte später auswählen möchten, wird der verbleibende Satz später festgelegt.
Henrik
@ Henrik: Okay, deshalb habe ich dich gefragt, ob du die verbleibende Liste brauchst. Das hast du nicht beantwortet.
Niklas B.
2

Ein Weg, dies zu tun, ist:

x.remove(random.choice(x))
Simeon Visser
quelle
7
Dies kann problematisch werden, wenn Elemente mehrmals auftreten.
Niklas B.
2
Dadurch wird das Element ganz links entfernt, wenn Duplikate vorhanden sind, was zu einem nicht perfekt zufälligen Ergebnis führt.
FogleBird
Mit können popSie einen Namen auf das entfernte Element verweisen, mit diesem können Sie nicht.
Agf
Fairerweise stimme ich zu, dass dies nicht sehr zufällig ist, wenn Elemente mehr als einmal vorkommen.
Simeon Visser
1
Abgesehen von der Frage des Verzerren Ihrer Verteilung ist removeein linearer Scan der Liste erforderlich. Das ist schrecklich ineffizient im Vergleich zum Nachschlagen eines Index.
Aaronasterling
2

Während ich nicht aus der Liste auftauchte, stieß ich bei Google auf diese Frage, als ich versuchte, X zufällige Elemente aus einer Liste ohne Duplikate abzurufen. Folgendes habe ich schließlich verwendet:

items = [1, 2, 3, 4, 5]
items_needed = 2
from random import shuffle
shuffle(items)
for item in items[:items_needed]:
    print(item)

Dies kann etwas ineffizient sein, da Sie eine ganze Liste mischen, aber nur einen kleinen Teil davon verwenden, aber ich bin kein Optimierungsexperte, daher könnte ich mich irren.

Noah McIlraith
quelle
3
random.sample(items, items_needed)
JFS
2

Ich weiß, dass dies eine alte Frage ist, aber nur zur Dokumentation:

Wenn Sie (die Person, die dieselbe Frage googelt) das tun, was Sie meiner Meinung nach tun, wählen Sie k zufällig eine Anzahl von Elementen aus einer Liste aus (wobei k <= len (Ihre Liste)), stellen Sie jedoch sicher, dass jedes Element nie mehr ausgewählt wird mehr als einmal (= Stichprobe ohne Ersatz) könnten Sie random.sample verwenden, wie es @ jf-sebastian vorschlägt. Aber ohne mehr über den Anwendungsfall zu wissen, weiß ich nicht, ob Sie dies benötigen.

Dolf Andringa
quelle
2

trotz vielen Antworten Gebrauch was darauf hindeutet , random.shuffle(x)und x.pop()seine sehr langsam auf große Daten. und die für eine Liste von 10000Elementen erforderliche Zeit dauerte ungefähr, 6 secondswenn das Mischen aktiviert wurde. Wenn Shuffle deaktiviert ist, war die Geschwindigkeit0.2s

Die schnellste Methode nach dem Testen aller oben genannten Methoden wurde von @jfs geschrieben

import random

L = ['1',2,3,'4'...1000] #you can take mixed or pure list
i = random.randrange(len(L)) # get random index
L[i], L[-1] = L[-1], L[i]    # swap with the last element
x = L.pop()                  # pop last element O(1)

Zur Unterstützung meiner Behauptung hier ist das Zeitkomplexitätsdiagramm aus dieser Quelle Geben Sie hier die Bildbeschreibung ein


WENN die Liste keine Duplikate enthält,

Sie können Ihren Zweck auch mit Sets erreichen. Sobald die Liste zu festgelegten Duplikaten erstellt wurde, wird sie entfernt. remove by valueund remove randomKosten O(1), dh sehr effizient. Dies ist die sauberste Methode, die ich mir vorstellen kann.

L=set([1,2,3,4,5,6...]) #directly input the list to inbuilt function set()
while 1:
    r=L.pop()
    #do something with r , r is random element of initial list L.

Im Gegensatz zu listswelcher Support- A+BOption unterstützen Sie setsauch A-B (A minus B)zusammen mit A+B (A union B)und A.intersection(B,C,D). Sehr nützlich, wenn Sie logische Operationen an den Daten ausführen möchten.


OPTIONAL

Wenn Sie Geschwindigkeit wünschen, wenn Operationen an Kopf und Ende der Liste ausgeführt werden, verwenden Sie Python Dequeue (Double Ended Queue), um meine Behauptung zu unterstützen. Ein Bild besteht aus tausend Wörtern.

Geben Sie hier die Bildbeschreibung ein

Nikil Swami
quelle
1

Diese Antwort wurde freundlicherweise von @ niklas-b zur Verfügung gestellt :

" Sie möchten wahrscheinlich so etwas wie pypi.python.org/pypi/blist verwenden. "

So zitieren Sie die PYPI-Seite :

... ein listenartiger Typ mit besserer asymptotischer Leistung und ähnlicher Leistung auf kleinen Listen

Die Blist ist ein Drop-In-Ersatz für die Python-Liste, der beim Ändern großer Listen eine bessere Leistung bietet. Das Blist-Paket enthält auch die Typen sortierte Listen, sortierte Sätze, Weaksortierte Listen, Weaksortierte Sätze, Sortierte Diktate und Btupel.

Man würde eine verminderte Leistung am Ende des Direktzugriffs / Zufallslaufs annehmen , da es sich um eine Datenstruktur "Kopie beim Schreiben" handelt. Dies verstößt gegen viele Anwendungsfallannahmen in Python-Listen. Gehen Sie daher vorsichtig damit um .

Wenn Ihr Hauptanwendungsfall jedoch darin besteht, etwas Seltsames und Unnatürliches mit einer Liste zu tun (wie im erzwungenen Beispiel von @OP oder meinem Problem mit der Python 2.6-FIFO-FIFO-Warteschlange mit Übergabe), passt dies gut zur Rechnung .

Mark Gerolimatos
quelle