Delphi-PRAXiS - QuickUnsort

Zitat:

Zitat von morbo

Hat da jemand eine Funktion parat?

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

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ß,
...:cat:...