Про динамические массивы

← →
Blind Guardian (2008-02-08 18:50) [0]

Здравствуйте. Парочка вопросов о динамических массивах.

1) Вот в си шарп есть два таких понятия: multidimensional и jugged массивы. И те и те - могут быть многомерными, но в массивах первого типа все элементы одного уровня имеют одну длину. То есть, массив - это всегда, как бы, параллелепипед. У Jugged array же элементами могут быть массивы разной длины. В хелпе ясно сказано, что jugged работают медленнее, чем multidimensional. В Дельфи же все многомерные динамические массивы могут иметь в качестве элементов массивы с разными длинами. Можно ли утверждать, что в дельфи динамический массив-параллелепипед работает медленнее, чем мог бы?

2) В программе у меня циклически выделяется по одному элементу для динамического массива (setLength(ar,n+1); inc(n);) Но программа будет работать намного быстрее, если я буду выделять память блоками, а по окончании выделения обрежу ненужный хвост. Вопросы: можно ли с помощью каких нибудь директив компилятору заставить его автоматически выделять память блоками? Блоки из скольки элементов рациональнее добавлять?

← →
ketmar © (2008-02-08 18:53) [1]

хотел трактат написать, но пиво кончилось. вкратце:
1. фигня.
2. фигня.

---
Understanding is not required. Only obedience.

← →
clickmaker © (2008-02-08 18:55) [2]

> можно ли с помощью каких нибудь директив компилятору заставить
> его автоматически выделять память блоками?

нет.
Но можно себя заставить написать AllocMem или юзать более удобные хранилища, такие как List, например. Там оно уже прикручено. Capacity и все такое

← →
Palladin © (2008-02-08 18:58) [3]

когда то я писал класс работы с безмерно многомерными массивами...
1. бред
2. посыл не бред, но директива бред
пиво только началось...

← →
ketmar © (2008-02-08 18:59) [4]

Удалено модератором

← →
Palladin © (2008-02-08 19:32) [5]

йогурта чтоли? :)

← →
Anatoly Podgoretsky © (2008-02-08 19:34) [6]

1. не верно
2. в общем неверно, в частном верно.

← →
Джо © (2008-02-08 19:51) [7]

Удалено модератором

← →
clickmaker © (2008-02-08 19:57) [8]

> Blind Guardian (08.02.08 18:50)

кстати. Чего рекомендуешь дунуть, чтобы массив представился параллелипипедом? Или тут грибочки, как минимум, нужны? o)

← →
Anatoly Podgoretsky © (2008-02-08 20:03) [9]

> clickmaker (08.02.2008 19:57:08) [8]

Паралепипед, частный случай кривого массива.

← →
clickmaker © (2008-02-08 20:05) [10]

> [9] Anatoly Podgoretsky © (08.02.08 20:03)

кривого, в смысле плохо заполненного?

← →
Palladin © (2008-02-08 20:05) [11]

> [7] Джо © (08.02.08 19:51)

нажраться всем формумом - это будет исторический момент...

← →
Palladin © (2008-02-08 20:06) [12]

> [10] clickmaker © (08.02.08 20:05)

это в смысле массив должен жить в трех измерениях, два измерения у него должны быть одинаковым, а одно разным или тоже одинаковым

← →
Anatoly Podgoretsky © (2008-02-08 20:09) [13]

> clickmaker (08.02.2008 20:05:10) [10]

В смысле не паралелипипед, а кривулина.

← →
clickmaker © (2008-02-08 20:10) [14]

> а одно разным или тоже одинаковым

трехмерный, да еще и кривой массив?
слава Аллаху, у меня в проектах такого нет... o)

← →
Anatoly Podgoretsky © (2008-02-08 20:11) [15]

> clickmaker (08.02.2008 20:10:14) [14]

Это еж какой то получается, а не массив

← →
DiamondShark © (2008-02-08 20:19) [16]

> Можно ли утверждать, что в дельфи динамический массив-параллелепипед
> работает медленнее, чем мог бы?

А CPU Window на что дадено?
var StatArr: array[0..10, 0..10] of integer; DynArr: array of array of integer; ... var q: integer; i, j: integer; ... q := StatArr[5, 5]; mov eax,[StatArr + $F0] Умный компилятор заранее посчитал смещение DynArr[5, 5] := q; mov ebx,[DynArr] Тоже всё весьма лаконично, ничего лишнего mov ebx,[ebx+$14] mov [ebx+$14],eax ... q := StatArr[i, j]; imul eax,edx,$0b lea eax,[eax*4+StatArr] mov eax,[eax+ecx*4] DynArr[i, j] := q; mov ebx,[DynArr] mov edx,[ebx+edx*4] mov [edx+ecx*4],eax

Вывод:
- в случае константных индексов статический массив быстрее (очень немножко)
- в случае переменных индексов... хм... Хэнк его знает, я по тактам не считал. Вообще-то, тут требуется промежуточный доступ к памяти за указателем на второе измерение. Если включить извращённую фантазию, и представить, что страница с нужным куском первого измерения откачана, то, вообще говоря, доступ может потребовать неопределённо большого времени. Но, с другой стороны, кусок статического массива тоже может быть откачан ;)

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

← →
DiamondShark © (2008-02-08 20:28) [17]

> clickmaker © (08.02.08 19:57) [8]
>
> кстати. Чего рекомендуешь дунуть, чтобы массив представился
> параллелипипедом? Или тут грибочки, как минимум, нужны?
> o)

Не, параллелипипедом -- это на и на трезвую (но немножко распаренную) голову можно. А вот тором представить, или бутылкой Клейна -- тут без синтетиков не обойтись.

← →
AlexWlad © (2008-02-08 21:36) [18]

> Anatoly Podgoretsky © (08.02.08 20:03) [9]
>
> > clickmaker (08.02.2008 19:57:08) [8]
>
> Паралепипед, частный случай кривого массива.

Эта-пять... маладец...

Кстати обратное тоже справедливо...

Удалено модератором

← →
Blind Guardian (2008-02-08 22:06) [23]

1. Jagged и multidimensional
http://www.mycode.ws/index.php?elif=ucsharp/arrays.aspx.htm
В C Sharp имеется три основных типа массивов: одномерные, многомерные и неровные(jagged)
...
Неровные (jagged) массивы - это, по сути, массивы массивов.
...
Отметим, что многомерные массивы являются важным отличием от других подобных языков (Java), ибо по сравнению с неровными массивами, обеспечивают гораздо большую производительность.

2.
Программа показывает, за какое время выделаются 10000000 байт по одному, и за сколько - по 1000.

program Project2; {$APPTYPE CONSOLE} uses SysUtils; const c=10000000; block=1000; var i1,n1,n2:integer; ar:array of byte; d1:double; begin n1:=0; d1:=gettime; //Выделяем по 1 элементу for i1:=1 to c do begin inc(n1); setLength(ar,n1); end; writeln(gettime-d1:0:15); n1:=0; n2:=0; setLength(ar,0); d1:=gettime; //Выделяем блоками for i1:=1 to c do begin inc(n1); if n1>n2 then begin inc(n2,block); setLength(ar,n2); end; end; setLength(ar,n1); writeln(gettime-d1:0:15); readln; end.
У меня эта программа вывела следующее:
0.000030555555556 0.000000914351852
Выигрыш во времени примерно в 33 раза.

← →
Blind Guardian (2008-02-08 22:21) [24]

и в чем я не прав?...

в том что ты решил что неправ

← →
Sapersky (2008-02-09 19:17) [26]

1.
q := StatArr[i, j];
imul eax,edx,$0b
lea eax,[eax*4+StatArr]
mov eax,[eax+ecx*4]

DynArr[i, j] := q;
mov ebx,[DynArr]
mov edx,[ebx+edx*4]
mov [edx+ecx*4],eax

А если "в условиях, приближенных к боевым":

For i:=0 to 9 do
For j:=0 to 9 do
StatArr[i, j] := q;

For i:=0 to 9 do
For j:=0 to 9 do
DynArr[i, j] := q;

... то разница есть, в случае статического массива компилятор использует инкремент указателя, в случае динамического - на каждой итерации заново рассчитывает адрес элемента.
Т.е. - да, динамический должен быть медленнее, хотя на сколько конкретно - не замерял.
В качестве альтернативы можно использовать "двумерный массив-указатель", по аналогии со свойством Pixels из библиотеки FastLIB:

Type
PArray =^TArray;
TArray = array[0..0] of Integer;
PArr2D =^TArr2D;
TArr2D = array[0..0]of PArray;
Var DynArr2 : PArr2D;
GetMem(DynArr2, 10 * 10 * SizeOf(Integer));
For i:=0 to 9 do
For j:=0 to 9 do
DynArr2[j, i] := q; // внимание! индексы пишутся в обратном порядке!
FreeMem(DynArr2);

Впрочем, компилятор и здесь считает адрес на каждой итерации - получается всего на одну команду меньше, чем с дин. массивом, за счёт более простой структуры (данные выделяются "одним куском"; наверное, так же устроен и multidimensional из C#).
Вывод - если всерьёз боремся за скорость, нужно вручную расписывать цикл на указателях (что, собственно, и делается в той же FastLIB).

2.
Да, выделять блоками - быстрее. Для D7 и более ранних к тому же уменьшает фрагментацию, которая при использовании SetLength(Length+1) может привести к преждевременному out of memory. Здесь:
http://sapersky.narod.ru/files/Arrays.rar
пример работы с дин. массивом в стиле TList - Length(Array) играет роль Capacity, реальная длина хранится в отдельной переменной. При "росте" массива выделяется в два раза больше, чем было, что может показаться несколько расточительным, зато минимизирует кол-во перевыделений (помнится, Джоэл Спольски именно так и рекомендовал делать, правда, применительно к менеджеру памяти Windows, не дельфийскому). Если нужна экономия - можно использовать алгоритм аналогичный TList.Grow.

Про динамические массивы Найти похожие ветки