Mirror

Shuffling data using a parallel algorithm (Views: 708)

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

<< Back to main page