Проведем небольшой замер скорости случайного и последовательного доступа, используя:
- статический массив (array, должен размещаться на стеке)
- класс-контейнер TList (размещается в куче)
- динамический массив (тоже размещается в куче)
Используем массив из 10 миллионов элементов имеющих типы данных "integer" и "varaint". При необходимости вы можете легко изменить тип в соответствующей секции программы.
program Bench1; uses SysUtils, Classes, DateUtils, Math; const MaxDimension = 10000000; type TTestedValueType = integer; PTestedValueType = ^TTestedValueType; var D1, D2: TDateTime; RndAddr: array [0..MaxDimension - 1] of integer; TestArray: array [0..MaxDimension - 1] of TTestedValueType; TestList: TList; TestDynArray: array of TTestedValueType; p: ^TTestedValueType; i: integer; Sum: double; begin Randomize; writeln('Prepare random access array'); for i := 0 to MaxDimension - 1 do RndAddr[i] := Math.RandomRange(0, MaxDimension); // Simple array for i := 0 to MaxDimension - 1 do TestArray[i] := 0; D1 := Now; for i := 0 to MaxDimension - 1 do TestArray[RndAddr[i]] := RndAddr[i]; D2 := Now; writeln('Simple array. Random access. Elapsed, sec: ', DateUtils.SecondSpan(D2, D1):5:2); Sum := 0; D1 := Now; for i := 0 to MaxDimension - 1 do Sum := Sum + TestArray[i]; D2 := Now; writeln('Simple array. Sequential access. Elapsed, sec: ', DateUtils.SecondSpan(D2, D1):5:2, '. Sum: ', Sum); // TList writeln('Prepare list'); TestList := TList.Create; TestList.Capacity := MaxDimension; for i := 0 to MaxDimension - 1 do begin new(p); p^ := 0; TestList.Add(p); end; D1 := Now; for i := 0 to MaxDimension - 1 do PTestedValueType(TestList[RndAddr[i]])^ := RndAddr[i]; D2 := Now; writeln('TList. Random access. Elapsed, sec: ', DateUtils.SecondSpan(D2, D1):5:2); Sum := 0; D1 := Now; for i := 0 to MaxDimension - 1 do Sum := Sum + PTestedValueType(TestList[i])^; D2 := Now; writeln('TList. Sequential access. Elapsed, sec: ', DateUtils.SecondSpan(D2, D1):5:2, '. Sum: ', Sum); for i := 0 to MaxDimension - 1 do dispose(PTestedValueType(TestList[i])); TestList.Free; // Dynamic array writeln('Prepare dynamic array'); SetLength(TestDynArray, MaxDimension); for i := 0 to MaxDimension - 1 do TestDynArray[i] := 0; D1 := Now; for i := 0 to MaxDimension - 1 do TestDynArray[RndAddr[i]] := RndAddr[i]; D2 := Now; writeln('Dynamic array. Random access. Elapsed, sec: ', DateUtils.SecondSpan(D2, D1):5:2); D1 := Now; Sum := 0; for i := 0 to MaxDimension - 1 do Sum := Sum + TestDynArray[i]; D2 := Now; writeln('Dynamic array. Sequential access. Elapsed, sec: ', DateUtils.SecondSpan(D2, D1):5:2, '. Sum: ', Sum); SetLength(TestDynArray, 0); end.
Результаты
Для целого типа данных оба массива ожидаемо более быстры для случайного доступа, чем список. При последовательном доступе разница не такая существенная.
Prepare random access array Simple array. Random access. Elapsed, sec: 0.12 Simple array. Sequential access. Elapsed, sec: 0.03. Sum: 3.16025412697520E+013 Prepare list TList. Random access. Elapsed, sec: 1.01 TList. Sequential access. Elapsed, sec: 0.05. Sum: 3.16025412697520E+013 Prepare dynamic array Dynamic array. Random access. Elapsed, sec: 0.13 Dynamic array. Sequential access. Elapsed, sec: 0.03. Sum: 3.16025412697520E+013
Теперь изменим тип на variant:
type TTestedValueType = variant;
Относительная разница для значений структурного типа, коим является variant, в целом не меняется, просто увеличивается общее время обработки за счет увеличения размера выделенной под массивы памяти.
Но для списка общее время случайного доступа почти не изменилось. Это объясняется структурой: в списке хранятся указатели, а они во всех тестах имеют одинаковый размер.
Prepare random access array Simple array. Random access. Elapsed, sec: 0.60 Simple array. Sequential access. Elapsed, sec: 0.74. Sum: 3.16119039688220E+013 Prepare list TList. Random access. Elapsed, sec: 1.08 TList. Sequential access. Elapsed, sec: 0.76. Sum: 3.16119039688220E+013 Prepare dynamic array Dynamic array. Random access. Elapsed, sec: 0.57 Dynamic array. Sequential access. Elapsed, sec: 0.73. Sum: 3.16119039688220E+013
Как можно видеть для разных типов данных, простых и структурных, статический или динамический массивы являются более быстрым решением при случайном или последовательном доступе к элементам.
Но именно более быстрыми, а не "лучшими". Во многих случаях управление списками при помощи TList и его аналогов может оказаться не только проще, но и производительнее за счет отсутствия необходимости реорганизации памяти при вставке/удалении элементов.