python - Obtenga una muestra aleatoria de la lista mientras mantiene el orden de los artículos?

plt.title bold

Question

Tengo una lista ordenada, digamos: (no son solo números, es una lista de objetos que se ordenan con un complicado algoritmo que consume mucho tiempo)

mylist = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ,9  , 10 ]

¿Hay alguna función de Python que me dará N de los elementos, pero mantendrá el orden?

Ejemplo:

randomList = getRandom(mylist,4)
# randomList = [ 3 , 6 ,7 , 9 ]
randomList = getRandom(mylist,4)
# randomList = [ 1 , 2 , 4 , 8 ]

etc ...

Answer 1

Manera simple de codificar O (N + K * log (K))

Tome una muestra aleatoria sin reemplazar los índices, clasifique los índices y tómelos del original.

indices = random.sample(range(len(myList)), K)
[myList[i] for i in sorted(indices)]

O más concisamente:

[x[1] for x in sorted(random.sample(enumerate(myList),K))]

Optimizado O (N) -time, O (1) -iespiary-space way

Alternativamente, puede utilizar un truco matemático e ir iterativamente a myList de izquierda a derecha, seleccionando números con probabilidad de cambio dinámico (N-numbersPicked)/(total-numbersVisited) . La ventaja de este enfoque es que es un algoritmo O(N) ya que no implica la clasificación.

from __future__ import division

def orderedSampleWithoutReplacement(seq, k):
    if not 0<=k<=len(seq):
        raise ValueError(''Required that 0 <= sample_size <= population_size'')

    numbersPicked = 0
    for i,number in enumerate(seq):
        prob = (k-numbersPicked)/(len(seq)-i)
        if random.random() < prob:
            yield number
            numbersPicked += 1

Prueba de concepto y prueba de que las probabilidades son correctas :

Simulado con 1 billón de muestras pseudoaleatorias en el transcurso de 5 horas:

>>> Counter(
        tuple(orderedSampleWithoutReplacement([0,1,2,3], 2))
        for _ in range(10**9)
    )
Counter({
    (0, 3): 166680161, 
    (1, 2): 166672608, 
    (0, 2): 166669915, 
    (2, 3): 166667390, 
    (1, 3): 166660630, 
    (0, 1): 166649296
})

Las probabilidades divergen de las verdaderas probabilidades por menos de un factor de 1.0001. La ejecución de esta prueba nuevamente dio como resultado un orden diferente, lo que significa que no está sesgado hacia un solo pedido. Ejecutar la prueba con menos muestras para [0,1,2,3,4], k=3 y [0,1,2,3,4,5], k=4 tuvo resultados similares.

editar: No estoy seguro de por qué las personas están votando comentarios equivocados o temen votar con votos ... NO, no hay nada de malo en este método. =)

(También una nota útil del usuario tegan en los comentarios: si esto es python2, querrás usar xrange, como de costumbre, si realmente te interesa el espacio extra).

edit : Prueba: Considerando la distribución uniforme (sin reemplazo) de escoger un subconjunto de k de una población de tamaño len(seq) , podemos considerar una partición en un punto arbitrario i en ''izquierda'' (0,1 ,. .., i-1) y ''derecha'' (i, i + 1, ..., len (seq)). Dado que seleccionamos los numbersPicked seleccionados del subconjunto conocido izquierdo, el resto debe provenir de la misma distribución uniforme en el subconjunto desconocido correcto, aunque los parámetros ahora son diferentes. En particular, la probabilidad de que seq[i] contenga un elemento elegido es #remainingToChoose/#remainingToChooseFrom , o (k-numbersPicked)/(len(seq)-i) , por lo que simulamos eso y recursemos en el resultado. (Esto debe terminar ya que si #remainingToChoose == #remainingToChooseFrom, todas las probabilidades restantes son 1.) Esto es similar a un árbol de probabilidad que se genera dinámicamente. Básicamente puede simular una distribución de probabilidad uniforme condicionando elecciones previas (a medida que crece el árbol de probabilidad, elige la probabilidad de la rama actual de manera que sea aposteriori igual que las hojas anteriores, es decir, condicionada a elecciones anteriores; esto funcionará porque esta probabilidad es uniformemente exactamente N / k).

editar : Timothy Shields menciona el Muestreo de Yacimientos , que es la generalización de este método cuando len(seq) es desconocido (como con una expresión de generador). Específicamente, el que se señala como "algoritmo R" es O (N) y O (1) espacio si se realiza en el lugar; implica tomar el primer elemento N y reemplazarlo lentamente (también se da una pista de una prueba inductiva). También hay variantes distribuidas útiles y variadas variantes de muestreo de yacimientos que se encuentran en la página de wikipedia.

editar : Aquí hay otra forma de codificarlo a continuación de una manera más semánticamente obvia.

from __future__ import division
import random

def orderedSampleWithoutReplacement(seq, sampleSize):
    totalElems = len(seq)
    if not 0<=sampleSize<=totalElems:
        raise ValueError(''Required that 0 <= sample_size <= population_size'')

    picksRemaining = sampleSize
    for elemsSeen,element in enumerate(seq):
        elemsRemaining = totalElems - elemsSeen
        prob = picksRemaining/elemsRemaining
        if random.random() < prob:
            yield element
            picksRemaining -= 1

from collections import Counter         
Counter(
    tuple(orderedSampleWithoutReplacement([0,1,2,3], 2))
    for _ in range(10**5)

)

Answer 2

Aparentemente random.sample se introdujo en python 2.3

entonces para la versión debajo de eso, podemos usar el orden aleatorio (ejemplo para 4 elementos):

myRange =  range(0,len(mylist)) 
shuffle(myRange)
coupons = [ bestCoupons[i] for i in sorted(myRange[:4]) ]

Answer 3

El siguiente código generará una muestra aleatoria de tamaño 4.

rand_smpl = [ mylist[i] for i in sorted(random.sample(xrange(len(mylist)), 4)) ]

Explicación:

random.sample(xrange(len(mylist)), sample_size)

genera una muestra aleatoria de los índices de la lista original.

Esta muestra luego se ordena para preservar el orden de los elementos en la lista original.

Finalmente, la lista de comprensión extrae los elementos de la lista original, dados los índices muestreados, y construye la muestra final (de los elementos reales).

Answer 4

Tal vez solo pueda generar la muestra de índices y luego recopilar los elementos de su lista.

randIndex = random.sample(range(len(mylist)), sample_size)
randIndex.sort()
rand = [mylist[i] for i in randIndex]

Answer 5

random.sample implementarlo.

>>> random.sample([1, 2, 3, 4, 5],  3)   # Three samples without replacement
[4, 1, 5]