wake-up-neo.net

Stichprobe von der Liste erhalten und dabei die Reihenfolge der Artikel beibehalten?

Ich habe eine sortierte Liste, sagen wir mal: (es sind nicht wirklich nur Zahlen, es ist eine Liste von Objekten, die mit einem komplizierten zeitaufwendigen 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 einhält?

Beispiel:

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

usw...

74
Yochai Timmer

Folgender 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: Verwenden Sie bei Python 2 besser xrange anstelle von range).

Erklärung

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

erzeugt eine Zufallsstichprobe der indices der ursprünglichen Liste.

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

Das Listenverständnis zieht schließlich die tatsächlichen Elemente aus der ursprünglichen Liste heraus, wenn man die abgetasteten Indizes berücksichtigt.

114
mhyfritz

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

Nehmen Sie eine Stichprobe ohne Ersetzung der Indizes, sortieren Sie die Indizes und nehmen Sie sie vom 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) -Hilfsweg

Sie können alternativ einen mathematischen Trick verwenden und myList von links nach rechts iterativ durchgehen und Zahlen mit dynamisch wechselnder Wahrscheinlichkeit (N-numbersPicked)/(total-numbersVisited) auswählen. 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

Konzeptnachweis und Test, dass die Wahrscheinlichkeiten korrekt sind:

Simuliert mit 1 Billion pseudozufälliger Proben innerhalb 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 wahren Wahrscheinlichkeiten ab. Das erneute Ausführen dieses Tests führte zu einer anderen Reihenfolge, was bedeutet, dass es nicht auf eine Reihenfolge ausgerichtet ist. Das Ausführen des Tests mit weniger Proben für [0,1,2,3,4], k=3 und [0,1,2,3,4,5], k=4 hatte ähnliche Ergebnisse.

edit: Nicht sicher, warum die Leute falsche Kommentare wählen oder Angst haben, sie zu verteidigen ... NEIN, mit dieser Methode stimmt nichts. =)

(In den Kommentaren auch ein nützlicher Hinweis von Benutzer tegan: Wenn dies Python2 ist, sollten Sie wie üblich xrange verwenden, wenn Sie wirklich mehr Platz benötigen.)

edit: Beweis: In Anbetracht der einheitlichen Verteilung (ohne Ersatz) der Auswahl einer Untermenge von k aus einer Population seq mit der Größe len(seq) können wir eine Partition an einem beliebigen Punkt i in 'left' (0, 1, ..., i-1) und "rechts" (i, i + 1, ..., len (seq)). Da wir numbersPicked aus der linken bekannten Teilmenge ausgewählt haben, müssen die verbleibenden Teile von derselben gleichförmigen Verteilung auf der rechten unbekannten Teilmenge stammen, obwohl die Parameter jetzt unterschiedlich sind. Insbesondere ist die Wahrscheinlichkeit, dass seq[i] ein ausgewähltes Element enthält, #remainingToChoose/#remainingToChooseFrom oder (k-numbersPicked)/(len(seq)-i), also simulieren wir das und wiederholen das Ergebnis. (Dies muss enden, da bei #remainingToChoose == #remainingToChooseFrom alle verbleibenden Wahrscheinlichkeiten 1 sind.) Dies ähnelt einem Wahrscheinlichkeitsbaum, der dynamisch generiert wird. Grundsätzlich können Sie eine einheitliche Wahrscheinlichkeitsverteilung simulieren, indem Sie frühere Auswahlen konditionieren (wenn Sie den Wahrscheinlichkeitsbaum vergrößern, wählen Sie die Wahrscheinlichkeit des aktuellen Zweigs so, dass er aposteriori wie vorherige Blätter ist, dh bedingt durch frühere Entscheidungen; dies wird funktionieren diese Wahrscheinlichkeit ist einheitlich genau N/k).

edit: Timothy Shields erwähnt Reservoir Sampling . Dies ist die Verallgemeinerung dieser Methode, wenn 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 erfolgt; es geht darum, das erste N-Element zu nehmen und langsam zu ersetzen (ein Hinweis auf einen induktiven Beweis wird ebenfalls gegeben). Es gibt auch nützliche verteilte Varianten und verschiedene Varianten der Reservoir-Probenahme auf der Wikipedia-Seite.

edit: Hier ist eine andere Möglichkeit, es unten semantisch 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)

)

86
ninjagecko

Vielleicht können Sie einfach eine 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]
7
Howard

Anscheinend wurde random.sample in Python 2.3 eingeführt

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

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

random.sample implementiere es.

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