"Теологический" вопрос о динамических массивах

← →
Franzy (2004-10-27 08:12) [0]

Пишу прогу, в которой активно используются динамические массивы. Причем окончательная длина части массивов не известна до самого окончания расчета даже приблизительно (задача как раз и заключается в создании массива определенного типа данных; причем элементы в массив только добавляются). В связи с этим встала проблема выделения памяти при добавлении в массив нового элемента. Вроде бы ничего сложного - просто пишем inc(n); setLength(a, n); при каждом увеличении длины масива а... верно? Но я тут подумал... Ведь это будет повторяться сотни и тысячи раз, а то и больше. Не вызовет ли это каких-либо глюков (виндов)? Или еще каких проблем, например, замедлении работы (я, честно говоря, не представляю, например, сколько флопов уходит на такую операцию... Если 10, еще нормально, если 100 - уже фигово :)). Такой вот "теологический вопрос".

В принципе, можно увеличивать длину массива сразу, скажем, на 100, и делать это только тогда, когда его емкости перестает хватать; а по окончании расчета лишние элементы просто обкарнать. Но это сложнее в реализации, и я не уверен, стоит ли с этим возиться, если на самом деле никаких проблем не возникнет...

Жду комментариев от Гуру :))

← →
Юрий Зотов © (2004-10-27 08:24) [1]

IMHO, глюков быть не должно, а замедление работы возможно. Весь вопрос в том, каким это замедление окажется.

Но почему бы не набросать простенькую тестовую программу и на ней все проверить? Просто прогнать единичный прирост длины массива в цикле (скажем, от единицы до миллиона) и засечь время (GetThreadTimes). А по результатам уже и решать, каким должен быть алгоритм.

← →
КаПиБаРа © (2004-10-27 08:28) [2]

Franzy (27.10.04 8:12)
При необходимости увеличения размера массива до 64 элементов увеличивай на 16, больше 64 элементов на Length div 4

← →
Думкин © (2004-10-27 08:35) [3]

Реализация таких конструкций на Дельфи, неплохо описана в книге Бакнелла.

← →
icWasya © (2004-10-27 10:18) [4]

http://www.delphimaster.ru/articles/dyntable/index.html

← →
panov © (2004-10-27 10:27) [5]

Так как у тебяИспользуй "упреждающее" выделение памяти.

Например, память первый раз выделяется под 64 эелемента.
Каждый следующий раз выделяется память не под 1 элемент, а сразу(например) под Length(Array)/8

> Ведь это будет повторяться сотни и тысячи раз, а то и больше.
> Не вызовет ли это каких-либо глюков (виндов)? Или еще каких
> проблем, например, замедлении работы (я, честно говоря,
> не представляю, например, сколько флопов уходит на такую
> операцию... Если 10, еще нормально, если 100 - уже фигово

Да, замедление работы будет. Потому что память будет перераспределяться. Посмотри, как реализовано в TList - сначала выделяем 1, потом 2, 4, 8, 16, 32, далее - по 64 (если не путаю). Или сразу TList используй.
Если честно - то добавление сотни элементов в массив даже по-одному - дело довольно быстрое (при разумном размере элементов, конечно).

Не просто перераспределяться, но еще и фрагментироваться.
Потому желательно уже первое выделение сделать равным ориетировачному максимальному размеру.

← →
Franzy (2004-10-28 00:28) [8]

Хммм... Идея с увеличением массива не на фиксированное число, а на 25%, честно говоря, мне едва ли подойдет. Потому что если длина массива эдак 1000, а нужно 1001, мы захапаем лишних 249 мест :) Хотя с другой стороны........ Нет, лучше все-таки увеливать на фиксированное число. Кстати, тут везде предлагается увеличивать на степень двойки - 4,16,64... Это как-то связано с особенностями памяти/адресации? Или из иных соображений?

"Теологический" вопрос о динамических массивах Найти похожие ветки