Apa cara paling pythonic untuk mengeluarkan elemen acak dari daftar?

Katakanlah saya memiliki daftar xdengan panjang tidak diketahui dari mana saya ingin memunculkan satu elemen secara acak sehingga daftar tersebut tidak berisi elemen setelahnya. Apa cara paling pythonic untuk melakukan ini?

Saya bisa melakukannya dengan menggunakan combincation agak unhandy dari pop, random.randint, dan len, dan ingin melihat solusi yang lebih pendek atau lebih bagus:

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

Apa yang saya coba capai adalah secara berurutan memunculkan elemen acak dari daftar. (yaitu, pop satu elemen secara acak dan pindahkan ke kamus, pop elemen lain secara acak dan pindahkan ke kamus lain, ...)

Perhatikan bahwa saya menggunakan Python 2.6 dan tidak menemukan solusi apa pun melalui fungsi pencarian.

Apa yang tampaknya Anda lakukan tidak terlihat sangat Pythonic di tempat pertama. Anda tidak boleh menghapus barang-barang dari tengah daftar, karena daftar diimplementasikan sebagai array di semua implementasi Python yang saya ketahui, jadi ini adalah O(n)operasi.

Jika Anda benar-benar membutuhkan fungsionalitas ini sebagai bagian dari algoritme, Anda harus memeriksa struktur data seperti blistyang mendukung penghapusan efisien dari tengah.

Dalam Python murni, apa yang dapat Anda lakukan jika Anda tidak membutuhkan akses ke elemen yang tersisa hanyalah mengocok daftar terlebih dahulu dan kemudian mengulanginya:

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

Jika Anda benar-benar membutuhkan sisanya (yang sedikit berbau kode, IMHO), setidaknya Anda dapat pop()dari akhir daftar sekarang (yang cepat!):

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

Secara umum, Anda sering dapat mengekspresikan program Anda dengan lebih elegan jika Anda menggunakan gaya yang lebih fungsional, daripada status mutasi (seperti yang Anda lakukan dengan daftar).

Anda tidak akan menjadi lebih baik dari itu, tetapi berikut ini sedikit perbaikan:

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

Dokumentasi tentang random.randrange():

random.randrange ([start], stop [, step])
Mengembalikan elemen yang dipilih secara acak dari range(start, stop, step). Ini sama dengan choice(range(start, stop, step)), tetapi tidak benar-benar membangun objek jangkauan.

Untuk menghapus satu elemen pada indeks acak dari daftar jika urutan elemen daftar lainnya tidak menjadi masalah:

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)

Swap digunakan untuk menghindari perilaku O (n) saat penghapusan dari tengah daftar.

Berikut alternatif lain: mengapa Anda tidak mengocok daftar terlebih dahulu , lalu mulai memunculkan elemen-elemennya hingga tidak ada lagi elemen yang tersisa? seperti ini:

import random

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

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

Salah satu cara untuk melakukannya adalah:

x.remove(random.choice(x))

Meskipun tidak muncul dari daftar, saya menemukan pertanyaan ini di Google saat mencoba mendapatkan X item acak dari daftar tanpa duplikat. Inilah yang akhirnya saya gunakan:

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

Ini mungkin sedikit tidak efisien karena Anda mengacak seluruh daftar tetapi hanya menggunakan sebagian kecil saja, tetapi saya bukan ahli pengoptimalan jadi saya bisa saja salah.

Saya tahu ini pertanyaan lama, tapi hanya demi dokumentasi:

Jika Anda (orang googling pertanyaan yang sama) melakukan apa yang saya pikir Anda lakukan, yaitu memilih k jumlah item secara acak dari daftar (di mana k <= len (daftar Anda)), tetapi pastikan setiap item tidak pernah dipilih lebih dari satu kali (= sampling tanpa penggantian), Anda dapat menggunakan random.sample seperti yang disarankan @ jf-sebastian. Tetapi tanpa mengetahui lebih banyak tentang kasus penggunaan, saya tidak tahu apakah ini yang Anda butuhkan.

meskipun banyak jawaban menyarankan penggunaan random.shuffle(x)dan x.pop()sangat lambat pada data besar. dan waktu yang dibutuhkan dalam daftar 10000elemen membutuhkan waktu sekitar 6 secondssaat pengacakan diaktifkan. ketika shuffle dinonaktifkan, kecepatan itu0.2s

metode tercepat setelah menguji semua metode yang diberikan di atas ternyata ditulis oleh @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)

untuk mendukung klaim saya di sini adalah grafik kompleksitas waktu dari sumber ini

JIKA tidak ada duplikat dalam daftar,

Anda dapat mencapai tujuan Anda menggunakan set juga. setelah daftar dibuat menjadi set duplikat akan dihapus. remove by valuedan remove randombiaya O(1), yaitu sangat efisien. ini adalah metode terbersih yang bisa saya lakukan.

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.

Tidak seperti opsi listsdukungan mana A+B, setsjuga mendukung A-B (A minus B)bersama A+B (A union B)dan A.intersection(B,C,D). sangat berguna ketika Anda ingin melakukan operasi logis pada data.

PILIHAN

JIKA Anda ingin kecepatan saat operasi dilakukan di head dan tail of list, gunakan python dequeue (double ended queue) untuk mendukung klaim saya di sini adalah gambarnya. sebuah gambar adalah ribuan kata.

Jawaban ini berasal dari @ niklas-b :

" Anda mungkin ingin menggunakan sesuatu seperti pypi.python.org/pypi/blist "

Mengutip halaman PYPI :

... tipe seperti daftar dengan kinerja asimtotik yang lebih baik dan kinerja serupa pada daftar kecil

Blist adalah pengganti drop-in untuk daftar Python yang memberikan kinerja lebih baik saat memodifikasi daftar yang besar. Paket blist juga menyediakan tipe sortlist, sortset, weaksortedlist, weaksortedset, sorteddict, dan btuple.

Seseorang akan berasumsi kinerja yang lebih rendah pada akses acak / run end acak , karena ini adalah struktur data "salinan saat menulis". Ini melanggar banyak asumsi kasus penggunaan pada daftar Python, jadi gunakan dengan hati-hati .

NAMUN, jika kasus penggunaan utama Anda adalah melakukan sesuatu yang aneh dan tidak wajar dengan daftar (seperti dalam contoh paksa yang diberikan oleh @OP, atau masalah antrian FIFO dengan pass-over Python 2.6 saya), maka ini akan sesuai dengan tagihan dengan baik .