AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Code-Bibliothek Library: Algorithmen Delphi Daten mischen mit Hilfe eines "Parallelen Algorithmus"

Daten mischen mit Hilfe eines "Parallelen Algorithmus"

Ein Thema von sakura · begonnen am 20. Feb 2004
Antwort Antwort
Benutzerbild von sakura
sakura

Registriert seit: 10. Jun 2002
Ort: München
11.412 Beiträge
 
Delphi 11 Alexandria
 
#1

Daten mischen mit Hilfe eines "Parallelen Algorithmus&q

  Alt 20. Feb 2004, 13:42
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.



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.



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ß,
......
Angehängte Dateien
Dateityp: zip shuffle_267.zip (4,1 KB, 114x aufgerufen)
Daniel W.
Ich bin nicht zurück, ich tue nur so
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 02:14 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz