17. 10
...als apic noch zap-zero hieß, dass er mit folgender Frage in !eof aufschlug:<zap-zero> rand($.) < 1 && ($line = $_) while <>; <zap-zero> das ist perl, um eine zufaellig zeile des inputs zu selektieren <zap-zero> wie zum frell kann das gehen? <zap-zero> ohne zu wissen, wie viele zeilen der input hat? <zap-zero> kann das dann ganz evenly distributed sein yberhaupt?Ja, ist es:
<brennbock> du meinst gleichverteilt?
<brennbock> du anglizismen-neusprech-gott?
<zap-zero> gaynau
<urs> zap-zero: das ist bestimmt nicht gleichverteilt
<zap-zero> urs: ok
<urs> Aber du könntest natürlich eine Messreihe durchführen. :)
<zap-zero> hatte ich vorhin mit 'seq 50000', war arschlahm :)
<zap-zero> perl--
<zap-zero> der compiled den schrott ja jedesmal neu
<zap-zero> sollte ich lieber in c re-implementen :)
<zap-zero> hab aber grad keinen boq
<urs> ah, moment *überleg*
<zap-zero> ich hab die reihe auch nicht ausgewertet
<urs> $. ist die aktuelle Zeilennummer, oder?
<zap-zero> ack
<urs> Hm, doch... dann ist es tatsächlich gleichverteilt.
<urs> Krass. :)
<urs> Beweis durch Induktion:
<das_petschge> zeigen
<urs> Induktionsanfang: Bei einer Datei mit nur einer Zeile wird diese
mit Wahrscheinlichkeit 1 gewählt, die wahrscheinlichkeit ist also
gleichverteilt.
<zap-zero> uhm
<zap-zero> und woher weiss das script, dass nach der einen zeile nicht
schluss ist?
<urs> Induktionsschritt: der algorithmus sei bereits über n zeilen
gelaufen, und $line halte mit gleichverteilter wahrscheinlichkeit eine
dieser Zeilen. Dann muss $line mit der Wahrscheinlichkeit 1/(n+1) die
n+1te zeile erhalten, mit 1 - 1(n+1) die bisherige behalten.
<urs> Und somit die wahrscheinlichkeit dafür, dass eine Zeile als $line
ausgewählt wird, auch für n+1 Zeilen gleichverteilt.
<das_petschge> oh, cool
<urs> und rand($.) < 1 ist genau mit wahrscheinlichkeit 1 / ($.) wahr.
<zap-zero> ich raffs trotzdem noch nicht
<zap-zero> woher weiss er denn dass nach zeile 1 nicht schon schluss ist?
<das_petschge> gar ned
<zap-zero> ja, aehm...
<zap-zero> wie kann er dann bei 1zeiligen teilen zeile 1 mit 100%
wahrscheinlichkeit selecten?
<das_petschge> aber wenn zeile zwei auftaucht, dann ersetzt er dit WS 1/2
die Auswahl der Zeile 1 mit Zeile 2
<zap-zero> ah, ok
<das_petschge> k
<zap-zero> er ist also immer nen schritt voraus irgendwie
<das_petschge> nicht wirklichj
<das_petschge> wenn die erste zeile kommt, dann wählt er die aus
<zap-zero> ack
<zap-zero> jo, langsam daemmerts :)
<zap-zero> coole methode jedenfalls
<das_petschge> wenn die zweite zeile kommt ersetzt er die auswahl mit
WS 1/2 druch die zeite
<urs> und die 2. nimmt er dann mit wahrscheinlichkeit 50%
<zap-zero> ich hab sowas frueher immer mit $grossem_scheissendrecks_array
geloest ;)
<das_petschge> bei der n. Zeile macht er das mit WS 1/n
<zap-zero> ok
<zap-zero> danke
<das_petschge> und wenn keine Zeile mehr kommt nimmt er die, die bis dahin
ausgewählt ist
<das_petschge> ja ist echt elegant
<zap-zero> ack
<das_petschge> danke auch an urs für die mathematische Analyse
Trackbacks