Delphi - What object (multidimensional array, etc) will work?

Question

I have a need to keep the top ten values in sorted order. My data structure is:

TMyRecord = record
  Number: Integer;
  Value: Float;
end

I will be calculating a bunch of float values. I need to keep the top 10 float values. Each value has an associated number. I want to add "sets"... If my float Value is higher than one of the top 10, it should add itself to the list, and then the "old" number 10, now 11, gets discarded. I should be able to access the list in (float value) sorted order...

It is almost like a TStringList, which maintains sorted order....

Is there anything like this already built into Delphi 2010?

Answer 1

You can use a combination of the generic list Generics.Collections.TList<TMyRecord> and insertion sort.

Your data structure is like this

TMyRecord = record
  Number: Integer;
  Value: Float;
end;

var
  Top10: TList<TMyRecord>;

You'll need to use Generics.Collections to get the generic list.

Instantiate it like this:

Top10 := TList<TMyRecord>.Create;

Use this function to add to the list:

procedure Add(const Item: TMyRecord);
var
  i: Integer;
begin
  for i := 0 to Top10.Count-1 do 
    if Item.Value>Top10[i].Value then
    begin
      Top10.Insert(i, Item);
      Top10.Count := Min(10, Top10.Count);
      exit;
    end;
  if Top10.Count<10 then
    Top10.Add(Item);
end;

This is a simple implementation of insertion sort. The key to making this algorithm work is to make sure the list is always ordered.

Answer 2

David's answer is great, but I think as you progress through the data, you'll fill the list pretty fast, and the odds of having a value greater than what's already in the list probably decreases over time.

So, for performance, I think you could add this line before the for loop to quickly discard values that don't make it into the top 10:

if (Item.Value <= Top10[Top10.Count - 1].Value) and (Top10.Count = 10) then
  Exit;

If the floats are always going to be above a certain threshold, it might make sense to initialize the array with 10 place-holding records with values below the threshold just so you could change the first line to this:

if (Item.Value <= Top10[9].Value) then
  Exit;

And improve the method to this:

procedure Add(const Item: TMyRecord);
var
  i: Integer;
begin

  // Throw it out if it's not bigger than our smallest top10
  if (Item.Value <= Top10[9].Value) then
    Exit;

  // Start at the bottom, since it's more likely
  for i := 9 downto 1 do 
    if Item.Value <= Top10[i - 1].Value then
    begin
      // We found our spot
      Top10.Insert(i, Item);
      // We're always setting it to 10 now
      Top10.Count := 10;
      // We're done
      Exit;
    end;

  // Welcome, leader!
  Top10.Insert(0, Item);
  // We're always setting it to 10 now
  Top10.Count := 10;
end;