Delphi - Какой объект (многомерный массив и т. Д.) Будет работать? - PullRequest
Новая
       29

Delphi - Какой объект (многомерный массив и т. Д.) Будет работать?

5 голосов
/ 03 декабря 2011

Мне нужно сохранить первые десять значений в отсортированном порядке.Моя структура данных: 

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

Я буду вычислять несколько значений с плавающей точкой.Мне нужно сохранить топ-10 значений с плавающей точкой.Каждое значение имеет связанный номер.Я хочу добавить «наборы» ... Если значение с плавающей запятой выше, чем один из 10 лучших, он должен добавить себя в список, и тогда «старое» число 10, теперь 11, будет отброшено.Я должен иметь возможность получить доступ к списку в (с плавающей запятой) отсортированном порядке ...

Это почти как TStringList, который поддерживает отсортированный порядок ....

Есть ли что-нибудь подобноеуже встроен в Delphi 2010?

Ответы [ 4 ]

5 голосов
/ 03 декабря 2011

Вы можете использовать комбинацию общего списка Generics.Collections.TList<TMyRecord> и сортировки вставок.

Ваша структура данных такова 

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

var
  Top10: TList<TMyRecord>;

Вам нужно будет использовать Generics.Collections, чтобы получить общий список.

Создайте это так: 

Top10 := TList<TMyRecord>.Create;

Используйте эту функцию для добавления в список: 

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;

Это простая реализация сортировки вставкой. Ключ к тому, чтобы этот алгоритм работал, должен убедиться, что список всегда упорядочен.

4 голосов
/ 03 декабря 2011

Ответ Дэвида великолепен, но я думаю, что по мере прохождения данных вы будете заполнять список довольно быстро, и вероятность того, что значение будет больше, чем то, что уже есть в списке, вероятно, со временем уменьшится.

Итак, для производительности, я думаю, вы могли бы добавить эту строку перед циклом for, чтобы быстро отбрасывать значения, которые не попадают в топ-10: 

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

Если значения с плавающей точкой всегда будут выше определенного порогового значения, возможно, имеет смысл инициализировать массив с 10 записями, занимающими место, со значениями ниже порогового значения, чтобы вы могли изменить первую строку следующим образом: 

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

И улучшить метод до этого: 

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;
2 голосов
/ 03 декабря 2011

Поскольку вы работаете с фиксированным числом элементов, вы можете использовать простой массив TMyRecord, например: 

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;
1 голос
/ 03 декабря 2011

Я бы не стал беспокоиться ни о чем, кроме прямого 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.
...