Nagy számok közelről · 3 perc olvasás
Egymilliárd rekordból hogyan válassz ezret anélkül, hogy mindet eltárolnád?
Folyamatosan érkeznek a rekordok, a teljes hossz előre ismeretlen, és csak ezer darab fér a mintatárba. Mégis elérhető, hogy a végén minden rekord azonos eséllyel szerepeljen a mintában. A megoldás az érkezési sorszámhoz igazítja a csere valószínűségét.
Ebben a cikkben
Először csak egy rekordot tartunk meg
Az első rekordot eltesszük. A második érkezésekor fele eséllyel lecseréljük rá a tároltat. A harmadiknál 1/3, a negyediknél 1/4, általában a j-ediknél 1/j valószínűséggel cserélünk. Ha nem cserélünk, a korábbi rekord marad. A választásokhoz minden alkalommal a megfelelő, független véletlen döntést feltételezzük.
A csere valószínűsége azért csökken, mert a később érkező rekordnak kevesebb későbbi cserét kell túlélnie. Ha mindig fele eséllyel cserélnénk, az utolsó rekord esélye mindig 1/2 maradna, az elsőké pedig sokszor feleződne. Az ilyen módszer a sor végét részesítené előnyben.
Az ötödik rekord után mind az öt esélye egyötöd
Nézzük a harmadik rekordot egy ötelemű adatfolyamban. Be kell kerülnie a harmadik lépésben, ennek esélye 1/3. Túl kell élnie a negyedik cseréjét, ennek esélye 3/4, majd az ötödikét, ennek esélye 4/5. A szorzat 1/3 × 3/4 × 4/5 = 1/5.
Az első rekord induláskor biztosan bent van, túlélési esélye pedig 1/2 × 2/3 × 3/4 × 4/5 = 1/5. Általában a j-edik rekord 1/j bekerülési esélyét a j/(j+1), (j+1)/(j+2), …, (n−1)/n túlélési tényezőkkel szorozzuk. A közbülső tényezők kiesnek, és 1/n marad. A végső n ismeretére az algoritmus közben nem volt szükség.
Az ezerrekordos változat csereszabálya
Ezer mintához az első ezer rekordot eltesszük. A j-edik további rekordnál egyenletes véletlen egész számot választunk 1 és j között. Ha a szám legfeljebb ezer, a megfelelő mintatári helyet felülírjuk az új rekorddal; ha nagyobb, a mintát változatlanul hagyjuk. Az új rekord bekerülésének esélye így 1000/j.
A NIST algoritmusleírása ezt rezervoár-mintavételnek nevezi. A Cornell jegyzete a helyességét is levezeti: a végén minden ezerelemű részhalmaz azonos valószínűségű, visszatevés nélküli mintát kapunk. Az egyes rekordok bekerülése egymással összefügg, hiszen a minta teljes mérete rögzített. Azonos értékű, de külön érkezett rekordok ebben a modellben külön megfigyelések.
A memóriaigény kicsi marad, a beolvasás megmarad
Ha egy rekord 128 bájtos, ezer megtartott rekord nyers adattartalma 128 000 bájt. Egymilliárd ilyen rekord teljes nyers tartalma 128 milliárd bájt lenne. A mintában tárolt adatok mérete egymilliomod része a teljesnek; a tényleges program ezen felül számlálót, véletlengenerátort és saját adatstruktúrákat is használ.
Az egyszerű algoritmus ettől még végighalad mind az egymilliárd rekordon. A memória-megtakarítás nem jelenti a beolvasási munka eltűnését. A feldolgozott darabszámot pontosan nyilván kell tartani, mert az a csere esélyét határozza meg. Egy újraindításnál elvesztett számláló vagy indokolatlanul visszaállított véletlengenerátor elronthatja a kívánt eloszlást.
Az egyenletes minta sem talál meg minden ritkaságot
Egymilliárd rekord és ezer megtartott elem mellett egy adott rekord bekerülésének esélye 1000/1 000 000 000 = 1/1 000 000, vagyis 0,0001%. Ha pontosan egy különleges rekord van az egész adatfolyamban, ugyanekkora eséllyel találjuk meg ezzel a mintával. A ritka hibák biztos felderítését egy kis, korrekt véletlen minta sem ígéri.
Az algoritmus a kiválasztást oldja meg; a minta méretét és a keresett jelenség gyakoriságát külön kell megtervezni. Ha kategóriánként biztosan szeretnél elemeket látni, más mintavételi tervre lehet szükség. A rezervoár akkor hasznos, amikor a teljes adatfolyamból egyenletes mintát szeretnél, és a tárolási lehetőség jóval kisebb a beérkező adatmennyiségnél.
A példák és a források
A számpéldák saját, szemléltető feladatok; a megadott feltételezésekből és képletekből újraszámolhatók. Valós vállalkozásra, országos statisztikára vagy jövőbeli eredményre nem vonatkoznak.
- NIST Dictionary of Algorithms and Data Structures: reservoir sampling ↗
- Cornell ORIE 6125: rezervoár-mintavétel és helyességi bizonyítás ↗
Forrásellenőrzés: 2026-11-09. A hivatkozások a fogalmakat és a módszert támasztják alá; a példaszámítások a cikk részei.
Négy kérdés a cikkhez
A válaszokból kiderül, melyik összefüggést érted már, és melyik részt érdemes újraolvasnod. A válaszokat és a pontszámot nem mentjük.
