Списки на базе массивов традиционно при нехватке места в массиве для очередного добавляемого элемента увеличиваются созданием нового массива удвоенного размера и копированием содержимого старого массива в новый.
Т.е. нет разницы 1048577 элементов добавлено или 2097152, массив будет размером 2097152 элементов.
Оказывается в Qt используется стратегия позволяющая более экономно расходовать память.
Цитата:
We build the string out dynamically by appending one character to it at a time. Let's assume that we append 15000 characters to the QString string. Then the following 18 reallocations (out of a possible 15000) occur when QString runs out of space: 4, 8, 12, 16, 20, 52, 116, 244, 500, 1012, 2036, 4084, 6132, 8180, 10228, 12276, 14324, 16372. At the end, the QString has 16372 Unicode characters allocated, 15000 of which are occupied.
The values above may seem a bit strange, but here are the guiding principles:
[*]QString allocates 4 characters at a time until it reaches size 20.
[*]From 20 to 4084, it advances by doubling the size each time. More precisely, it advances to the next power of two, minus 12. (Some memory allocators perform worst when requested exact powers of two, because they use a few bytes per block for book-keeping.)
[*]From 4084 on, it advances by blocks of 2048 characters (4096 bytes). This makes sense because modern operating systems don't copy the entire data when reallocating a buffer; the physical memory pages are simply reordered, and only the data on the first and last pages actually needs to be copied.
http://doc.qt.digia.com/4.7-snapshot/co ... strategiesС использованием этой стратегии размер массива при 1048577 добавленных элементах будет равен 1050612 элементам.
Проверил эту стратегию в А2, и оказалось, что экономия памяти даже не сказалась на производительности.
Следующий код с использованием что одной что другой стратегии выполнялся примерно 170 секунд в обоих случаях:
Код:
MODULE ListTest; (** AUTHOR ""; PURPOSE ""; *)
IMPORT
Commands, Lists, Random, PreciseTimer;
PROCEDURE Test*(context: Commands.Context);
VAR
r: Random.Generator;
l: Lists.LongintList;
i, n: LONGINT;
t: HUGEINT;
BEGIN
context.out.Ln;
t := PreciseTimer.GetTicks();
NEW(r);
NEW(l, {Lists.LIST_SORTED, Lists.LIST_NO_DUPLICATES});
FOR i := 0 TO 525000 DO
n := r.Dice(500000);
IF l.IndexOf(n) = -1 THEN
l.Add(n)
END
END;
t := PreciseTimer.GetTicks() - t;
context.out.Ln;
context.out.String("Count: ");
context.out.Int(l.GetCount(), 0);
context.out.Ln;
context.out.String("Time: ");
context.out.Float(PreciseTimer.GetTime(t), 15);
context.out.Ln;
END Test;
END ListTest.
ListTest.Test ~
SystemTools.Free ListTest Lists ~
Код библиотеки
http://subversion.assembla.com/svn/ober ... /Lists.Mod