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

← →
Михаил (2004-04-29 00:25) [0]

Всем привет! вопрос собственно в создании сабжа.
допустим нужен двухмерный динамический массив... как это сделать, помогите плиз, очень нужно. я пока пользуюсь просто массивом одномерных массивов и рулю ими с помошью setlength =)
но ведь можно же сделать это "по-людски"! подскажите плиз!

← →
kat (2004-04-29 01:28) [1]

var a:array of array of integer;
setlength(a,1000);
for i:=0 to 999 do
setlength(a[i],1000);

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

← →
Юрий Зотов © (2004-04-29 02:35) [2]

F1 - "Multidimensional dynamic arrays". С примером.

← →
Михаил (2004-04-29 09:05) [3]

спасибо огромное!

kat>> по хелпу посмотреть как-то даже и не догадался =) буду знать сенк =)

← →
Рамиль © (2004-04-29 09:16) [4]

> kat (29.04.04 01:28) [1]

Зачем такая то конструкция?!.
Достаточно
setlength(a, 1000, 1000);

← →
Igorek © (2004-04-29 09:38) [5]

F1 конечно круто.
Но имхо для глубокого понимания сути сабжа важно разобраться с указателями и на них самому построить динам. многом. массив.

← →
Sha © (2004-04-29 10:07) [6]

Igorek © (29.04.04 09:38) [5]

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

Михаил (29.04.04 00:25)

Поэтому если умеешь работать с одномерным массивом указателей и с одномерным массивом массивом данных по отдельности, то должен легко представить себе, как можно было бы сэмулировать многомерный массив. Именно это тебе и предлагает Борланд.

← →
Goida © (2004-04-29 10:15) [7]

> Sha
> у Борланда вообще нет многомерных динамческих массивов. Они только эмулирутся при помощи динамического массива указателей на одномерные динамические массивы.

В таком случае: А есть ли тогда хоть в каком-то языке динамические многомерные массивы? ;-J

← →
Sha © (2004-04-29 10:25) [8]

Goida © (29.04.04 10:15) [7]

Да, есть. Например, в PL/1 есть локальные в пределах процедуры динамические массивы. Пример начала процедуры (за синтаксис не отвечаю, давно это было):

procedure SomeProc(m, n: integer); integer a(m,n); begin;

Здесь важно то, что в момент входа в процедуру под массив а(m,n) отводится вся необходимая память размером m*n целых. И никаких указателей, и матрица всегда прямоугольная.

← →
Ega23 © (2004-04-29 10:26) [9]

Sha © (29.04.04 10:25) [8]

Но "в кишках" это же всё равно одномерный массив с длиной n*m

← →
Sha © (2004-04-29 10:35) [10]

Ega23 © (29.04.04 10:26) [9]

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

← →
Goida © (2004-04-29 10:39) [11]

> Sha

У тебя есть док-ва, что у Борланда эмулируется именно "не подлинный"?

← →
Ega23 © (2004-04-29 10:39) [12]

Указатели, указатели и ещё раз указатели. GetMem, New, FreeMem, Dispose.

← →
Alex44 (2004-04-29 10:43) [13]

A pravil"nej (i bystree), navernoe, budet sdelat" odnomernyj,
SetLength(, n*m), i pereschityvat" indexy.

← →
Goida © (2004-04-29 10:45) [14]

> Alex44

Правильней так, как этого требует поставленная задача.

← →
Sha © (2004-04-29 10:50) [15]

Goida © (29.04.04 10:39) [11]

Не только у меня, они есть и у тебя, и у Борланда :)

Посмотри пример Юрий Зотов © (29.04.04 02:35) [2]. Как ты думаешь, почему в этом примере именно так устнавливается длина второго измерения?

← →
Sha © (2004-04-29 10:58) [16]

Alex44 (29.04.04 10:43) [13]

Этот метод примерно равноценен Борландовскому при малых размерах и чуть быстрее при больших. Но он может значительно проигрывать при попытках изменения внутренних размерностей.

← →
Igorek © (2004-04-29 11:02) [17]

> Sha © (29.04.04 10:35) [10] Впрочем, можно сэмулировать и
> "подлинный" многомерный массив.
...
> и матрица всегда прямоугольная.

Можно узнать как такое возможно? ;-)))

← →
Goida © (2004-04-29 11:09) [18]

> Sha

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

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

← →
Sha © (2004-04-29 11:11) [19]

> Igorek © (29.04.04 11:02) [17]
>> Sha © (29.04.04 10:35) [10] Впрочем, можно сэмулировать и
>> "подлинный" многомерный массив.
>> и матрица всегда прямоугольная.

> Можно узнать как такое возможно? ;-)))

Здесь имелось ввиду фиксированное в design time количество размерностей.
В этом случае, вроде, все очевидно. Для матриц:
- отводим память m * n * SizeOf(TElement).
- пишем Get(i,j), Put(i,j) для пересчета индексов.

← →
Sha © (2004-04-29 11:13) [20]

> Goida © (29.04.04 11:09) [18]
> Во-первых, в этом примере ни слова о машинной реализации. И мы
> можем только догадываться, что там на самом деле происходит.
> Попробуй смотреть беспристрастно.

Попробуй смотреть в CPU window :)

> Во-вторых, есть только два способа организовать динамические
> многомерные массивы: связанные списки или перемещение блоков
> памяти и выстраивание элементов в цепочку.

Я знаю гораздо больше :)
Посмотри, например, Sha © (29.04.04 11:11) [19]

← →
Goida © (2004-04-29 11:20) [21]

> Sha

Если ты в CPU сам видел организацию, то вопрос вообще отпадает.
Но что смотреть в > Sha © (29.04.04 11:11) [19]? Там что-то новое написано? Как было два, так и осталось - два способа.

← →
Sha © (2004-04-29 11:26) [22]

Goida © (29.04.04 11:20) [21]

Да, точно. Третий вариант реализован, например, в Борланд (без связных списков :))

← →
Goida © (2004-04-29 11:33) [23]

> Sha

Без списков - такого не бывает. Тебе все равно где-то необходимо хранить адрес ячеек.

← →
Sha © (2004-04-29 11:39) [24]

Goida © (29.04.04 11:33) [23]

Борланд для этого использует массив адресов ячеек.

← →
Goida © (2004-04-29 11:45) [25]

> Sha

А как же он меняет кол-во элементов массива адрессов ячеек???

← →
Sha © (2004-04-29 11:47) [26]

Способ #4: хранить данные, разделяя их маркерами начала элемента и начала размерностей (как в Advanced Revelation).
Способ #5: хранить положение и тип маркеров в отдельном массиве.
Способ #6: другой взгляд на массив: ведь, если задуматься, что такое "элемент a[i,j]"? - это "переменная с именем a[i,j]". Достаточно разрешить переменные с такими именами и придумать правила работы с ними (как в REXX).
Есть и другие способы, описанные в умных книжках о структурах данных.

А вообще есть только один способ организовать динамические
многомерные массивы: хранить данные в памяти :))

← →
Sha © (2004-04-29 11:48) [27]

Goida © (29.04.04 11:45) [25]

SetLength :)

← →
Goida © (2004-04-29 11:54) [28]

> Sha

Всё с тобой ясно. Ты явно незнаешь организацию памяти. Или прикидываешься таковым. Изучай ассемблер.
Все, о чем ты только что сказал - перемещение блоков памяти и выстраивание элементов в цепочку (только по разному оформленного). Суть неизменна.

← →
Sha © (2004-04-29 11:56) [29]

Goida © (29.04.04 11:54) [28]

Hу, ну :)))))))

← →
Goida © (2004-04-29 11:58) [30]

> Hу, ну

Хороший аргумент :-,

← →
Johnmen © (2004-04-29 12:00) [31]

>Sha ©

Не спорь с ламерами. Которые, кстати, сами не знают с кем и о чём спорят...

← →
Sha © (2004-04-29 12:01) [32]

Goida © (29.04.04 11:58) [30]

Более доступно. Понимание приходит с опытом. Не все женщины одинаковы.

← →
Goida © (2004-04-29 12:05) [33]

> Johnmen

Где аргументы. Словами в воздух и могу кидаться. Но что за ними стоит. Я не пытаюсь переубедить вас, а хочу понять сам. Но пока нет оснований отрекаться от того, что сказал я: либо ты распологаешь все линейно в памити, либо связываешь ячейки памяти (каким угодно способом). Другого не дано. Я не прав? Почему? Где объяснения. А то чем вы занимаетесь, это бравадство...

← →
Goida © (2004-04-29 12:35) [34]

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

← →
Sha © (2004-04-29 12:48) [35]

Видишь ли, Goida. Все элементы массива - связанная по смыслу совокупность данных. Хранить ее, никак не связывая, невозможно.
Последовательное расположение элементов в памяти - это тоже один из способов связывания элементов.
С этой точки зрения существует всего лишь один способ хранения - связанное хранение элементов массива.
Вопрос в том, как именно это связанное хранение организовано. Именно на низком уровне. Все перечисленные способы этим и отличаются друг от друга. От этого завивисит их эффективность и пригодность в том или ином случае.
Ты просто не заметил этого. Бывает.

← →
Goida © (2004-04-29 12:59) [36]

> Sha

Спасибо. Теперь я понял, с какой позиции вы смотрите. Я с вами согласен.

← →
Anatoly Podgoretsky © (2004-04-29 14:35) [37]

Sha © (29.04.04 10:07) [6]
Я бы больше сказал. Важно понять, что у Борланда вообще нет многомерных динамческих массивов. Они только эмулирутся при помощи динамического массива указателей на одномерные динамические массивы.

И даже это не совсем абстрактно,
Можно посмотреть по другому

1. У Борланда динамический массив является указателем с автоматичеким управлением памятью и поддержкой расчета индексов на уровне язиыка.
Определение array of type, если type является динамическим мвссивов, то вступает определение об указателе, и так далее по уровням. Язык обеспечит управление память и доступ к ячейкам по индексу.

← →
Igorek © (2004-04-29 15:37) [38]

> Здесь имелось ввиду фиксированное в design time количество
> размерностей.
> В этом случае, вроде, все очевидно. Для матриц:
> - отводим память m * n * SizeOf(TElement).
> - пишем Get(i,j), Put(i,j) для пересчета индексов.

Надеюсь ты имеешь ввиду динамический массив. В моем понимании таковым является массив в котором размерности при написании кода неизвестны.

← →
WebErr © (2004-04-29 15:41) [39]

> Anatoly Podgoretsky © (29.04.04 14:35) [37]

Я бы даже сказал, что многомерных массивов вообще не существует в машинной логике, это всё "эмуляция" одномерного массива. ;)

← →
Sha © (2004-04-29 15:51) [40]

> Igorek © (29.04.04 15:37) [38]

> Надеюсь ты имеешь ввиду динамический массив. В моем понимании
> таковым является массив в котором размерности при написании
> кода неизвестны.

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

← →
Sha © (2004-04-29 16:09) [41]

> WebErr © (29.04.04 15:41) [39]

> Я бы даже сказал, что многомерных массивов вообще не существует в машинной логике

А команда MOV EAX,[ECX+EDX] из какой логики?
А переменные существуют? А может это все один массив MEM[0..MaxInt]?
:))

← →
Goida © (2004-04-29 16:20) [42]

> Sha

Команда это одно, а в памяти все равно - линия...

← →
WebErr © (2004-04-29 16:25) [43]

> А команда MOV EAX,[ECX+EDX] из какой логики?

Дилетантский выпад - асм я и сам знаю, индексация всё равно в линию! ;)
Кстати, могли бы тогда уж ткнуть в меня чем-то наподобие DS:[BX][SI]. Вот где она иллюзия двойной индексации на самом низком уровне (прости, асм).

← →
Sha © (2004-04-29 16:36) [44]

> WebErr © (29.04.04 16:25) [43]
> Дилетантский выпад - асм я и сам знаю, индексация всё равно в линию! ;)

Вовсе необязательно быть столь самокритичным :)))
Хотя, наверное, именно поэтому с тобой так приятно разговаривать.

← →
Anatoly Podgoretsky © (2004-04-29 16:37) [45]

Goida © (29.04.04 16:20) [42]
Для многомерных динамических, при современной реализации это не так, это много линий.

← →
WebErr © (2004-04-29 16:41) [46]

> Anatoly Podgoretsky © (29.04.04 16:37) [45]

Но линий, и никаких матриц, кубов и прочей нечисти! :)

← →
Sha © (2004-04-29 16:47) [47]

> Goida © (29.04.04 16:20) [42]
> Команда это одно, а в памяти все равно - линия...

Еще иногда а в памяти прямоугольник, а иногда а в памити куб.
Проходили, или уже прошли?

← →
Goida © (2004-04-29 16:54) [48]

> Sha

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

← →
WebErr © (2004-04-29 16:59) [49]

> Sha © (29.04.04 16:47) [47]

What you see is not what is it
Первое правило программера: Не верь глазам своим! ;)

← →
Anatoly Podgoretsky © (2004-04-29 17:03) [50]

Goida © (29.04.04 16:54) [48]
Кто сказал, про банки слышал, классический пример матрицы.

← →
WebErr © (2004-04-29 17:06) [51]

> Anatoly Podgoretsky © (29.04.04 17:03) [50]

Что за банки?

← →
Sha © (2004-04-29 17:07) [52]

> Goida © (29.04.04 16:54) [48]
> Не может быть в памити куба. Память линейна. Но если ты говоришь о логическом представлении...

Еще как может.
Память линейна как раз в логическом представлении программиста. Конструктивно удобнее разбивать адрес на две (как в современных ОЗУ) или три (как это было раньше) группы битов, и представлять эти группы битов как индексы для доступа к "прямоугольной" или "кубической" памяти. Это делается прозрачно для программиста.

← →
Sha © (2004-04-29 17:10) [53]

> WebErr © (29.04.04 16:59) [49]
> Первое правило программера: Не верь глазам своим! ;)

Так то программера, а я программист.

← →
Goida © (2004-04-29 17:12) [54]

Хорошо. Раз так, то дайте определение ВМ Фон Неймана. Компьютер пока еще не стал чем-то иным.

> Sha

За знаниями. Но Вы говорите вещи, которые не соответствую классическому описанию хранения информации в памяти машины.

> Конструктивно удобнее разбивать адрес на две (как в современных
> ОЗУ) или три (как это было раньше) группы битов

Скажи, ты имел ввиду что-то типа сегментов и смещений?

Нет, речь идет о контроллере памяти :)
Северном мосте, так сказать :)

Goida © (29.04.04 17:17) [56]

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

> Sha

Хотя бы одну ссылку о том, о чем Вы говорите. Пожалуйста. Мне все равно: рус., анг..

developer.intel.com
www.agner.org/assem
www.wasm.ru

Хорошо, я посмотрю. Не обещаю, что сразу же. Но если я замечу, что Вы в чем-то ошиблись, обязательно ;) Вам об этом сообщу. Спасибо за ссылки :)

Goida © (29.04.04 17:41) [62]

Ага, сообщи :)
Перед этим еще стоит прочесть какую-нибудь хорошую книгу по архитектуре современных ЭВМ.

Насчет "матричной" памяти, не получится используется во многих системах, Виндоус тоже давно поддерживает, граница в 4 гб, давно не граница.

> Sha

Хватит сарказничать. Я достаточно хорошо знаю архитектуру ЭВМ. Если увижу, что Вы не правы, сообщу... В другом случае признаю правоту Вашей точки зрения...

> Goida © (29.04.04 17:55) [65]
> Хватит сарказничать. Я достаточно хорошо знаю архитектуру ЭВМ.

Думаю, знания никому не вредят.

> В другом случае признаю правоту Вашей точки зрения...

Да не надо мне этого.

> В таком случае: А есть ли тогда хоть в каком-то языке динамические
> многомерные массивы? ;-J

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

← →
CyberStorm (2004-04-29 20:39) [68]

Понаписали то :)
Вопрос был про многомерный динамический массив... то что у Borland он сделан при помощи указателей на одномерные динамические массивы вполне закономерно и исходит из принципов работы диспетчера памяти как Windows так и "надстройки" над Windows-ким диспетчером от Borland. Понятие "динамический" подразумевает произвольное изменение размеров элементов по первому требованию и использование указателей на одномерные динамические массивы позволяет работать с многомерными структурами самым эффективным образом - быстрее просто не придумать. В статических многомерный массивах нет проблемы перераспределения памяти при изменениях размерности - "там все делается раз и навсегда" поэтому и организация другая и доступ к элементам более быстрый, но гибкости меньше.

> Sha

Хочу уточнить. Что ты имеешь ввиду под не линейностью физического представления памяти? Надеюсь, я правильно тебя понял? Ты утверждаешь, что в современных ЭВМ память может быть матрицей, кубом или чем-то подобным. Так? Или ты не это имеешь ввиду? Просто, чтобы мне что-то искать, мне нужно точно знать твою позицию.

> TUser

Это и я говорил. Только вот мне не поверили...

> Goida © (29.04.04 21:45) [69]
> ...Ты утверждаешь, что в современных ЭВМ память может быть матрицей...

Утверждаю :)
В частности, утверждаю, что кеш данных L1 - это матрица:
Pentium, PPro - 256 * 32, PMMX, PII, PIII - 512 * 32, P4 Northwood - 128 * 64, Pentium 4 Prescott - 256 * 64, Athlon XP, K8 - 1024 * 64.

Утверждаю, что:
Все линии кеша выравниваются на границу, равную своей длине.
Доступ к данным в пределах одной линии быстрее, чем случайный.
Работа с данными, пересекающими границу, неэффективна.
Ну и много чего еще.

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

Да вспомните машины (Поста, Тьюринга, РАМ) и желание квадрировать и кубировать память отпадет как неактуальное.

Goida © (29.04.04 21:45) [69]
Sha © (29.04.04 23:50) [70]

Думаю, что ты как человек, достаточно хорошо знающий архитектуру ЭВМ, понимаешь, что структура кеша в конечном счете определяет структуру всей памяти. Именно потому, что в кеш необходимо грузить линию целиком при доступе к яейке памяти по произвольному адресу и проиводится деление адреса на группы битов, упомянутое ранее.

> Sha

Думаю, опять же, что мы с тобой говорим о разном. Пока я не берусь утверждать окончательно, т.к. не могу тебе сейчас привести ссылки на источники (конспекты и книги), но думаю так. Ты говоришь все таки о логической структуре памяти. А я о её физической, т.е. на схеме. Я предпологаю, что при обращении к памяти действительно программист записываеть может двумерную адресацию в схему памяти, но в результате работы дешифраторов и ассоциативного устройства памяти, которое, кстати, не отменяет ее линейную структуру, адрес преобразуется в линейный. Таким образом, преобразование двумерного адреса в линейный будет скрато от программиста на аппаратном уровне.
Но, ты говоришь о кеше. На сколько я помню, в нем как раз и используется ассоциативное устройство памяти. Так как такое устройство, на сегодняшний день, позволяет иметь наиболее быстрый доступ к даннм. Устройство не могу привести, т.к. с ходу в инете не нашел. Но могу тебя заверить, такое устройство - это надстройка над линейно физической памятью. Найду, приведу тебе её устройство.

Goida © (30.04.04 10:26) [73]

Хорошо бы еще заверить производителей чипсетов и чипов памяти.
Заверяю тебя, они знают недостаточно - у них в техдокументации такое понаписано :)

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

Для начала
http://developer.intel.com/design/pentium4/manuals/
http://developer.intel.com/design/Pentium4/documentation.htm
http://www.amd.com/us-еn/Processors/TechnicalResources/0,,30_182_739,00.html
http://www.amd.com/us-en/Processors/DevelopWithAMD/0,,30_2252,00.html
http://www.via.com.tw/en/Digital%20Library/PR040212KT880.jsp
http://www.via.com.tw/en/k7-series/kt880.jsp

> Sha

Спасибо, посмотрю :)

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