Форум: "Основная";
Текущий архив: 2007.04.01;
Скачать: [xml.tar.bz2];
ВнизДинамические массивы 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 ...
Вы ошиблись, это константа для арктических пингвинов.
← →
GrayFace © (2007-02-04 22:59) [29]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
← →
Суслик © (2007-02-05 01:15) [30]Братцы с опытом, что вы такое говорите?
Почитайте 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
← →
Суслик © (2007-02-05 01:17) [31]Дин массив - указатель на массив, к которому применяется compiler magic.
Т.е. компилятор берет на себя управление выделенной памятью.
← →
Германн © (2007-02-05 01:23) [32]
> Суслик © (05.02.07 01:17) [31]
>
> Дин массив - указатель на массив, к которому применяется
> compiler magic.
> Т.е. компилятор берет на себя управление выделенной памятью.
>
И перераспределением выделенной памяти в рантайме тоже занимается компиллятор?
← →
Суслик © (2007-02-05 01:26) [33]Ну чо ты придираешься, будто удовольствие получаешь.
Один из завсегдатаев сморозил жуткую фигню.
Я возмутился. Что - нельзя?
-----
Если по сути вопроса, то, ответ "конечно" - именно компилятор вставляет вызовы методов управлению памяться, где это нужно.
← →
Суслик © (2007-02-05 01:29) [34]
> Desdechado © (31.01.07 15:18) [10]
> Врать не буду, но имхо не стоит особенно расчитывать на
> то, что новые элементы динамического массива располагаются
> последовательно и строго за старыми. Внутренняя реализация
> скорее напоминает список, в который помять может выделяться
> произвольными кусками в произвольных местах, что очень сильно
> зависит от фрагментации памяти и от работы менеджера памяти.
> А менеджеры у разных версий разные, а можно и вообще свои
> подключать.
О чем речь вообще - почитай доку - там четко сказано, что такое дин. массивы и как они хранятся. Это специфицировано и весьма четко. Доку я, кстати, привел.
← →
Desdechado © (2007-02-05 11:59) [35]Похоже, что я действительно фигню сморозил. Однако фразу из [12] повторю: "считаю, что нечего смешивать механизмы прямого доступа по адресу с нормальными языковыми конструкциями."
Такие вещи я делал и люблю делать на Си, но на паскале это, имхо, противоестественно. Не его это механизмы. Имхо.
ЗЫ Однако интересен вопрос с динамическими многомерными (разной размерности) массивами. Там-то как размерности в памяти лежат? В порядке объявления или в порядке выделения? Каждая размерность в произвольном месте памяти или таки в общем непрерывном куске? А то ведь при изменении размерности какого-нибудь серединного массива происходит ли перевыделение памяти на весь массив целиком?
Думаю, этих проблем достаточно, чтобы забить на динамические массивы и использовать списки. Имхо, они гораздо гибче, легче по ресурсам и понятнее. И там нет таких подводных камней, всё в руках твоих, а не спрятано в недрах компиляторных фишек.
← →
OSA © (2007-02-05 13:50) [36]
> 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, а если это не возможно, то списками.
← →
Leff © (2007-02-05 15:15) [37]> Т.е. всё же возможна сегментация !?
> Теперь не буду смешивать данные методы выделения и работы
> с памятью.
>
> ЗЫ. Теперь при возможности буду юзать GetMem, а если это
> не возможно, то списками.
Где в цитированном куске указано что возможна сегментация? Там как-раз говорится о том что данные хранятся последовательно и непрерывно в пределах одного динамического массива
Однако интересен вопрос с динамическими многомерными (разной размерности) массивами. Там-то как размерности в памяти лежат? В порядке объявления или в порядке выделения? Каждая размерность в произвольном месте памяти или таки в общем непрерывном куске?
многомерный динамический массив - это array of array of array ... of type, соответственно массив нулевого уровня храни указатели на массивы первого и т. д.
← →
Desdechado © (2007-02-05 15:23) [38]> соответственно массив нулевого уровня храни указатели на массивы первого и т. д.
Это и ежу понятно. Память по каким правилам под них выделяется?
← →
begin...end © (2007-02-05 15:56) [39]> 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. Но распределяет память динамически, но обращатся можно по элементам масива!
← →
Anatoly Podgoretsky © (2007-02-05 20:18) [41]> Desdechado (05.02.2007 11:59:35) [35]
Многомерных динамических массивов не бывает, бывает только array of type
Type может быть другим массивом.
Для удобства Борланд иммитирует многомерные массивы, но в отличии от не динамических, многомерный массив может быть не прямоугольным, вполне возможен такой массив
a
a b
a b c
Размещение памяти для любого массива последовательное. Каждый массив не зависим.
Остальные выводы сделаешь сам, на основе данной информации.
← →
Desdechado © (2007-02-06 11:50) [42]Anatoly Podgoretsky © (05.02.07 20:18) [41]
Спасибо, но вы повторяете begin...end © (05.02.07 15:56) [39].
Выводы я сделал. Остаюсь при своих приоритетах - TList forever.
← →
evvcom © (2007-02-06 12:05) [43]> [42] Desdechado © (06.02.07 11:50)
> forever
Слишком категорично. Ситуевины разные бывают. Иногда просто нет смысла из пушки по воробьям.
← →
Desdechado © (2007-02-06 12:31) [44]А если картечью? :)
ЗЫ каждому свое
← →
GrayFace © (2007-02-06 19:28) [45]Erik2 (05.02.07 17:38) [40]
Помоему всем уже не до вопроса. Как я понял основная проблема во втором варианте это излишнее выделение памяти. Это легко обойти, можно использовать тотже механизм, что и TList.
Если нужно активное расширение массива, то можно вообще обойтись без реаллокации. Правда, доступ к элементам чуть-чуть замедлится.
Страницы: 1 2 вся ветка
Форум: "Основная";
Текущий архив: 2007.04.01;
Скачать: [xml.tar.bz2];
Память: 0.59 MB
Время: 0.048 c