Какова сложность SetLength?

Question

Мне часто приходится многократно называть SetLength для увеличения длины динамического массива. Какова сложность следующего кода?

const 
    n = 1000000; 
var 
    a: array of integer; 

for i := 1 to n do 
    SetLength(a, i); 

Answer 1

Предполагая, что сложность SetLength сложна O (1), ваш алгоритм будет иметь сложность O (n), потому что вы вызываете SetLength n раз.

Может быть, эта статья может помочь вам в дальнейшем связанные вопросы: https://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm

Answer 2

Одиночный вызов SetLength может иметь O (N) сложность, потому что если память после окончания массива используется для чего-то еще, всех массив должен быть скопирован в новую позицию (т. е. может потребоваться создать совершенно новый массив, скопировать содержимое из старого, освободить старый).

Это предполагает, что код, который вы указали, будет иметь сложность O (n^2). Однако, если вы сравниваете это, вы, скорее всего, обнаружите, что удвоение n удваивает время работы, предполагая, что весь алгоритм работает в O (n), что, в свою очередь, предполагает, что SetLength является O (1). Наиболее вероятно, что диспетчер памяти фактически занимает больше памяти, чем вы запросили для массива. Поэтому в последующих вызовах SetLength он может легко увеличить длину массива, потому что память после окончания массива на самом деле уже зарезервирована для массива.

Однако я бы все равно не увеличивал динамический массив по одному на каждой итерации. Вы по-прежнему получите гораздо лучшую производительность (особенно, если вы запускаете миллионы итераций), если вы делаете только один вызов SetLength заранее. В вашем случае я бы

SetLength(a, n); 
for i := 1 to n do 
    // no need for SetLength here 

Если вы не знаете, как большой массив должен быть, вы можете сделать что-то вроде этого

SetLength(a, 16); 
aLength := 0; 
while Whatever do 
begin 
    if aLength = Length(a) then 
    SetLength(a, aLength * 2); 
    ... 
    a[aLength] := ... 
    Inc(aLength); 
    ... 
end; 

Здесь я использовал 16 для начальной длины массива и удвоить длину после того, как массив заполнится. Они могут быть скорректированы в зависимости от проблемы.

Кроме того, рассмотрите, можете ли вы использовать некоторую доступную структуру данных, используя TList, например, вам не нужно беспокоиться о том, чтобы увеличить массив самостоятельно. Я не уверен, есть ли общая версия TList в FreePascal, но это, вероятно, лучший вариант.