Jaki jest najbardziej pythonowy sposób na zdejmowanie losowego elementu z listy?

Powiedzmy, że mam listę xo nieznanej długości, z której chcę losowo zdjąć jeden element, aby lista nie zawierała później elementu. Jaki jest najbardziej pythonowy sposób na zrobienie tego?

Można to zrobić przy użyciu raczej niepraktyczny combincation o pop, random.randinti len, i chciałby, aby krótsze lub ładniejsze rozwiązania:

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

To, co próbuję osiągnąć, to kolejno zdejmować losowe elementy z listy. (tj. losowo przesuń jeden element i przenieś go do słownika, losowo przesuń inny element i przenieś go do innego słownika, ...)

Zauważ, że używam Pythona 2.6 i nie znalazłem żadnych rozwiązań za pomocą funkcji wyszukiwania.

Wydaje się, że to, co zamierzasz, nie wygląda zbyt Pythonicznie. Nie powinieneś usuwać rzeczy ze środka listy, ponieważ listy są implementowane jako tablice we wszystkich implementacjach Pythona, które znam, więc jest to O(n)operacja.

Jeśli naprawdę potrzebujesz tej funkcji jako części algorytmu, powinieneś sprawdzić strukturę danych, taką jak ta, blistktóra obsługuje wydajne usuwanie od środka.

W czystym Pythonie, jeśli nie potrzebujesz dostępu do pozostałych elementów, wystarczy najpierw przetasować listę, a następnie ją powtórzyć:

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

Jeśli naprawdę potrzebujesz reszty (co jest odrobiną zapachu kodu, IMHO), przynajmniej możesz teraz pop()od końca listy (co jest szybkie!):

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

Ogólnie rzecz biorąc, możesz często bardziej elegancko przedstawiać swoje programy, jeśli używasz bardziej funkcjonalnego stylu zamiast mutowania stanu (tak jak robisz to z listą).

Nie dostaniesz nic lepszego, ale tutaj jest niewielka poprawa:

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

Dokumentacja dotycząca random.randrange():

random.randrange ([start], stop [, step])
Zwraca losowo wybrany element z range(start, stop, step). Jest to równoważne choice(range(start, stop, step)), ale w rzeczywistości nie tworzy obiektu zakresu.

Aby usunąć pojedynczy element o losowym indeksie z listy, jeśli kolejność pozostałych elementów listy nie ma znaczenia:

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)

Zamiana jest używana do uniknięcia zachowania O (n) przy usuwaniu ze środka listy.

Oto kolejna alternatywa: dlaczego nie można przetasować listę pierwszy , a następnie rozpocząć pojawiały elementy, dopóki nie więcej elementy pozostają? lubię to:

import random

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

while x:
    p = x.pop()
    # do your stuff with p

Jednym ze sposobów jest:

x.remove(random.choice(x))

Chociaż nie wyskoczyłem z listy, napotkałem to pytanie w Google, próbując pobrać X losowych pozycji z listy bez duplikatów. Oto, czego ostatecznie użyłem:

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

Może to być nieco nieefektywne, ponieważ tasujesz całą listę, ale używasz tylko niewielkiej jej części, ale nie jestem ekspertem od optymalizacji, więc mogę się mylić.

Wiem, że to stare pytanie, ale ze względu na dokumentację:

Jeśli Ty (osoba wpisująca w Google to samo pytanie) robisz to, co myślę, że robisz, czyli losowo wybierasz k liczby pozycji z listy (gdzie k <= len (twoja lista)), ale upewniając się, że każdy element nigdy nie zostanie wybrany więcej niż jeden raz (= próbkowanie bez zamiany), możesz użyć random.sample, jak sugeruje @ jf-sebastian. Ale nie wiedząc więcej o przypadku użycia, nie wiem, czy tego potrzebujesz.

Ta odpowiedź jest dzięki uprzejmości @ niklas-b :

„ Prawdopodobnie chcesz użyć czegoś takiego jak pypi.python.org/pypi/blist ”

Aby zacytować stronę PYPI :

... typ listowy z lepszą wydajnością asymptotyczną i podobną wydajnością na małych listach

Blist jest zamiennikiem listy Pythona, który zapewnia lepszą wydajność podczas modyfikowania dużych list. Pakiet blist udostępnia również typy sortlist, sortset, weaksortedlist, weaksortedset, sortdict i btuple.

Można by założyć obniżoną wydajność na końcu losowego dostępu / losowego uruchomienia , ponieważ jest to struktura danych „kopia przy zapisie”. To narusza wiele założeń dotyczących przypadków użycia na listach Pythona, więc używaj go ostrożnie .

JEDNAK, jeśli twoim głównym przypadkiem użycia jest zrobienie czegoś dziwnego i nienaturalnego z listą (jak w wymuszonym przykładzie podanym przez @OP lub moim problemem kolejki FIFO w Pythonie 2.6), to będzie to dobrze pasować do rachunku .

pomimo wielu odpowiedzi sugerujących użycie random.shuffle(x)i x.pop()bardzo powolny w przypadku dużych danych. a czas potrzebny na liście 10000elementów zajął mniej więcej 6 secondspo włączeniu odtwarzania losowego. gdy odtwarzanie losowe jest wyłączone, prędkość wynosiła0.2s

najszybszą metodą po przetestowaniu wszystkich powyższych metod okazał się @jfs

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)

Na poparcie mojego twierdzenia jest tutaj wykres złożoności czasowej z tego źródła

JEŚLI na liście nie ma duplikatów,

możesz osiągnąć swój cel również za pomocą zestawów. gdy lista zostanie utworzona jako duplikaty zestawu, zostanie usunięta. remove by valuei remove randomkoszt O(1), czyli bardzo efektywny. to najczystsza metoda, jaką mogłem wymyślić.

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.

W przeciwieństwie do tej opcji listswsparcia A+B, setsobsługuje również A-B (A minus B)wraz z A+B (A union B)i A.intersection(B,C,D). bardzo przydatne, gdy chcesz wykonywać operacje logiczne na danych.

OPCJONALNY

Jeśli chcesz, aby operacje wykonywane na początku i końcu listy były szybkie, użyj dekolejki Pythona (kolejka podwójna) na poparcie mojego twierdzenia, oto obraz. obraz to tysiąc słów.