Quelle est la façon la plus pythonique d'extraire un élément aléatoire d'une liste ?

Question

Disons que j'ai une liste x de longueur inconnue dont je veux extraire un élément au hasard de sorte que la liste ne contienne plus cet élément par la suite. Quelle est la manière la plus pythonique de faire cela ?

Je peux le faire en utilisant une combinaison peu pratique de pop , random.randint y len et aimerait voir des solutions plus courtes ou plus agréables :

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

Ce que j'essaie de faire, c'est d'extraire consécutivement des éléments aléatoires d'une liste. (par exemple, extraire au hasard un élément et le déplacer dans un dictionnaire, extraire au hasard un autre élément et le déplacer dans un autre dictionnaire, ...).

Notez que j'utilise Python 2.6 et que je n'ai pas trouvé de solution via la fonction de recherche.

Answer 1

Ce que vous semblez faire ne semble pas très pythonique en premier lieu. Vous ne devriez pas enlever des choses au milieu d'une liste, parce que les listes sont implémentées comme des tableaux dans toutes les implémentations de Python que je connais, donc il s'agit d'un O(n) opération.

Si vous avez vraiment besoin de cette fonctionnalité dans le cadre d'un algorithme, vous devriez vous tourner vers une structure de données telle que la structure blist qui permet une suppression efficace du milieu.

En Python pur, ce que vous pouvez faire si vous n'avez pas besoin d'accéder aux éléments restants, c'est de mélanger la liste d'abord, puis d'itérer dessus :

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

Si vous ont vraiment besoin le reste (ce qui est un peu une odeur de code, IMHO), au moins vous pouvez pop() à partir de la fin de la liste (ce qui est rapide !) :

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

En général, vous pouvez souvent exprimer vos programmes de manière plus élégante si vous utilisez un style plus fonctionnel, au lieu de muter l'état (comme vous le faites avec la liste).

Answer 2

Vous n'obtiendrez pas beaucoup mieux, mais voici une légère amélioration :

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

Documentation sur random.randrange() :

random.randrange([start], stop[, step])
Renvoyer un élément sélectionné au hasard dans range(start, stop, step) . Cela équivaut à choice(range(start, stop, step)) mais ne construit pas réellement d'objet de plage.

Answer 3

Pour retirer un unique élément à un index aléatoire d'une liste si l'ordre du reste des éléments de la liste n'a pas d'importance :

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)

La permutation est utilisée pour éviter un comportement O(n) lors de la suppression d'un élément au milieu d'une liste.

Answer 4

Malgré de nombreuses réponses suggérant l'utilisation random.shuffle(x) et x.pop() Il est très lent pour les données volumineuses et le temps nécessaire à l'établissement d'une liste de données. 10000 Les éléments ont pris environ 6 seconds lorsque la lecture aléatoire est activée. lorsque la lecture aléatoire est désactivée la vitesse a été 0.2s

la méthode la plus rapide après avoir testé toutes les méthodes données ci-dessus s'est avérée être celle écrite par @jfs

import random

L = [1,"2",[3],(4),{5:"6"},'etc'] #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)

Pour étayer mon propos, voici le tableau de la complexité temporelle à partir de cette source

---

S'il n'y a pas de doublons dans la liste,

vous pouvez également atteindre votre objectif en utilisant des ensembles. une fois la liste établie en ensembles, les doublons seront supprimés. remove by value et remove random coût O(1) C'est la méthode la plus propre que j'ai trouvée.

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.

Contrairement à lists qui soutiennent A+B option, sets soutiennent également A-B (A minus B) ainsi que A+B (A union B) y A.intersection(B,C,D) . très utile lorsque vous souhaitez effectuer des opérations logiques sur les données.

---

OPTIONNEL

SI vous voulez de la rapidité lorsque des opérations sont effectuées sur la tête et la queue d'une liste, utilisez python dequeue (double ended queue) pour étayer mon propos voici l'image. une image vaut mille mots.

Answer 5

Voici une autre solution : pourquoi ne pas mélanger la liste ? premier et commence à en extraire des éléments jusqu'à ce qu'il n'en reste plus ? comme ceci :

import random

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

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