Насколько я неправильно использую SetLength?

← →
Студент (2011-01-12 13:31) [0]

Здравствуйте... Скажите, насколько кривовато будет вот такое (или как будет сделать правильнее):

. . . For i:=0 To Length(Masss)-1 Do Begin Count:=0; For j:=0 To Length(Arrr)-1 Do If (Arrr[j].Flag=i) Then Begin Inc(Count); SetLength(Masss[i].Mass, Count); Masss[i].Mass[Count-1]:=@Arrr[j]; End; SetLength(Masss[i].Mass, Count); End; . . .

Может было лучше сначала посчитать Count в отдельном цикле? А уж потом один SetLength и заполнять?

P.S. Программа делалась наспех, это был просто отчаянный полёт мысли...

← →
Ega23 © (2011-01-12 13:37) [1]

> Может было лучше сначала посчитать Count в отдельном цикле?
> А уж потом один SetLength и заполнять?

А ты не приращай память на каждой итерации. Приращай кусками, потом в конце отсечёшь ненужное.
что-то типа
if Length(Mass) < Count then SetLength(Mass, Count + 100);
А в конце
SetLength(Mass, Count);

Таким образом уменьшишь реаллоки в 100 раз.

← →
Студент (2011-01-12 13:43) [2]

Хм... Действительно хорошо получается, спасибо...)
Просто количество этих Count не известно заранее, может оказаться любым...

А если двумя циклами - будет хуже?
Хотя наверное да, хуже... Особенно чем больше массивы...

← →
Ega23 © (2011-01-12 13:46) [3]

> А если двумя циклами - будет хуже?

А тебе не всё равно? Ну поставь не 100, а 1000. Прикинь, примерно, сколько у тебя возможное значение Count - и ставь. В конце обрежешь.
Просто считай, что на каждый SetLength по приросту длины у тебя перевыделение памяти происходит. А это - тормоза.

← →
Студент (2011-01-12 13:51) [4]

Это да... Перевыделение...
А когда в конце отсекать размер массива до Count, то тоже полностью перевыделение будет (при уменьшении-то размера)?

← →
RWolf © (2011-01-12 13:58) [5]

нет, усечение бесплатно.

← →
Ega23 © (2011-01-12 14:05) [6]

> то тоже полностью перевыделение будет (при уменьшении-то
> размера)?

Не, там просто отсекут лишнее. Условно говоря, адрес нулевого элемента не изменится.

← →
Студент (2011-01-12 14:10) [7]

Спасибо огромное...)

← →
Servy © (2011-01-13 02:09) [8]

> А ты не приращай память на каждой итерации. Приращай кусками,
> потом в конце отсечёшь ненужное.
> что-то типа
> if Length(Mass) < Count then
> SetLength(Mass, Count + 100);
>
> А в конце
> SetLength(Mass, Count);
>
> Таким образом уменьшишь реаллоки в 100 раз.

В последних версиях Делфи используется менеджер памяти FastMM, который во многом берет эту задачу на себя:

Moving data around in memory is typically a very expensive operation. Consequently, FastMM thus an intelligent reallocation algorithm to avoid moving memory as much as possible. When a block is upsized FastMM adjusts the block size in anticipation of future upsizes, thus improving the odds that the next reallocation can be done in place.

Соответственно в обыденных, не остро критичных к производительности ситуациях можно не заморачиваться.

> Условно говоря, адрес нулевого элемента не изменится.

Обычно так, хотя есть оговорка, соответственно полагаться на это не стоит:

When a pointer is resized to a smaller size, FastMM requires the new size to be significantly smaller than the old size otherwise the block will not be moved.

> [0]

Ваш код скорее всего неоптимален, так как можно существенно сократить число итераций: вы выполняете внутренний цикл Length(Arrr) * Length(Masss) раз, тогда как в данной ситуации куда более логичным кажется поменять порядок циклов и обойтись за Length(Arrr) итераций. Код примерно такой:

var Index: Integer; // для читабельности ... for J := 0 to High(Arrr) do begin Index := Arrr[J].Flag; if (Index >= 0) and (Index < Length(Masss)) then begin SetLength(Masss[Index].Mass, Length(Masss[Index].Mass) + 1); Masss[Index].Mass[High(Masss[Index].Mass)] := @Arrr[J]; end; end;

Код писал тут, за отсутствие опечаток не ручаюсь. В данном коде происходит добавление новых масс в Masss[Index].Mass, так что если в каком-либо из элементов массива Masss свойство Mass не является перед выполнением сего кода пустым массивом, то необходимо произвести дополнительные действия по предварительному обнулению старых массивов Masss[i].Mass.

Кроме того, ваши названия переменных (Arr и Masss) не указывают на их предназначение, что плохо. Я бы посоветовал переименовать их так, чтобы из их названия явно следовало их предназначение.

← →
Servy © (2011-01-13 02:22) [9]

> [D7, XP]

Извиняюсь, не обратил внимания на версию. В Delphi 7 FastMM еще не использовался, так что вы можете или подключить его вручную, или доработать код из [8], самостоятельно добавив реаллокацию "с запасом", как вам советовали ранее.

← →
Германн © (2011-01-13 02:45) [10]

Не важно какая версия Delphi используется. Важно понять суть "выделения/перераспределения" памяти при вызове SetLength.

← →
Servy © (2011-01-13 03:09) [11]

> Не важно какая версия Delphi используется. Важно понять
> суть "выделения/перераспределения" памяти при вызове SetLength.

По-моему, автору куда важнее понять, что если в его массиве Arrr все Flag равны 0, то его алгоритм будет для каждого элемента Masss кроме нулевого безуспешно, долго и напрасно искать, не завалялось ли где Flag соответствующего текущему индексу в Masss. Увеличивая при таких входных данных размер массива Masss, можно получить весьма впечатляющие потери времени, которые легко превзойдут потери от перераспределений памяти.

Впрочем вы правы, это не тот вопрос, который был задан автором :). Он же про:

> Насколько я неправильно использую SetLength?

спрашивал.

← →
KSergey © (2011-01-13 09:32) [12]

> Ega23 © (12.01.11 13:46) [3]
> по приросту длины у тебя перевыделение памяти происходит. А это - тормоза.

Тормоза - половина беды.
Хуже то, что память в итоге кончается, и под очередное "раздвижение" сплошного куска необходимой длины может уже не оказаться. Хоты пустой памяти будет действительно много много.

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

← →
Sapersky (2011-01-13 18:56) [13]

Дык пишут же в [8]: всё уже придумано до нас и реализовано в FastMM. Мелкие блоки наращиваются агрессивно, [старый размер]*2 + N, большие экономно, на 25%. Видимо, это оптимальный баланс между скоростью и расходом памяти.

← →
Студент (2011-01-17 17:32) [14]

> Ваш код скорее всего неоптимален, так как можно существенно сократить ...

ам... Это как вы так перевывернули циклы?)
Спасибо, нужно будет над этим подумать...))

А вот ещё такое глупое уточнение... Допустим у меня динамический массив в локальных переменных процедуры/функции... Нужно ли перед выходом из функции делать SetLength(Mass, 0); ?

> А вот ещё такое глупое уточнение... Допустим у меня динамический
> массив в локальных переменных процедуры/функции... Нужно
> ли перед выходом из функции делать SetLength(Mass, 0); ?
>

Нет, так как об инициализации пустым значением и финализации динамических массивов (также как и строк) заботится компилятор.

> ам... Это как вы так перевывернули циклы?)
> Спасибо, нужно будет над этим подумать...))

Ну как-как, вы для каждого I из промежутка [0..Length(Masss)-1] искали равные ему "флаги" в массиве Arrr, создав на пустом месте квадратичную сложность. Гораздо более очевидное решение - для каждого элемента из Arrr сделать необходимые действия (в данном случае - добавление в массив) если его флаг лежит в указанном промежутке [0..Length(Masss)-1].

> Нужно ли перед выходом из функции делать SetLength(Mass,
> 0); ?

При выходе из области видимости массива память подчистится.

> подчистится.

щеткой ? :)

> Студент (17.01.2011 17:32:14) [14]

Нет, это автоматически контроллируемый компилятором тип, но если сделаешь,
то ничего страшного не будет.

Насколько я неправильно использую SetLength? Найти похожие ветки