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?

David Heffernan · Accepted Answer · 2011-12-02 23:02:42Z

5

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.

edited Dec 2, 2011 at 23:02

answered Dec 2, 2011 at 22:18

David Heffernan

616k46 gold badges1.1k silver badges1.5k bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Marcus Adams · Accepted Answer · 2011-12-03 02:58:41Z

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;

Remy Lebeau · Accepted Answer · 2011-12-02 23:03:29Z

2

Since you are working with a fixed number of items, you could use a plain TMyRecord array, eg:

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

const
  MaxRecordsInTopTen = 10;

var
  TopTen: array[0..MaxRecordsInTopTen-1] of TMyRecord; 
  NumRecordsInTopTen: Integer = 0;

procedure CheckValueForTopTen(Value: Float; Number: Integer);
var
  I, J, NumToMove: Integer;
begin
  // see if the new Value is higher than an value already in the list
  for I := 0 to (NumRecordsInTopTen-1) do
  begin
    if Value > TopTen[I].Value then
    begin
      // new Value is higher then this value, insert before
      // it, moving the following values down a slot, and
      // discarding the last value if the list is full

      if NumRecordsInTopTen < MaxRecordsInTopTen then
        NumToMove := NumRecordsInTopTen - I
      else
        NumToMove := MaxRecordsInTopTen - I - 1;

      for J := 1 to NumToMove do
        Move(TopTen[NumRecordsInTopTen-J], TopTen[NumRecordsInTopTen-J-1], SizeOf(TMyRecord));

      // insert the new value now
      TopTen[I].Number := Number;
      TopTen[I].Value := Value;
      NumRecordsInTopTen := Min(NumRecordsInTopTen+1, MaxRecordsInTopTen);

      // all done
      Exit;
    end;
  end;

  // new value is lower then existing values,
  // insert at the end of the list if room
  if NumRecordsInTopTen < MaxRecordsInTopTen then
  begin
    TopTen[NumRecordsInTopTen].Number := Number;
    TopTen[NumRecordsInTopTen].Value := Value;
    Inc(NumRecordsInTopTen);
  end;
end;

answered Dec 2, 2011 at 23:03

Remy Lebeau

609k36 gold badges516 silver badges875 bronze badges

3 Comments

David Heffernan Over a year ago

this looks much more complex than the generic list

Remy Lebeau Over a year ago

Yes, but on the other hand it doesn't allocate and reallocate memory all over the place like TList does. It is a single fixed memory block that gets updated inline as needed.

David Heffernan Over a year ago

hardly. Once the list has its 10 elements then there is no more allocation.

Glenn1234 · Accepted Answer · 2011-12-03 10:28:55Z

I wouldn't bother with anything other than straight Object Pascal.

{$APPTYPE CONSOLE}
program test2; uses sysutils, windows;
  const
    MAX_VALUE = $7FFF;
    RANDNUMCOUNT = 1000;
  var
    topten: array[1..10] of Longint;
    i, j: integer;
    Value: Longint;
  begin
    randomize;
    FillChar(topten, Sizeof(topten), 0);
    for i := 1 to RANDNUMCOUNT do
      begin
        Value := Random(MAX_VALUE);
        j := 1;
        while j <= 10 do
          begin
            if Value > topten[j] then
              begin
                 Move(topten[j], topten[j+1], SizeOf(Longint) * (10-j));
                 topten[j] := Value;
                 break;
              end;
            inc(j);
          end;
     end;
    writeln('Top ten numbers generated were: ');
    for j := 1 to 10 do
      writeln(j:2, ': ', topten[j]);
    readln;
  end.

Collectives™ on Stack Overflow

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

4 Answers 4

Comments

Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related