Динамические массивы vs Статические массивы

← →
SH@RK © (2007-01-31 12:47) [0]

Существуют алгоритмы, память для работы которых выделяется во время их работы. Т.е. заранее неизвестен размер массива, с которым работает алгоритм.

Пример:
type TNode = packed record Child: packed array [0..31] of Word; Parent: Word; Final: LongBool; end; PArrNode = packed array of TNode; var Node: PArrNode; // динамич. массив

1)
В ходе выполнения алгоритма выделяю память кусками (по мере неоходимости):
Len := Length(Node); SetLength(Node, Len + 100);

Я полагаю, что при этом элементы массива Node2^ располагаются в виртуальной памяти последовательно. Поэтому я допускаю работу с этим массивом как со статическим:
.... type PArrNodeSt = ^TArrNodeSt; TArrNodeSt = packed array [0..0] of TNode; .... PArrNodeSt(Node)^[i] := ....
Вообще это дупустимо?

2)
Когда во внешней программе просчитывается этот алгоритм, то в файл с данными я записываю и кол-во элементов массива.
Поэтому в основной программе я выделяю память под этот массив при помощи GetMem (юзаю FastMM4).
Но при чтении этого массива как динамического (x := Node[i]), иногда возникают ошибки. Ошибки происходят в ф-ии модуля System @DynArrayClear (@FreeMem).
Как это понимать? При обычном чтении динамического массива происходит обращение к ф-иям выделения/освобождения памяти?

Теперь при любом методе выделения памяти под массив работаю с ним как со статическим массивом. Это допустимо?

← →
MBo © (2007-01-31 13:02) [1]

packed array - packed не нужно, массивы всегда упакованы

А зачем приводить динамический массив к статическому типу, если синтаксис работы с ним никак не отличается?

← →
Сергей М. © (2007-01-31 13:05) [2]

Переменная типа дин.массив есть суть указатель на управляющую структуру этого массива, а не на собственно данные, хранимые массивом.

← →
GrayFace © (2007-01-31 13:06) [3]

Все допустимо, но не понятно, чем SetLength не устроил.

← →
SH@RK © (2007-01-31 13:17) [4]

Хотелось бы узнать чем отличаются динамические от статических массивов. Я не чётко понимаю работу с динамическими массивами. Как под них выделяется память?
Одинаково ли интерпретирует компилятор эти строки:
x := Node[i].Child[j] ; x := PArrNodeSt(Node)^[i].Child[j];

← →
DevilDevil © (2007-01-31 13:24) [5]

Так наверное правильнее:

x := Node[i].Child[j] ; x := PArrNodeSt(@Node[0])^[i].Child[j];

← →
SH@RK © (2007-01-31 13:26) [6]

точно подмечено =)
сорри

← →
Сергей М. © (2007-01-31 13:28) [7]

> чем отличаются динамические от статических массивов

Динамические придуманы для лентяев и батонокидателей)

← →
SH@RK © (2007-01-31 13:50) [8]

Т.е. , как я понял, ошибка @DynArrayClear возникала из-за того что не была сформирована управляющая структура массива !?

← →
Сергей М. © (2007-01-31 14:10) [9]

> SH@RK © (31.01.07 13:50) [8]

Угу. Либо загажена.

Чем списки-от не угодили ?

← →
Desdechado © (2007-01-31 15:18) [10]

Врать не буду, но имхо не стоит особенно расчитывать на то, что новые элементы динамического массива располагаются последовательно и строго за старыми. Внутренняя реализация скорее напоминает список, в который помять может выделяться произвольными кусками в произвольных местах, что очень сильно зависит от фрагментации памяти и от работы менеджера памяти. А менеджеры у разных версий разные, а можно и вообще свои подключать.

← →
Сергей М. © (2007-01-31 15:25) [11]

> Desdechado © (31.01.07 15:18) [10]

> Врать не буду

Но тем не менее врешь)

← →
Desdechado © (2007-01-31 15:41) [12]

> Но тем не менее врешь)
Возможно. Но хотелось бы узнать, в чем именно. Желательно со ссылкой на документацию.

ЗЫ Я в этих тонкостях детально не разбирался, т.к. считаю, что нечего смешивать механизмы прямого доступа по адресу с нормальными языковыми конструкциями.

← →
evvcom © (2007-01-31 15:42) [13]

> [7] Сергей М. © (31.01.07 13:28)
> Динамические придуманы для лентяев и батонокидателей)

Значит я лентяй или батонокидатель или и то, и другое :)
Хотя нет. Я могу и со статическими типа управиться. Значит только лентяй :)

> [10] Desdechado © (31.01.07 15:18)
> но имхо не стоит особенно расчитывать

Фиг знает. Это надо доки смотреть. Но думаю, можно.

> что новые элементы динамического массива располагаются последовательно
> и строго за старыми

До D7 включительно именно так и располагаются.

> Внутренняя реализация скорее напоминает список, в который
> помять может выделяться произвольными кусками в произвольных
> местах

По D7 не так.

← →
SH@RK © (2007-01-31 15:44) [14]

Первоначальный вариант алгоритма работал вот с такой структурой:
type PNode = ^TNode; TNode = record Child: array [0..255] of PNode; Parent: PNode; Final: LongBool; end;
В каждом элементе имеются ссылки на другие элементы.
Память под каждый элемент выделялась при помощи New.
Но эта реализация много памяти жрёт.
Вот и приходится думать как всё это дело оптимизировать.

ЗЫ. Ну не знаю я как заранее просчитать кол-во элементов автомата Ахо-Корасик.

← →
Сергей М. © (2007-01-31 15:52) [15]

> не знаю я как заранее просчитать кол-во элементов автомата
> Ахо-Корасик.
>

А причем здесь это ?

Речь-то идет о перераспределении памяти на момент когда требуется добавить элемент(ы) ... А к карасик там или не карасик потребовал от тебя это - совершенно не важно ...

← →
jack128 © (2007-01-31 15:59) [16]

Сергей М. © (31.01.07 13:05) [2]
Переменная типа дин.массив есть суть указатель на управляющую структуру этого массива, а не на собственно данные, хранимые массивом.
не-а. "управляющая структура" находится по отрицательному смещению от указателя. Так же как и длинных строках. Собственно длинные строки - частный случай дин массивов.

← →
Anatoly Podgoretsky © (2007-01-31 16:00) [17]

> SH@RK (31.01.2007 12:47:00) [0]

Справка: Do not apply the dereference operator (^) to a dynamic-array variable

← →
Amoeba © (2007-01-31 16:07) [18]

> Desdechado © (31.01.07 15:18) [10]
>
> Врать не буду, но имхо не стоит особенно расчитывать на
> то, что новые элементы динамического массива располагаются
> последовательно и строго за старыми. Внутренняя реализация
> скорее напоминает список, в который помять может выделяться
> произвольными кусками в произвольных местах, что очень сильно
> зависит от фрагментации памяти и от работы менеджера памяти.
> А менеджеры у разных версий разные, а можно и вообще свои
> подключать.
>

Определенно врешь!

← →
Сергей М. © (2007-01-31 16:11) [19]

> jack128 © (31.01.07 15:59) [16]

Ну если это принципиально, то да.

Просто компилятор не позволит сделать приведение типа а-ля

PMyType(MyDynArray)[someindex]

← →
Джо © (2007-01-31 16:21) [20]

Автору по поводу SetLength. По возможности, следует избегать, как чумы, частого вызова SetLength. Что для длинных строк, что для дин. массивов. То есть, эти вызовы нужно сводить к наименьшему возможному количеству, в идеале — к одному. Дабы избежать дорогостоящего перераспределения памяти, к которому эти вызовы могут приводить.

← →
SH@RK © (2007-01-31 16:24) [21]

При использовании в D7+FastMM4 динамического массива память для него выделяется последовательно. Во всяком случае у меня 6 мегабайтный массив именно так расположился =)

Всё. Нафиг эти дин. массивы. Сделаю два варианта модуля:
1) с отдельным выделением памяти под элемент (New);
2) с глобальным выделением памяти под все элементы (GetMem);

Всё равно данные подготавливаются в отдельном приложении (там буду юзать 1 модуль), в котором узнаю число элементов.
А в главной прожке буду работать со 2 модулем, благо в данных уже содержится кол-во элементов (что бы память экономилась).

← →
Джо © (2007-01-31 16:28) [22]

> [21] SH@RK © (31.01.07 16:24)
> При использовании в D7+FastMM4 динамического массива память
> для него выделяется последовательно.
Дык, она всегда будет выделяться последовательно. Потому и многократный вызов SetLength — крайне опасная штука.
По поводу остального — никак не могу понять, чем динамические массивы не угодили? :)
Если же задача такова, что приходится часто добавлять-удалять элементы, то лучший выбор — списки. Во многих случаях хватит стандартного класса TList.

← →
OSA © (2007-01-31 16:41) [23]

> Дык, она всегда будет выделяться последовательно. Потому
> и многократный вызов SetLength — крайне опасная штука.
> По поводу остального — никак не могу понять, чем динамические
> массивы не угодили? :)
> Если же задача такова, что приходится часто добавлять-удалять
> элементы, то лучший выбор — списки. Во многих случаях хватит
> стандартного класса TList.

Поробую объяснить научно-популярно.

Первый способ как раз и использует TList. Но в этом способе памяти требуется в 2 раза больше, т.к. каждая ссылка на элемент дерева Ахо-Корасик представляет собой Pointer.

Второй способ использует относительные ссылки на элементы в виде Word.

ЗЫ. Уже всё сделал и протестировал.

← →
jack128 © (2007-02-01 00:35) [24]

Сергей М. © (31.01.07 16:11) [19]
Просто компилятор не позволит сделать приведение типа а-ля

PMyType(MyDynArray)[someindex]

Почему не позволит?? Дин массив - суть указатель. Так тчо его можно привести к любому "указательному" типу.

type TDynIntegerArray = array of Integer; TStaticIntegerArray = array[0..MaxInt div SizeOf(Integer) - 1] of Integer; PStaticIntegerArray = ^TStaticIntegerArray; procedure TForm9.FormCreate(Sender: TObject); var Arr: TDynIntegerArray; begin SetLength(Arr, 1); PStaticIntegerArray(Arr)[0] := 10; Caption := IntToStr(Arr[0]) end;

Или я что то не так понял?

SH@RK © (31.01.07 16:24) [21]
Всё. Нафиг эти дин. массивы. Сделаю два варианта модуля:
1) с отдельным выделением памяти под элемент (New);
2) с глобальным выделением памяти под все элементы (GetMem);
Почему нафиг?? С New/GetMem - гораздо больше ошибок огребешь, чем с дин массивами

← →
Desdechado © (2007-02-01 11:18) [25]

Amoeba © (31.01.07 16:07) [18]
Еще один. Читай Desdechado © (31.01.07 15:41) [12]

← →
umbra © (2007-02-01 12:15) [26]

> Я не чётко понимаю работу с динамическими массивами. Как
> под них выделяется память?

http://www.rsdn.ru/?article/Delphi/dynarrays.xml

← →
reonid © (2007-02-01 12:47) [27]

2SH@RK © (31.01.07 16:24) [21]
>При использовании в D7+FastMM4 динамического массива память для него >выделяется последовательно.

Для гренландских голубых китов коэффициент Пи обычно считается равным 3.1416 ...

← →
Джо © (2007-02-01 14:26) [28]

> [27] reonid © (01.02.07 12:47)
> 2SH@RK © (31.01.07 16:24) [21]
> >При использовании в D7+FastMM4 динамического массива память
> для него >выделяется последовательно.
>
> Для гренландских голубых китов коэффициент Пи обычно считается
> равным 3.1416 ...

Вы ошиблись, это константа для арктических пингвинов.

DevilDevil © (31.01.07 13:24) [5]
Так наверное правильнее:
Без разницы.

Сергей М. © (31.01.07 13:28) [7]
Динамические придуманы для лентяев и батонокидателей)
Зря ты смайлик не дорисовал, а то ведь поверить могут. :)

evvcom © (31.01.07 15:42) [13]
До D7 включительно именно так и располагаются.
Хоть я и не смотрел D8-D2006, но после D7 это тоже наверняка так.

jack128 © (01.02.07 0:35) [24]
Почему нафиг?? С New/GetMem - гораздо больше ошибок огребешь, чем с дин массивами
+1

Братцы с опытом, что вы такое говорите?
Почитайте memory manegement в хелпе.
В крайнем случае CPU посмотрите.

Что стало модно такие ответы давать. Вот для справки "лентяям":

Dynamic Array Types
On the Win32 platform, a dynamic-array variable occupies four bytes of memory which contain a pointer to the dynamically allocated array. When the variable is empty (uninitialized) or holds a zero-length array, the pointer is nil and no dynamic memory is associated with the variable. For a nonempty array, the variable points to a dynamically allocated block of memory that contains the array in addition to a 32-bit length indicator and a 32-bit reference count. The table below shows the layout of a dynamic-array memory block.
Dynamic array memory layout (Win32 only) Offset Contents
-8
32-bit reference-count

-4
32-bit length indicator (number of elements)

0..Length * (size of element) -1
array elements

Дин массив - указатель на массив, к которому применяется compiler magic.
Т.е. компилятор берет на себя управление выделенной памятью.

> Суслик © (05.02.07 01:17) [31]
>
> Дин массив - указатель на массив, к которому применяется
> compiler magic.
> Т.е. компилятор берет на себя управление выделенной памятью.
>

И перераспределением выделенной памяти в рантайме тоже занимается компиллятор?

Ну чо ты придираешься, будто удовольствие получаешь.
Один из завсегдатаев сморозил жуткую фигню.
Я возмутился. Что - нельзя?
-----
Если по сути вопроса, то, ответ "конечно" - именно компилятор вставляет вызовы методов управлению памяться, где это нужно.

> Desdechado © (31.01.07 15:18) [10]
> Врать не буду, но имхо не стоит особенно расчитывать на
> то, что новые элементы динамического массива располагаются
> последовательно и строго за старыми. Внутренняя реализация
> скорее напоминает список, в который помять может выделяться
> произвольными кусками в произвольных местах, что очень сильно
> зависит от фрагментации памяти и от работы менеджера памяти.
> А менеджеры у разных версий разные, а можно и вообще свои
> подключать.

О чем речь вообще - почитай доку - там четко сказано, что такое дин. массивы и как они хранятся. Это специфицировано и весьма четко. Доку я, кстати, привел.

Похоже, что я действительно фигню сморозил. Однако фразу из [12] повторю: "считаю, что нечего смешивать механизмы прямого доступа по адресу с нормальными языковыми конструкциями."
Такие вещи я делал и люблю делать на Си, но на паскале это, имхо, противоестественно. Не его это механизмы. Имхо.

ЗЫ Однако интересен вопрос с динамическими многомерными (разной размерности) массивами. Там-то как размерности в памяти лежат? В порядке объявления или в порядке выделения? Каждая размерность в произвольном месте памяти или таки в общем непрерывном куске? А то ведь при изменении размерности какого-нибудь серединного массива происходит ли перевыделение памяти на весь массив целиком?
Думаю, этих проблем достаточно, чтобы забить на динамические массивы и использовать списки. Имхо, они гораздо гибче, легче по ресурсам и понятнее. И там нет таких подводных камней, всё в руках твоих, а не спрятано в недрах компиляторных фишек.

> Dynamic Array Types
> On the Win32 platform, a dynamic-array variable occupies
> four bytes of memory which contain a pointer to the dynamically
> allocated array. When the variable is empty (uninitialized)
> or holds a zero-length array, the pointer is nil and no
> dynamic memory is associated with the variable. For a nonempty
> array, the variable points to a dynamically allocated block
> of memory that contains the array in addition to a 32-bit
> length indicator and a 32-bit reference count. The table
> below shows the layout of a dynamic-array memory block.
> Dynamic array memory layout (Win32 only) Offset Contents
>
> -8
> 32-bit reference-count
>
> -4
> 32-bit length indicator (number of elements)
>
> 0..Length * (size of element) -1
> array elements

Т.е. всё же возможна сегментация !?
Теперь не буду смешивать данные методы выделения и работы с памятью.

ЗЫ. Теперь при возможности буду юзать GetMem, а если это не возможно, то списками.

> Т.е. всё же возможна сегментация !?
> Теперь не буду смешивать данные методы выделения и работы
> с памятью.
>
> ЗЫ. Теперь при возможности буду юзать GetMem, а если это
> не возможно, то списками.

Где в цитированном куске указано что возможна сегментация? Там как-раз говорится о том что данные хранятся последовательно и непрерывно в пределах одного динамического массива

Однако интересен вопрос с динамическими многомерными (разной размерности) массивами. Там-то как размерности в памяти лежат? В порядке объявления или в порядке выделения? Каждая размерность в произвольном месте памяти или таки в общем непрерывном куске?

многомерный динамический массив - это array of array of array ... of type, соответственно массив нулевого уровня храни указатели на массивы первого и т. д.

> соответственно массив нулевого уровня храни указатели на массивы первого и т. д.
Это и ежу понятно. Память по каким правилам под них выделяется?

> Desdechado © (05.02.07 15:23) [38]

В случае многомерных динамических массивов для каждого array of array (массива указателей на тела вложенных массивов) и для каждого array of TSomeType (массива максимальной вложенности) будут выделены непрерывные блоки памяти.

Например, вызвав SetLength(A, 2, 2) для A: array of array of Integer, получим 3 независимо выделенных блока памяти: один -- для массива A, который содержит два указателя, и два -- для тел вложенных массивов A[0] и A[1].

← →
Erik2 (2007-02-05 17:38) [40]

To SH@RK
Помоему всем уже не до вопроса. Как я понял основная проблема во втором варианте это излишнее выделение памяти. Это легко обойти, можно использовать тотже механизм, что и TList. Но распределяет память динамически, но обращатся можно по элементам масива!

Динамические массивы vs Статические массивы Найти похожие ветки