Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

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

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

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

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

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

Anatoly Podgoretsky (2004-10-27 11:38:00) [2]
Не просто перераспределяться, но еще и фрагментироваться.
Потому желательно уже первое выделение сделать равным ориетировачному максимальному размеру.

TUser (2004-10-27 10:32:00) [3]

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

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

panov (2004-10-27 10:27:00) [4]
Так как у тебяИспользуй "упреждающее" выделение памяти.

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

icWasya (2004-10-27 10:18:00) [5]
http://www.delphimaster.ru/articles/dyntable/index.html

Думкин (2004-10-27 08:35:00) [6]
Реализация таких конструкций на Дельфи, неплохо описана в книге Бакнелла.

КаПиБаРа (2004-10-27 08:28:00) [7]
Franzy (27.10.04 8:12)
При необходимости увеличения размера массива до 64 элементов увеличивай на 16, больше 64 элементов на Length div 4

Юрий Зотов (2004-10-27 08:24:00) [8]
IMHO, глюков быть не должно, а замедление работы возможно. Весь вопрос в том, каким это замедление окажется.

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

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »