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
Tags für diesen Artikel: ,

Trackbacks


Keine Trackbacks

Kommentare

Ansicht der Kommentare: (Linear | Verschachtelt)

Noch keine Kommentare

Kommentar schreiben


Die angegebene E-Mail-Adresse wird nicht dargestellt, sondern nur für eventuelle Benachrichtigungen verwendet.

Um maschinelle und automatische Übertragung von Spamkommentaren zu verhindern, bitte die Zeichenfolge im dargestellten Bild in der Eingabemaske eintragen. Nur wenn die Zeichenfolge richtig eingegeben wurde, kann der Kommentar angenommen werden. Bitte beachten Sie, dass Ihr Browser Cookies unterstützen muss, um dieses Verfahren anzuwenden.
CAPTCHA

Pavatar, Gravatar, MyBlogLog, Monster ID, Pavatar Autoren-Bilder werden unterstützt.
HTML-Tags werden in ihre Entities umgewandelt.
BBCode-Formatierung erlaubt