Ottenere un campione casuale di elenco, pur mantenendo l’ordinamento degli elementi?

Ho un elenco ordinato, diciamo: (non è davvero solo dei numeri, è un elenco di oggetti che vengono ordinati con un complesso che richiede tempo algoritmo)

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

C’è qualche funzione python che mi darà a N di elementi, ma di mantenere l’ordine?

Esempio:

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

ecc…

  • Perché non si desidera random.sample e quindi ordinare?
  • E ‘ ordinato, con una non banale algoritmo… non è proprio solo dei numeri
  • Un leggero cambiamento di Daniel commento: esempio di una gamma di [0,count), ordinare l’esempio (i numeri nell’intervallo hanno un ordinamento naturale), quindi estrarre i valori da mylist basato sugli indici. Utilizzando zip potrebbe ottenere lo stesso effetto con un po ‘ di meccaniche differenti.
  • ok, posso avere una risposta + esempio così ho qualcosa da accettare ? 🙂

 

5 Replies
  1. 118

    Codice seguente genera un campione casuale di dimensione 4:

    import random
    
    sample_size = 4
    sorted_sample = [
        mylist[i] for i in sorted(random.sample(range(len(mylist)), sample_size))
    ]

    (nota: con Python 2, è meglio usare xrange invece di range)

    Spiegazione

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

    genera un campione casuale di indici della lista originale.

    Tali indici, quindi ordinati per conservare l’ordine degli elementi della lista originale.

    Infine, la lista di comprensione tira fuori i reali elementi dalla lista originale, dato che il campionato indici.

  2. 88

    Semplice-per-il codice O(N + K*log(K)) modo

    Prendere un campione casuale, senza sostituzione, di indici, di ordinamento degli indici, e portarli dall’originale.

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

    O più brevemente:

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

    Ottimizzato O(N) in tempo O(1)-ausiliari-space modo

    In alternativa, è possibile utilizzare la matematica trucco e iterativamente passare attraverso myList da sinistra a destra, la raccolta di numeri con dinamicamente cambiare probabilità (N-numbersPicked)/(total-numbersVisited). Il vantaggio di questo approccio è che è un O(N) algoritmo in quanto non coinvolgono l’ordinamento!

    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

    Prova di concetto e di prova che le probabilità sono corrette:

    Di simulazione di 1 trilione di pseudocasuali campioni nel corso di 5 ore:

    >>> 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
    })

    Probabilità discosta dal vero probabilità da meno di un fattore di 1.0001. L’esecuzione di questo test di nuovo portato in un ordine diverso significato non è sbilanciata verso un ordine. Esecuzione del test con un minor numero di campioni per [0,1,2,3,4], k=3 e [0,1,2,3,4,5], k=4 avuto risultati simili.

    edit: Non so perché la gente vota torto commenti o ha paura di dare un voto positivo… NO, non c’è niente di sbagliato con questo metodo. =)

    (Anche una utile nota dall’utente tegan nei commenti: Se questo è python2, si desidera utilizzare xrange, come al solito, se vi interessa davvero spazio extra.)

    modifica: Prova: Considerando la distribuzione uniforme (senza sostituzione) di scegliere un sottoinsieme di k su una popolazione seq di dimensioni len(seq), si può considerare una partizione in un punto arbitrario i in ‘sinistra’ (0,1,…,i-1) e ‘di destra’ (i,i+1,…,len(seq)). Dato che abbiamo scelto numbersPicked da sinistra noto sottoinsieme, i restanti devono provenire dalla stessa distribuzione uniforme sulla destra unknown sottoinsieme, se i parametri sono diversi. In particolare, la probabilità che seq[i] contiene un elemento scelto è #remainingToChoose/#remainingToChooseFrom, o (k-numbersPicked)/(len(seq)-i), così simuliamo che e recurse sul risultato. (Questo deve terminare in quanto se #remainingToChoose == #remainingToChooseFrom, tutte le altre le probabilità sono 1.) Questo è simile a una probabilità albero che sembra essere generato dinamicamente. Fondamentalmente si può simulare una uniforme distribuzione di probabilità condizionata da precedenti scelte (come si cresce la probabilità albero, si prende la probabilità che l’attuale ramo tali che è aposteriori lo stesso come prima le foglie, cioè condizionata, sulle scelte fatte in precedenza; in questo lavoro, perché questa probabilità è uniformemente esattamente N/k).

    modifica: Timothy Scudi cita Serbatoio Di Campionamento, che è la generalizzazione di questo metodo quando len(seq) è sconosciuto (ad esempio con un generatore di espressione). In particolare quello indicato come “algoritmo R” è O(N) e O(1) se sul posto; si tratta di prendere i primi N elementi e, lentamente, la loro sostituzione (un accenno a un sensore induttivo prova è data anche). Ci sono anche degli utili distribuiti varianti e varie varianti di serbatoio di campionamento per essere trovati sulla pagina di wikipedia.

    modifica: Ecco un altro modo per il codice riportato di seguito in un più semanticamente modo evidente.

    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)

    )

    • nessun svantaggio, solo un aumento di velocità di O(N) piuttosto O(N log(N))
    • La tua ultima affermazione è errata, in quanto la probabilità va a 1 naturalmente se i campioni non vengono ritirati. Si prega di essere così gentile da eseguire il backup la tua prima affermazione con la matematica, sarei molto interessato se si può dimostrare che ho sbagliato nonostante la mia vasta simulazioni.
    • Molto bello, mi chiedevo come fare questo approccio lineare troppo. Non questa formula ha una pagina di wikipedia? 🙂
    • grazie! Mi chiedevo anche io, ma non riuscivo a trovare, non so dove aggiungere anche, forse en.wikipedia.org/wiki/Uniform_distribution_%28discrete%29 … potrebbe essere in probabilità libri di testo, però; è la generalizzazione del [1/N,1/N-1,1/N-2,...,1] metodo di campionamento uniforme distribuzione discreta di valori multipli (senza sostituzione).
    • Mi sorprende che questa risposta non avere più upvotes, è in realtà spiega come funziona questa soluzione (e fornisce un’altra soluzione!!!), contrariamente alla prima risposta che è solo una linea frammento– mi dà alcuna idea del perché o come ha funzionato.
    • Bella soluzione ninjagecko. C’è una bella induttivo prova la tua soluzione, se qualcuno è interessato a scrivere su.
    • Bella soluzione ! Non dimenticate di aggiungere from __future__ import division per coloro che eseguono Python 2.
    • Si deve il nome dell’algoritmo la tua risposta: Serbatoio di Campionamento
    • In questa situazione, si probabilmente desidera utilizzare xrange() non range(), soprattutto se la tua lista è lunga, range() mette tutti gli elementi di memoria, mentre xrange() valuta pigramente (in modo da non perdere tempo e memoria per la creazione di un elenco non c’è bisogno). Vedere here per ulteriori dettagli
    • tegan: Ah sì, scusa, ho usato per la codifica in python3. Non è il tag OP postato su (solo python2), ma per quello che vale, range() è un pigro oggetto in python3. A cura.
    • Per coloro che eseguono Python 2.x: prob = (k-numbersPicked)/float(len(seq)-i)
    • Ho provato questo algoritmo e defenitly non può funzionare bene per qualsiasi sequenza. Qui è un semplice contatore-esempio: ideone.com/FNYfj8
    • provato questo algoritmo e defenitly non può funzionare bene per qualsiasi sequenza. Qui è un semplice contro-esempio.”) Un algoritmo funziona se si dispone di una valida prova matematica come questo, nel caso di test è anche abbastanza buona la prova che funziona. Non conosco C#, ma ho notato che il vostro i variabile non è nemmeno di essere incrementato. Ci possono essere altri errori del vostro trascrizione.
    • Ho riletto la tua risposta e qui è stato risolto attuazione. Sono d’accordo che sembra che garantisce per tornare esattamente N record. Mi dispiace per la lettura inattentively la prima volta.

  3. 7

    Forse si può solo generare il campione di indici e poi raccogliere gli elementi dalla vostra lista.

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

    Apparentemente random.sample è stato introdotto in python 2.3

    così per la versione sotto, siamo in grado di utilizzare shuffle (ad esempio, per 4 voci):

    myRange =  range(0,len(mylist)) 
    shuffle(myRange)
    coupons = [ bestCoupons[i] for i in sorted(myRange[:4]) ]
    • Stai usando Python 2.2?! Si dovrebbe aggiornare… che è fuori di data.
    • bene, è quello che abbiamo sul server.. facendo un ampio sistema di aggiornamento è troppa Burocrazia
  5. -1

    casuale.esempio di implementazione.

    >>> random.sample([1, 2, 3, 4, 5],  3)   # Three samples without replacement
    [4, 1, 5]
    • Che non è ordinato.

Lascia un commento