Shuffling data using a parallel algorithm (Views: 29)
Problem/Question/Abstract: There are many solutions for sorting your data (Bubblesort, QuickSort, Merge and Divide, ...), however if you ever want to shuffle your data, often you'll be left alone. Answer: A common way to merge your data Most algorithms shuffling your data are based upon a simple Random based algorithm that swaps different positions in an array with each other over and over again. Long enough that you may say that the data are in a unordered position. A single thread (usually your main application) access the data in different positions multiple times and does it often enough to provide a solution you will accept as "merged". // 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; Splitting the work and get many "slaves" working on one problem Now we want to take the idea a step further and let multiple threads do the work of shuffeling our data. All threads access the same data source and shuffle the data within parallel. Actually, every worker thread does the job of shuffeling the data itself, while other threads shuffle the data at other positions at the same time. We just have to ensure that no two threads are accessing the same memory spaces at the same time. For matters of simplyfication I have used a global critical section to do the job, however, you should ensure it for each data slot independently. This way in most cases the method will need little more time than having a single thread do the work, however, it should provide a higher probability of well merged data (Whatever we should understand here!). in order to reach a better merging result, every thread should have its own random number generator, rather than all threads accessing the same number pool. The sample provided with this article will provide both ways. First using the standard Delphi random number generator for all threads, second implementing a random number generator with every thread. (The generator is not of great quality, however, it shows you the idea behind the logic.) NOTE: In case your Delphi-Version does not provide the Function RandomRange (unit Math.pas), simply use the following replacement.begin if AFrom > ATo then Result := Random(AFrom - ATo) + ATo else Result := Random(ATo - AFrom) + AFrom; end; Next you'll see the defining part of the shuffle thread class: 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 line 19 in the source code, of the example provided with the article, you'll find a compiler switch. Enable it to enable the thread owned random number generator, disable it to use the random number pool of Delphi for all threads. Component Download: http://www.baltsoft.com/files/dkb/attachment/Shuffle.ziphttp://www.baltsoft.com/files/dkb/attachment/Shuffle.zip |