Zufällige Stichprobe aus der Liste erhalten, während die Reihenfolge der Artikel beibehalten wird?

84

Ich habe eine sortierte Liste, sagen wir: (Es sind nicht nur Zahlen, sondern eine Liste von Objekten, die mit einem komplizierten zeitaufwändigen Algorithmus sortiert werden.)

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

Gibt es eine Python-Funktion, die mir N der Elemente gibt, aber die Reihenfolge beibehält?

Beispiel:

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

etc...

Yochai Timmer
quelle
1
Warum willst du nicht random.sampleund dann sortieren?
Daniel Lubarov
Es ist mit einem nicht trivialen Algorithmus sortiert ... es sind nicht wirklich nur Zahlen
Yochai Timmer
4
Eine sehr geringfügige Änderung von Daniels Kommentar: Probieren Sie einen Bereich aus [0,count), sortieren Sie die Stichprobe (die Zahlen im Bereich haben eine natürliche Reihenfolge) und extrahieren Sie dann die Werte mylistbasierend auf den Indizes. Die Verwendung zipkönnte den gleichen Effekt mit leicht unterschiedlichen Mechaniken erzielen.
1
ok, kann ich eine Antwort + ein Beispiel bekommen, damit ich etwas zu akzeptieren habe? :)
Yochai Timmer

Antworten:

120

Der folgende Code generiert eine Zufallsstichprobe der Größe 4:

import random

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

(Hinweis: Mit Python 2 besser verwenden xrangeals range)

Erläuterung

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

generiert eine zufällige Stichprobe der Indizes der ursprünglichen Liste.

Diese Indizes werden dann sortiert, um die Reihenfolge der Elemente in der ursprünglichen Liste beizubehalten.

Schließlich zieht das Listenverständnis die tatsächlichen Elemente aus der ursprünglichen Liste heraus, wenn die Stichprobenindizes gegeben sind.

mhyfritz
quelle
89

Einfach zu codierender O (N + K * log (K)) Weg

Nehmen Sie eine Zufallsstichprobe ohne Ersatz der Indizes, sortieren Sie die Indizes und entnehmen Sie sie dem Original.

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

Oder genauer:

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

Optimierte O (N) -Zeit, O (1) -Intiliilraum-Weg

Sie können alternativ einen mathematischen Trick und iterativ durchläuft myListvon links nach rechts, Kommissionierung Zahlen mit dynamisch wechselnden Wahrscheinlichkeit (N-numbersPicked)/(total-numbersVisited). Der Vorteil dieses Ansatzes ist, dass es sich um einen O(N)Algorithmus handelt, da keine Sortierung erforderlich ist!

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

Proof of Concept und Test der Richtigkeit der Wahrscheinlichkeiten :

Simuliert mit 1 Billion Pseudozufallsstichproben über einen Zeitraum von 5 Stunden:

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

Die Wahrscheinlichkeiten weichen um einen Faktor von 1.0001 von den tatsächlichen Wahrscheinlichkeiten ab. Das erneute Ausführen dieses Tests führte zu einer anderen Reihenfolge, was bedeutet, dass er nicht auf eine Bestellung ausgerichtet ist. Durchführen des Tests mit weniger Proben für [0,1,2,3,4], k=3und [0,1,2,3,4,5], k=4ähnliche Ergebnisse.

edit: Ich bin mir nicht sicher, warum Leute falsche Kommentare abgeben oder Angst haben, zu stimmen ... NEIN, an dieser Methode ist nichts auszusetzen. =)

(Auch ein nützlicher Hinweis von Benutzer tegan in den Kommentaren: Wenn dies python2 ist, sollten Sie xrange wie gewohnt verwenden, wenn Sie sich wirklich für zusätzlichen Speicherplatz interessieren.)

edit : Beweis: In Anbetracht der gleichmäßigen Verteilung (ohne Ersatz) der Auswahl einer Teilmenge kaus einer Population seqvon Größe len(seq)können wir eine Partition an einem beliebigen Punkt iin 'links' (0,1, ..., i-1) betrachten. und 'richtig' (i, i + 1, ..., len (seq)). Da wir numbersPickedaus der linken bekannten Teilmenge ausgewählt haben, müssen die verbleibenden aus derselben gleichmäßigen Verteilung in der rechten unbekannten Teilmenge stammen, obwohl die Parameter jetzt unterschiedlich sind. Insbesondere ist die Wahrscheinlichkeit, seq[i]die ein ausgewähltes Element enthält,#remainingToChoose/#remainingToChooseFrom , oder(k-numbersPicked)/(len(seq)-i)Also simulieren wir das und greifen auf das Ergebnis zurück. (Dies muss beendet werden, da bei #remainingToChoose == #remainingToChooseFrom alle verbleibenden Wahrscheinlichkeiten 1 sind.) Dies ähnelt einem Wahrscheinlichkeitsbaum, der zufällig dynamisch generiert wird. Grundsätzlich können Sie eine gleichmäßige Wahrscheinlichkeitsverteilung simulieren, indem Sie auf vorherige Entscheidungen konditionieren (wenn Sie den Wahrscheinlichkeitsbaum vergrößern, wählen Sie die Wahrscheinlichkeit des aktuellen Zweigs so aus, dass sie aposteriori mit früheren Blättern identisch ist, dh von vorherigen Entscheidungen abhängig ist; dies funktioniert, weil diese Wahrscheinlichkeit ist einheitlich genau N / k).

edit : Timothy Shields erwähnt Reservoir Sampling , die Verallgemeinerung dieser Methode, wenn sie len(seq)unbekannt ist (z. B. mit einem Generatorausdruck). Insbesondere ist der als "Algorithmus R" bezeichnete O (N) - und O (1) -Raum, wenn er an Ort und Stelle durchgeführt wird; Dabei wird das erste N-Element genommen und langsam ersetzt (ein Hinweis auf einen induktiven Beweis wird ebenfalls gegeben). Auf der Wikipedia-Seite finden Sie auch nützliche verteilte Varianten und verschiedene Varianten der Reservoir-Probenahme.

Bearbeiten : Hier ist eine andere Möglichkeit, es unten semantisch offensichtlicher zu codieren.

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)

)

Ninjagecko
quelle
1
@pst: kein Nachteil, nur eine Beschleunigung von O(N)eherO(N log(N))
Ninjagecko
1
Sehr schön, ich habe mich gefragt, wie ich diesen linearen Ansatz auch machen soll. Hat diese Formel eine Wikipedia-Seite? :)
Jochen Ritzel
2
Ich bin überrascht, dass diese Antwort nicht mehr positive Stimmen hat. Sie erklärt tatsächlich, wie die Lösung funktioniert (und bietet eine andere Lösung!), Im Gegensatz zu der ersten Antwort, die nur ein einzeiliger Ausschnitt ist - und gibt mir keine Ahnung, warum oder wie es funktioniert hat.
crazy2be
1
Schöne Lösung Ninjagecko. Es gibt einen schönen induktiven Beweis für Ihre Lösung, wenn jemand daran interessiert ist, sie aufzuschreiben.
Neil G
3
Schöne Lösung! Vergessen Sie nicht, from __future__ import divisionfür diejenigen hinzuzufügen , die Python 2
ausführen
7

Vielleicht können Sie einfach die Stichprobe von Indizes generieren und dann die Elemente aus Ihrer Liste sammeln.

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

Anscheinend random.samplewurde in Python 2.3 eingeführt

Für die Version darunter können wir also Shuffle verwenden (Beispiel für 4 Elemente):

myRange =  range(0,len(mylist)) 
shuffle(myRange)
coupons = [ bestCoupons[i] for i in sorted(myRange[:4]) ]
Yochai Timmer
quelle
4
Sie verwenden Python 2.2?! Sie sollten ein Upgrade durchführen ... das ist veraltet.
Katriel
1
Nun, es ist das, was wir auf den Servern haben. Ein systemweites Update durchzuführen ist zu viel Bürokratie
Yochai Timmer
-2

random.sample implementieren es.

>>> random.sample([1, 2, 3, 4, 5],  3)   # Three samples without replacement
[4, 1, 5]
Xiao
quelle
9
Das ist nicht bestellt.
Astrid