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

Question

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?

Answer 1

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