С какой стороны добавлять в список TList

 Дисклеймер. 
Надеюсь, вы понимаете, что к любым цифрам в Интернете
следует относиться с осторожностью.

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

program SpeedTest;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.Classes,
  System.SysUtils,
  System.Diagnostics;

const
  cTestSize  = 1000000;

var
  t : TStopwatch;

function ListAdd:integer;
var
  i, j : Integer;
  k, m : integer;
  list : TList;
begin
  list := TList.Create;
  t := TStopwatch.StartNew;
  for i := 1 to cTestSize do
  begin
    list.Add(nil);
  end;
  t.Stop;
  list.Free;
  result := t.ElapsedMilliseconds;
end;

function ListInsert:integer;
var
  i, j : Integer;
  k, m : integer;
  list : TList;
begin
  list := TList.Create;
  t := TStopwatch.StartNew;
  for i := 1 to cTestSize do
  begin
    list.Insert(0, nil);
  end;
  t.Stop;
  list.Free;
  result := t.ElapsedMilliseconds;
end;

begin
  try
    WriteLn('Add         : ', FormatFloat('0.000', ListAdd / 1000));
    WriteLn('Insert      : ', FormatFloat('0.000', ListInsert / 1000));
  except
    on e: exception do
      writeln(e.Message);
  end;
  writeln('I''m finished.');
  readln;
end. 

Вроде бы, при добавлении сложность должна нарастать линейно, а при вставке квадратично, но насколько всё серьёзно?
Поиграемся с cTestSize и получим табличку:

Число элементов (шт.) 1 000 10 000 100 000 500 000 1 000 000
Добавление (сек.) 0.000 0.000 0.000 0.004 0.009
Вставка (сек.) 0.000 0.018 1.818 48,318 242.976

Добавление элементов в конец несущественно.
Вставка в начало становится заметной на 10000 элементов и, как и положено квадратичной функции, проблема стремительно нарастает.

Как только мы говорим о нескольких тысячах элементов списка, каждый TList.Insert должен вызывать вопросы... 

 

Метки: