shuffle in Schleife laufen lassen (solved) (Allgemeines zu Perl)

[thread]19436[/thread]

shuffle in Schleife laufen lassen [solved]

Tags: perl5 Similar Threads

Readers: 16

Articles: hide open all | hide show old branches

+16 replies
qwe123qwe

2014-12-27 17:42

User since
2013-10-08
65 articles
BenutzerIn

Hi all,
die Frage hat eher was mit der "Erzeugung des Zufalls" bzw. Mathematik zu tun, aber eventuell hat ja schon jemand sowas mit Perl gelöst.

In einer langsam aber sicher anwachsenden Datei habe ich inzwischen einige 10.000 Zeileneinträge stehen, die ich testweise möglichst gut durchmischt in eine neu anzulegende Datei schreiben will.

Bisher habe ich dazu ein bash-Skript mit dem "shuf" Befehl benutzt. Einigermaßen akzeptabel ist die Durchmischung hier aber erst durch das mehrmalige Aufrufen von "shuf" in einer Schleife geworden. Der "Zufall" bei der Sortierreihenfolge wird aber mit zunehmender Länge der Datei immer schlechter - zumindest habe ich subjektiv diesen Eindruck.

Jetzt wollte ich das mit dem "shuffle" Aufruf aus dem Modul List::Utils versuchen.
Kann ich davon ausgehen, daß die Durchmischung wirklich besser ist ? Bringt das was, wenn ich den Aufruf wie bei dem Bash-Skript in eine Schleife packe oder ist das hier vom mathematischen Standpunkt egal ?

Hinbekommen werde ich ein Perl-Skript ganz sicher, vielleicht gibt's aber einen Trick, mit dem man die Durchmischung optimieren kann.
- +12 replies
- hlubenow
  
  2014-12-27 18:28
  
  User since
  2009-02-22
  877 articles
  BenutzerIn
  
  Vorweg: Leider bin ich mir auch immer unsicher, wie genau Computer Zufallszahlen erzeugen.
  Statt List::Util::shuffle() könntest Du auch eine Zufallszahl erzeugen und dann die Sache mit der Liste von Hand machen. Hier ist eine ganz gute Anleitung:
  
  http://perl-howto.de/2008/06/zufallszahlen-pseudo-...
  
  Der Zufallszahlengenerator hat irgendwas mit einem "seed" zu tun. Mit srand() kann man auf den einwirken. Auf der Seite heißt es aber:
  
  Quote
  Rufen Sie niemals srand() auf, wenn Sie nicht genau wissen, was Sie tun. Perl ruft srand() automatisch für Sie mit einem geeignetem Seed auf, sobald rand() verwendet wird.
  
  Das heißt: Normalerweise braucht man sich um diese Details nicht zu kümmern. Ansonsten gibt es für stärkeren Zufall noch das interessante Modul Math::Random::Secure.
  - +9 replies
  - qwe123qwe
    
    2014-12-27 20:09
    
    User since
    2013-10-08
    65 articles
    BenutzerIn
    
    Danke für den Link !
    Wenn ich diesen Artikel und den hier samt weiteren Verweis richtig verstanden habe, benutzt shuffle denselben Algorithmus "Ziehen ohne Zurücklegen").
    
    Beim shuf-Befehl der Bash ist das aber nach diesem Beispiel nicht anders. Trotzdem ist das Ergebnis nicht sehr gut bis grottenschlecht.
    
    Das Modul klingt interessant.
    Mein Bash-Skript benutzt aber ebenfalls /dev/urandom als Zufallsquelle....
    
    Ich versteh eben nicht, wo da das eigentliche Problem bei "shuf" liegt und ob Perls "shuffle" das tatsächlich besser macht......
    - +8 replies
    - Muffi
      
      2015-01-02 20:07
      
      User since
      2012-07-18
      1465 articles
      BenutzerIn
      
      Und du glaubst du hast jetzt einen gravierenden bug darin gefunden, der bis jetzt noch niemandem auffiel?
      1 + 1 = 10
      - +7 replies
      - qwe123qwe
        
        2015-01-03 10:33
        
        User since
        2013-10-08
        65 articles
        BenutzerIn
        
        wieso Bug ?
        Ich glaube, daß ich bisher keine befriedigende Lösung für die Aufgabe gefunden habe -- sonst nix.
        Falls Du ähnliche gelöste Beispiele kennst wäre es toll, wenn Du mir da einen Link geben könntest.
        
        Falls es feststeht, daß der Umstieg auf Perl hier nix bringt, würde ich das auch gern wissen. Dann kann ich mir das sparen.
        Last edited: 2015-01-03 10:57:19 +0100 (CET)
        
        +6 replies
        
        Muffi
        
        2015-01-03 14:43
        
        User since
        2012-07-18
        1465 articles
        BenutzerIn
        
        Also wenn eine Funktion ein Array/Liste shuffeln soll und das aber nicht tut dann ist da ein Bug drin.
        1 + 1 = 10
        
        +5 replies
        
        qwe123qwe
        
        2015-01-03 16:09
        
        User since
        2013-10-08
        65 articles
        BenutzerIn
        
        die Funktion "shuffelt" ja, ebenso der Befehl in der Bash.
        
        Es steht ja nirgends geschrieben, ob das Resultat dann mathematisch exakt einer Zufallsverteilung entspricht. Gerade das wollte ich hier im Forum erfahren.
        Außerdem kann es gut sein, daß das verwendete Verfahren an sich perfekt ist, die Umsetzung auf dem jeweiligen Rechner aber weshalb auch immer dann nicht. Ich kann mir schon vorstellen, daß mein 1GB-RAM Rechner da schlechtere Durchmischungen liefert als eine 64GB Rennmaschine.
        
        +4 replies
        
        Muffi
        
        2015-01-03 16:15
        
        User since
        2012-07-18
        1465 articles
        BenutzerIn
        
        Der Algorithmus liefert ein perfekt durchmischtes array und der rand() im Rechner liefert genügend gute Zufallswerte.
        Also entweder ist ein Bug drin oder du siehst da was was nicht ist.
        1 + 1 = 10
        
        qwe123qwe
        
        2015-01-03 16:23
        
        User since
        2013-10-08
        65 articles
        BenutzerIn
        
        wie gesagt, das ist gut möglich und das will/muß ich testen.
        
        Aber ich kann dann doch vorher nachfragen, ob jemand schon auf was Ähnliches gestoßen ist bzw. solche Test durchgeführt hat.
        Also schau ma mal, was bei den Tests rauskommt.
        
        Wird aber wie schon geschrieben aber etwas dauern.
        Last edited: 2015-01-03 16:25:02 +0100 (CET)
        
        +2 replies
        
        qwe123qwe
        
        2015-01-03 17:05
        
        User since
        2013-10-08
        65 articles
        BenutzerIn
        
        noch ein paar Erläuterungen zur Situation :
        
        wie eingangs geschrieben, enthält die Datei inzwischen einige 10.000 Zeilen. Die Datei ist mehrere MB groß.
        Der Rechner, auf dem das Mischen (derzeit) läuft hat 1 GB RAM.
        Das Mischskript läuft ohne besondere Priorität unter einer GUI. Es können auch noch gleichzeitig andere Anwendungen laufen (z.B. Browser).
        
        Mein subjektiver Eindruck ist wie ebenfalls schon beschrieben, daß die Bereiche innerhalb der Arrays, aus denen die jeweilige Zeile kommt bzw. dann geschrieben wird überproporzional oft gleich sind.
        Also ich würde das so beschreiben, daß die Mischung nicht immer vollständig über das ganze Array sondern zum Teil "blockweise" durchgeführt wird. In diesem Fall könnte das reltiv niedrige Verhältnis von verfügbarem RAM und Größe der Datei eine Rolle spielen - oder eben auch nicht.
        
        So abwegig halte ich als Laie das nicht und deshalb frage ich hier im Forum nach, ob jemand da schon Erfahrungen gesammelt hat.
        
        Raubtier
        
        2015-01-03 18:29
        
        User since
        2012-05-04
        1081 articles
        BenutzerIn
        
        Also, wenn da mehrere 10000 Zeilen drin sind, dann gibt es ja 1e4! = 2.8e35659 mögliche Permutationen. Der Randseed ist aber deutlich weniger lang. Und der RNG hat einen internen State. Ich habe keine Ahnung, ob das hier irgendwelche Probleme verursachen kann, d.h. ob dadurch bestimmte Permutationen wahrscheinlicher sind als andere. Fischer-Yates geht ja von einem perfekten RNG aus. Vielleicht probierst du mal einen eigenen Fischer-Yates mit Math::Random::Secure aus.
  - +2 replies
  - qwe123qwe
    
    2015-01-02 18:59
    User since
    2013-10-08
    65 articles
    BenutzerIn
    
    ich hab das jetzt erst einmal so umgesetzt :
    
    Code (perl): (dl )
    
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
    
    #!/usr/bin/perl # Prog mischen.pl use strict; use warnings; my @alteliste = (); my @neueliste = (); my %bereits_gezogen = (); my $gezogen; # alte Datei einlesen open(UNGEMISCHTEDATEI,"<ungemischte_liste") || die "kann ungemischte Datei nicht zum Einlesen öffnen : $!"; while (my $zeile = <UNGEMISCHTEDATEI>) { push (@alteliste,$zeile); } close (UNGEMISCHTEDATEI); # ziehen ohne Zurücklegen for ( 1 .. $#alteliste ) { $gezogen = int (rand($#alteliste)); redo if exists $bereits_gezogen{$gezogen}; push (@neueliste, $alteliste[$gezogen]); $bereits_gezogen{$gezogen}++; } # neue Datei schreiben open(GEMISCHTEDATEI,">gemischte_liste") || die "kann gemischte Datei nicht zum Schreiben öffnen : $!"; foreach (@neueliste) { print GEMISCHTEDATEI ("$_"); } close (GEMISCHTEDATEI);
    
    Die neue Liste ist noch um eine Zeile kürzer als die alte. Sieht jemand auf die Schnelle, wie ich die noch herbekomme ?
    
    Ich versuch jetzt folgendermaßen die "Qualität" der Mischerei abzuschätzen:
    ich habe am Anfang meiner Testdatei 10 Zeilen, die mit a angehen und am Ende 10 die mit z angehen. Dazwischen sind 50 Zeilen, die weder mit a noch mit z angehen. Nach dem Mischen zähle ich die Zeilen, die in den ersten Bzw. letzten 10 Zeilen jeweils mit a bzw. z angehen.
    Bei einer guten Durchmischung sollten bei mehreren Versuchen im Durchschnitt unter den ersten wie auch unter den letzten 10 Zeilen genauso viele mit a wie mit z angehen.
    Stimmt das so oder habe ich da einen Denkfehler ?
    Last edited: 2015-01-02 19:00:29 +0100 (CET)
    - Raubtier
      
      2015-01-03 11:36
      
      User since
      2012-05-04
      1081 articles
      BenutzerIn
      
      Dein Algorithmus ist vor allem auch ineffizient. Stell dir mal ein sehr langes Array vor. Am Ende ist nur noch ein Element nicht gezogen worden, aber deine Schleife muss noch sehr oft würfeln, bis sie es endlich findet.
      
      Edit: s/for allem/vor allem/; - meine Güte, zu viele Schleifen hier ;-)
- +2 replies
- Raubtier
  
  2015-01-03 11:31
  User since
  2012-05-04
  1081 articles
  BenutzerIn
  Gucken wir doch einmal nach, wie das aktuell implementiert ist.
  
  Zeilen 873--878 aus der ListUtil.xs sind die interessanten:
  
  Code: (dl )
  
  1 2 3 4 5 6
  
  for (index = items ; index > 1 ; ) { int swap = (int)(Drand01() * (double)(index--)); SV *tmp = ST(swap); ST(swap) = ST(index); ST(index) = tmp; }
  
  Das sieht nach Fischer-Yates aus.
  
  Ich sehe also kein Problem in dem shuffle aus List::Util.
  
  Hast du mal ein Beispiel, wenn das Mischen fehlschlägt? Ich würde mal (natürlich nur zum Testen!) srand festsetzen, sodass es reproduzierbar wird. Ansonsten wäre ich sehr vorsichtig mit Gefühlen, dass etwas nicht richtig gemischt ist.
  Last edited: 2015-01-03 11:33:08 +0100 (CET)
  - qwe123qwe
    
    2015-01-03 11:57
    
    User since
    2013-10-08
    65 articles
    BenutzerIn
    
    ja, das ist mir schon klar. Deswegen will ich ja auch die Teststrategie fahren. Wird aber ein paar Tage dauern bis ich dazu komme.
    
    "Gefühlmäßig" erscheinen Zeilen der ersten x Prozent der alten Liste überproporzional oft im oberen Bereich der neuen Liste und entsprechend die letzten y Prozent im unteren Bereich. Das will ich mich der beschriebenen Strategie testen.
    Sicherlich wird's auch da bessere Verfahren geben.
    
    Laut den oben angebenen Links arbeitet ja auch der "shuf" - Befehl mit Fisher-Yates.
    
    Ich schau mal, daß ich die Tests möglichst bald durchlaufen lasse.
    Danke wieder mal für's Kümmern.
- qwe123qwe
  
  2015-01-10 09:59
  User since
  2013-10-08
  65 articles
  BenutzerIn
  So, ich denke ich hab den Hasen im Pfeffer gefunden.
  
  Nachdem ich das Skript mit "Shuffle" fertig geschrieben hatte und ich keine Auffälligkeiten mehr bemerkt habe, habe ich mir den Quellcode des Programms angesehen, das mich überhaupt erst auf den Gedanken mit der ungleichen Verteilung gebracht hat. Dort tauchen folgende Zeilen auf
  
  Code: (dl )
  
  1 2
  
  geeqie-1.0/src/slideshow.c: guint p = (double)rand() / ((double)RAND_MAX + 1.0) * array->len; geeqie-1.0/src/collect.c: random = (guint) (1.0 * length * rand()/(RAND_MAX + 1.0));
  
  ich denke , das RAND_MAX führt tatsächlich dazu, daß die Mischung nicht ganz sauber erfolgt.
  Ich halte das Problem damit für gelöst, da mein Skript eben keine Beschränkungen beinhaltet.
  
  Danke nochmal an alle fürs Ansehen !

View all threads created 2014-12-27 17:42.