QuickUnsort

[morbo]

Hi,
ich Suche eine Funktion ala Quicksort umgedreht, die aus einer sortierten Liste eine möglichst zufällig unsortierte Liste erstellt.

Hat da jemand eine Funktion parat?

Gruß

[morbo]

Hi,
meine erste Funktion ist:

Code:

procedure Tform1.doShuffle(var sl: TStringDynArray);
var
  i, l, r1, r2: Integer;
  sTmp: String;
begin
  l := Length(sl)-1;
  Randomize;

  for i:=0 to l div 2 do
  begin
    r1 := RandomRange(0, l);
    r2 := RandomRange(0, l);
    sTmp := sl[r1];
    sl[r1] := sl[r2];
    sl[r2] := sTmp;
  end;
end;

hat jemand eine bessere?

[ims]

hi morbo
einfach mal so auf die schnelle, sollte funktionieren:

listbox1: deine sortierte liste
listbox2: das ergebnis

Delphi-Quellcode:

procedure unsort;
 var
  i : Integer;
begin
  form1.ListBox2.Clear;
  randomize;
  for i := 0 to form1.ListBox1.Items.Count - 1 do
    begin
      form1.ListBox2.Items.Add(form1.ListBox1.Items.Strings[random(form1.ListBox1.Items.Count)])
    end;
end;

wie gut diese prozedur allerdings "unsortet" weiss ich nicht. vielleicht genügts dir ja, oder hilft sonst weiter.


gruss, dave


//Edit: deine ist natürlich viel schöner und kommt ohne zus. komponenten aus..

[morbo]

Zitat von ims:

hi morbo
einfach mal so auf die schnelle, sollte funktionieren:

listbox1: deine sortierte liste
listbox2: das ergebnis

Delphi-Quellcode:

procedure unsort;
 var
  i : Integer;
begin
  form1.ListBox2.Clear;
  randomize;
  for i := 0 to form1.ListBox1.Items.Count - 1 do
    begin
      form1.ListBox2.Items.Add(form1.ListBox1.Items.Strings[random(form1.ListBox1.Items.Count)])
    end;
end;

wie gut diese prozedur allerdings "unsortet" weiss ich nicht. vielleicht genügts dir ja, oder hilft sonst weiter.


gruss, dave


//Edit: deine ist natürlich viel schöner und kommt ohne zus. komponenten aus..

Hi vielen Dank für den Vorschlag,
ohne das ich es getestet habe,
sieht es so aus das einige Enträge nach der dem "unsort" doppelt und andere danach nicht mehr vorkommen können.

Gruß

[ims]

jetzt wo du's sagts: stimmt... war dann wohl nix

vielleicht gibts dir ja noch einen anstoss.

gruss, dave

[sakura]

Zitat von morbo:

Hat da jemand eine Funktion parat?

Nein, aber das ist ein super Gebiet für "Parallele Datenverarbeitung" Daraus resultieren jetzt auch meine hier vorgestellten Lösungen. Damit es nicht zu langweilig wird, gleich einmal einen aufgesplitteten Ansatz

Die meisten Algorithmen zum Mischen von Daten basieren auf dem Ansatz ein paar Runden mit Hilfe des Random-Befehls die Daten untereinander auszutauschen. Ein einzelner Thread (die Anwendung) greift mehrmals hintereinander auf den Datenspeicher (im Beispiel ein Integer-Array) zu und vertauscht zwei Werte miteinander. Nach einer genügend hohen Anzahl an Tauschvorgängen kann man den Array als "gemischt" betrachten.

Folgende Grafik veranschaulicht den Vorgang ein wenig. Der Tausch der Daten wird sequenziell (also nacheinander) durchgeführt.

http://www.delphipraxis.com/specials...fle/single.gif

Die folgende Methode übernimmt ein solches Datenarray und mischt es.

Delphi-Quellcode:

// ShuffleArray
//   aData: pointer to an array of integer numbers (probably sorted)
//   aMin: lowest member of array to be shuffeled
//   aMax: highest member of array to be shuffeled
//   aIterations: number of iterations each thread has to do on array
procedure ShuffleArray(aData: PIntegerArray; aMin, aMax: Integer; aIterations: Integer);
var
  Source, Dest, Temp: Integer;
begin
  // for each shuffle to be done
  while aIterations > 0 do
  begin
    // get source an destination for shuffling
    Source := RandomRange(aMin, aMax);
    Dest := RandomRange(aMin, aMax);
    // swap data
    Temp := aData^[Source];
    aData^[Source] := aData^[Dest];
    aData^[Dest] := Temp;
    // one shuffle done
    Dec(aIterations);
  end;
end;

Das Ganze kann jetzt erweitert werden, indem man das Mischen in mehrere Threads auslagert, welche alle auf einen gemeinsamen Datenspeicher zu greifen und diesen dann parallel mischen. Das heißt, jeder Thread mischt den gesamten Datenspeicher für sich, während die anderen Threads zur gleichen Zeit das Gleiche am gleichen Ort tun. Raus kommt Chaos, also ein kräftig gemischtes Array.

http://www.delphipraxis.com/specials...e/threaded.gif

Diese Methode benötigt etwas mehr Zeit, als ein einzelner Thread, der die Zahlen kräftig mischt, bietet jedoch auch eine höhere Wahrscheinlichkeit gemischter Daten. Zur Simplifizierung greife ich in folgendem Beispiel auf die Critical Section zurück, um Mehrfachzugriffe auf die gleiche Zelle im Array durch unterschiedliche Threads zur gleichen Zeit zu vermeiden. Um dieses zu erreichen gibt es verschiedene Möglichkeiten, diese soll aber Genüge tun

Um die Mischverhältnisse zu optimieren sollte allerdings jeder Thread auch seinen eigenen Zufallszahlengenerator nutzen. In folgendem Beispiel sind zwei Optionen vorgestellt. Einmal wird der Zufallsgenerator (Random) aus Delphi-Unit System genutzt und das andere mal wird jedem Thread sein eigener Zufallsgenerator mitgeliefert (Stand Delphi 3).

Anmerkung Sollte in Eurer Delphi-Version die Funktion RandomRange nicht enthalten sein, so könnt Ihr diese Funktion nutzen (Unit math.pas)

Delphi-Quellcode:

function RandomRange(const AFrom, ATo: Integer): Integer;
begin
  if AFrom > ATo then
    Result := Random(AFrom - ATo) + ATo
  else
    Result := Random(ATo - AFrom) + AFrom;
end;

Jetzt erst einmal der entscheidene Teil des Shuffle-Threads. Der gesamte Code ist im Anhang enthalten.

Delphi-Quellcode:

constructor TShuffleThread.Create(aData: PIntegerArray; aMin,
  aMax: Integer; aCS: TCriticalSection; aIterations: Integer);
begin
  inherited Create(False);
  // store data
  FData := aData;
  if aMin < aMax then
  begin
    FMin := aMin;
    FMax := Succ(aMax);
  end else begin
    FMin := aMax;
    FMax := Succ(aMin);
  end;
  FCS := aCS;
  FIterations := aIterations;
  {$IFDEF UseThreadRandomize}
    Randomize;
  {$ENDIF}
  // initialize automatic freeing of thread
  FreeOnTerminate := True;
end;

procedure TShuffleThread.Execute;
var
  Source, Dest, Temp: Integer;
begin
  // for each shuffle to be done
  while FIterations > 0 do
  begin
    // get source an destination for shuffling
    Source := RandomRange(FMin, FMax);
    Dest := RandomRange(FMin, FMax);
    // enter critical data move section
    FCS.Acquire;
    try
      // swap data
      Temp := FData^[Source];
      FData^[Source] := FData^[Dest];
      FData^[Dest] := Temp;
    finally
      // leave critical data move section
      FCS.Release;
    end;
    // one shuffle done
    Dec(FIterations);
  end;
end;

In Zeile 19 findet Ihr einen Compiler Schalter. Ist dieser aktiviert, dann nutzt jeder Thread seinen eigenen Zufallszahlengenerator, ansonsten wird der Generator aus der Unit System für alle Threads parallel genutzt.

Viel Spaß,
......

[APP]

Hallo Sakura,
ich finde, diese schöne Lösung gehört unbedingt in die Library!

[sakura]

Zitat von APP:

Hallo Sakura,
ich finde, diese schöne Lösung gehört unbedingt in die Library!

Gute Idee Ich versuche mal [strg]+[v] und [strg]+[c]

......

[morbo]

Hi,
super Thread Lösung.

Wie wäre es noch mit einem Wert zu Ermittlung der Entropie um herauszubekommen ob die
geThreadede Lösung wirklich die zufälligere ist.

Gruß

[sakura]

Zitat von morbo:

Wie wäre es noch mit einem Wert zu Ermittlung der Entropie um herauszubekommen ob die geThreadede Lösung wirklich die zufälligere ist.

Viel Spass Aber für wirkliche Zufälle braucht man eh einen nicht-Pseudo-Zahlengenerator

......