Daten mischen mit Hilfe eines "Parallelen Algorithmus"

[sakura]

Hi DP-ler,

vorgestellt habe ich die Lösung hier: QuickUnsort und hinterlasse hier mal die gleichen Spuren :-)

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:...