CODEWITHSUNDEEP
delphiparallel-processingppl
Steve Maughan
Steve Maughan

Reputation: 1264

Find the Maximum in a List of calculated values using the Parallel Programming Library

I have a list of values. I'd like to find the maximum value. This is a common task. A simple version might be:

iBest := -1;
iMax := -1e20;
for i := 0 to List.Count - 1 do
begin
  if List[i].Value > iMax then
  begin
    iBest := i;
    iMax := List[i].Value;
  end;
end;

In my case, the .Value getter is the performance bottleneck as it invokes a time consuming calculation (~100ms) which returns the final value.

How can I make this parallel using the Parallel Programming Library?

Upvotes: 0

Views: 890

Answers (1)

J...
J...

Reputation: 31433

If the value is a calculated value and you can afford to cache, a simple solution might look something like this:

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils, Threading, DateUtils, Math, Generics.Collections, StrUtils;

type
  TFoo = class
  private
    FCachedValue : double;
    function GetValue : double;
  public
    property CalculateValue : double read GetValue;
    property CachedValue : double read FCachedValue;
  end;

  TFooList = class(TObjectList<TFoo>)
    public
      procedure CalculateValues;
      function GetMaxValue(var BestIndex : integer) : double;
  end;


function TFoo.GetValue : double;
begin
  sleep(10);   // simulate taking some time... make up a value
  FCachedValue := DateUtils.MilliSecondOfTheSecond(now);
  result := FCachedValue;
end;

procedure TFooList.CalculateValues;
begin
  TParallel.For(0, Count - 1,
    procedure (j:integer)
    begin
      self[j].CalculateValue;
    end);
end;

function TFooList.GetMaxValue(var BestIndex : Integer) : double;
var
  i, iBest : integer;
  maxval : double;
begin
  CalculateValues;
  iBest := 0;
  maxval := self[0].CachedValue;
  for i := 0 to self.Count - 1 do
  begin
    if self[i].CachedValue > maxval then
    begin
      iBest := i;
      maxval := self[i].CachedValue;
    end;
  end;
  BestIndex := iBest;
  result := maxval;
end;


var
  LFooList : TFooList;
  i, iBest : integer;
  maxval : double;
begin
  LFooList := TFooList.Create(true);
  try
    for i := 0 to 9999 do LFooList.Add(TFoo.Create);
    maxval := LFooList.GetMaxValue(iBest);
    WriteLn(Format('Max value index %d', [iBest]));
    WriteLn(Format('Max value %.6f', [maxval]));
  finally
    LFooList.Free;
  end;
  ReadLn;
end.

This way your object retains a cache of the last calculated value, which you can refresh at any time, but which you can also access quickly. It's somewhat easier to parallelize a full calculation of the list than it is to paralellize the min/max search, and if the bottleneck is the calculation then it makes sense to restrict the added complexity to that operation alone (where you know the overhead is worth it).

Upvotes: 3

Related Questions