Array per Zufall sortieren

[flocki]

Hi folks,

ich habe ein array namens @test_random. Dieses hat ca. 2.800.000 Einträge.
ich müsste nun dieses Array per  zufall sortieren. Aber leider läuft meine Version sehr, sehr langsam. Am langsamsten läuft der Code in Zeile 80 aus dem unten folgenden Code-Fragment. Ich nehme stark an, dass es an splice liegt. Der Ca. 2.8000.000 malige Aufruf von splice geht anscheinend sehr, sehr langsam.
Kommentiere ich die Zeile 80 aus, läuft das Programm in ca. 6 Minuten durch, was sehr akzeptabel ist und die Einträge des Arrays sind orginalgetreu in eine Datei geschrieben worden.
Schalte ich aber Zeile 80 dazu, dauert der Durchlauf des Programmes ca. 9 Stunden, was leider nicht mehr akzeptabel ist. Der unten aufgelistete Code-Teil macht zwar, was ich gerne hätte, aber leider relativ ineffizient (denke ich mal, es muss doch einen schnelleren Weg geben um ein Array per Zufall zu sortieren). Deshalb meine Bitte: Hat jemand von euch eine Idee, wie ich "schonender" ein Array per Zufall sortieren kann?

5: my $sanzahl=@test_random;
10: my $superanzahl=$sanzahl;
20: my @my_random_temp;
30: for ($i=0;$i<$superanzahl;$i++) {
40:    $my_random_temp[$i]=$i;
50: }
60: for ($i=0;$i<$superanzahl;$i++) {
70:    print OUTFILE1 $test_random[$i];
80:    print OUTFILE2 $test_random[splice(@my_random_temp, int(rand($anzahl)), 1)];
90:    $anzahl=$anzahl-1;
100: }

viele Grüße

flocki

[rolfrost]

Mahlzeit

Schalte ich aber Zeile 80 dazu, dauert der Durchlauf des Programmes ca. 9 Stunden, was leider nicht mehr akzeptabel ist. Der unten aufgelistete Code-Teil macht zwar, was ich gerne hätte, aber leider relativ ineffizient (denke ich mal, es muss doch einen schnelleren Weg geben um ein Array per Zufall zu sortieren). Deshalb meine Bitte: Hat jemand von euch eine Idee, wie ich "schonender" ein Array per Zufall sortieren kann?

Probier mal das shuffle

subfunktion menge mischen (siehe PERL Doku: fisher_yates_shuffle)

sub shuffle{
 my $array = shift;
 my $i;
 for ($i = @$array; --$i;){
  my $j = int rand ($i+1);
  next if $i == $j;
  @$array[$i,$j] = @$array[$j,$i];
 }
}

und schreib dann die Datei.

Gruß, Rolf

[flocki]

Danke für die rasche Antwort. Super!

[Cheatah]

Hi,

ich müsste nun dieses Array per  zufall sortieren. Aber leider läuft meine Version sehr, sehr langsam.

hast Du

perldoc perlfaq4, "How do I shuffle an array randomly?"

gelesen? Die Codes in der Perl-FAQ sind zumeist hochgradig effizient.

Am langsamsten läuft der Code in Zeile 80 aus dem unten folgenden Code-Fragment. Ich nehme stark an, dass es an splice liegt.

"You've probably seen shuffling algorithms that works using splice, [...] This is bad because [...]"

Cheatah

[flocki]

Danke für die rasche Antwort. Super!