В чем отличие массива массивов от многомерного массива и почему многомерный массив вроде бы как лучше. Сколько ни писал на Java и на C++, разницы так и не заметил
new RSDN@Home(1.1.4, 303) << new Message(); std::head::ear << "Celtic Awakening — The Wind Dances";
Здравствуйте, ansi, Вы писали:
A>В чем отличие массива массивов от многомерного массива и почему многомерный массив вроде бы как лучше. Сколько ни писал на Java и на C++, разницы так и не заметил
Многомерный массив — это один большой кусок памяти, а массив массивов — много более мелких кусков памяти. + и — очевидны.
А что ты подразумеваешь под двумя этими понятиями?
Если взять точку зрения Quintanar, то он исходит из технической реализации данного вопроса. IMHO это не есть правильно, поскольку я могу создать "массив массивов" используя единый кусок памяти. Отличия будут только в логике работы с элементами массива.
Здравствуйте, ansi, Вы писали:
A>В чем отличие массива массивов от многомерного массива и почему многомерный массив вроде бы как лучше. Сколько ни писал на Java и на C++, разницы так и не заметил
Многомерный массив — это некий контейнер, у которого размерности не зависят друг от друга. Поэтому он представляет "гиперпрямоугольник".
Линеаризация многомерного массива (развёртка на одномерный) — очень проста:
(...(((x1)*X2+x2)*X3+x3)...+xn) где X1...Xn — размеры, x1...xn — координаты элемента.
Поэтому зачастую его хранят в одномерном массиве, т.е. сплошном блоке памяти.
Массив массивов — означает (в общем случае) массив с рваными краями, где нет гарантии, что размеры подмассивов с разными координатами равны.
Соответственно, задача линеаризации оказывается более сложной — и обычно ею не занимаются, размещая подмассивы в разных блоках и храня на них указатели.
По скорости доступа — многомерные массивы и массивы массивов примерно равны: в одном случае затраты на арифметику, в другом — на косвенность. А дальше — как карта ляжет с кэшем.
Здравствуйте, Quintanar, Вы писали:
Q>Здравствуйте, ansi, Вы писали:
A>>В чем отличие массива массивов от многомерного массива и почему многомерный массив вроде бы как лучше. Сколько ни писал на Java и на C++, разницы так и не заметил
Q>Многомерный массив — это один большой кусок памяти, а массив массивов — много более мелких кусков памяти. + и — очевидны.
То есть int[][] vs int** ?
new RSDN@Home(1.1.4, 303) << new Message(); std::head::ear << "Cazwa Kain — Bygones";
Здравствуйте, kiamor, Вы писали:
K>А что ты подразумеваешь под двумя этими понятиями?
Это я хочу у вас спросить. Просто видел несколько раз фразы, что Java поддерживает многомерные массивы, в отличие от Си++. Ну и в этом плане — это плюс для Java.
K>Если взять точку зрения Quintanar, то он исходит из технической реализации данного вопроса. IMHO это не есть правильно, поскольку я могу создать "массив массивов" используя единый кусок памяти. Отличия будут только в логике работы с элементами массива.
Ну понятно. Если смотреть в этом плане, то вроде как в си++ действительно нельзя такое сделать напрямую (динамически выделить память под многомерный массив).
K>Разницу чувствуешь?
Ага
new RSDN@Home(1.1.4, 303) << new Message(); std::head::ear << "Celtic Awakening — Breton Children's Song";
Здравствуйте, Кодт, Вы писали:
К>Многомерный массив — это некий контейнер, у которого размерности не зависят друг от друга. Поэтому он представляет "гиперпрямоугольник".
[] К>Массив массивов — означает (в общем случае) массив с рваными краями, где нет гарантии, что размеры подмассивов с разными координатами равны. К>Соответственно, задача линеаризации оказывается более сложной — и обычно ею не занимаются, размещая подмассивы в разных блоках и храня на них указатели.
Ясно. Спасибо!
new RSDN@Home(1.1.4, 303) << new Message(); std::head::ear << "Celtic Awakening — Feast At Tintern";
Здравствуйте, ansi, Вы писали:
K>>Если взять точку зрения Quintanar, то он исходит из технической реализации данного вопроса. IMHO это не есть правильно, поскольку я могу создать "массив массивов" используя единый кусок памяти. Отличия будут только в логике работы с элементами массива. A>Ну понятно. Если смотреть в этом плане, то вроде как в си++ действительно нельзя такое сделать напрямую (динамически выделить память под многомерный массив).
Да почему нельзя, очень даже можно.
Вариант номер раз:
const int N = 5;
const int M = 7;
Some *pLinear = new Some[N*M];
Some(*pTwoDim)[M] = reinterpret_cast< Some(*)[M] >(pLinear);
...
delete [] pLinear; // удалять нужно именно линейный массив, иначе можно огрести проблемы
В данном случае reinterpret законный, так как по Стандарту элементы массива идут встык, и можно трактовать линейный массив как массив из одинаковых массивов.
Вариант номер два:
int n, m;
Some *pLinear = new Some[n*m];
Some **pTwoDim = new Some*[n];
for(int x=0; x<n; ++x) pTwoDim[x] = pLinear + x*m;
...
delete [] pTwoDim[0]; // == pLineardelete [] pTwoDim;
Здравствуйте, Quintanar, Вы писали:
Q>Здравствуйте, ansi, Вы писали:
A>>В чем отличие массива массивов от многомерного массива и почему многомерный массив вроде бы как лучше. Сколько ни писал на Java и на C++, разницы так и не заметил
Q>Многомерный массив — это один большой кусок памяти, а массив массивов — много более мелких кусков памяти. + и — очевидны.
Многомерный массив и массив массивов это в точности одно и тоже — один большой кусок памяти:
ARRAY M, N OF ... = (* сокращенное обозначение для *) = ARRAY M OF ARRAY N OF ...
А что касается случая когда память фрагментирована — так это массив указателей на массивы.
Здравствуйте, ansi, Вы писали:
K>>А что ты подразумеваешь под двумя этими понятиями? A>Это я хочу у вас спросить. Просто видел несколько раз фразы, что Java поддерживает многомерные массивы, в отличие от Си++. Ну и в этом плане — это плюс для Java.
Разгадка состоит в том что в Си/Си++ вообще нет встроенного массивового типа!!!
На языках Си/Си++ нельзя написать аналога следующей процедуры:
PROCEDURE Fill(VAR a: ARRAY OF ARRAY OF REAL; value: REAL);
VAR i,j: INTEGER;
BEGIN
FOR i := 0 TOLEN(a, 0) - 1 DO
FOR j := 0 TOLEN(a, 1) - 1 DO
a[i, j] := value
END
END
END Fill;
Здравствуйте, Сергей Губанов, Вы писали:
СГ>Многомерный массив и массив массивов это в точности одно и тоже — один большой кусок памяти:
Это в Обероне одно и то же. А в общем случае — нет.
Представим себе, что массив, помимо собственно элементов, несёт ещё какую-нибудь полезную информацию о самом себе (например, габариты).
Двумерный массив (не позволяющий получать подмассив-срез — только отдельные элементы) может хранить оба габарита в единственном количестве; а массив массивов — вынужден скопировать эти габариты в каждый свой элемент — подмассив.
Спросишь — зачем нужно информацию времени компиляции хранить, а не подразумевать?
Очень просто. Если какая-то функция принимает ссылку на обобщённый "двумерный массив" либо на "одномерный массив одномерных массивов", то она может поинтересоваться в рантайме об этих габаритах. Естественно, придётся обеспечить какое-то полиморфное поведение — т.е. либо хранить габариты, либо держать указатель на vmt, с методами, возвращающими эти габариты.
Здравствуйте, Сергей Губанов, Вы писали:
СГ>Разгадка состоит в том что в Си/Си++ вообще нет встроенного массивового типа!!!
... и вообще, встроенные типы скудны до безобразия. Поэтому лучше пользоваться классами, тем более, что их можно наваять сколько угодно под любые нужды.
Кстати, я уже говорил как-то, что манипулирование встроенными типами и голыми структурами данных — хороший способ испортить себе жизнь при отладке или рефакторинге.
И сейчас повторю.
СГ>На языках Си/Си++ нельзя написать аналога следующей процедуры:
Если пользоваться невстроенными типами — то как нефиг делать.
Даже со сплошным хранилищем.
Здравствуйте, kiamor, Вы писали:
K>...я могу создать "массив массивов" используя единый кусок памяти. Отличия будут только в логике работы с элементами массива.
K>Разницу чувствуешь?
Чувствую что ты не понимашь о чем говоришь.
Вот тебе простенький код для того чтбы было более понятно:
byte[][] jaggedArray = new byte[10][];
jaggedArray[1] = new byte[] { 1, 2 };
jaggedArray[7] = new byte[] { 2, 4, 8, 12 };
...
// где-то в глубине программы
jaggedArray[7] = jaggedArray[7];
Как это реализовать "единым кусок памяти"? Сколько по твоему байт будет уходить на хранение одного элемента массива jaggedArray? А на 64-битной платформе?
Массив массивов — это массив ссылок на массивы определенного типа (в том числе и опять же массивов массивов).
Многомерные же массивы — это матрицы. Конечно не важно как они реализованы, но важно, что они не обладают теми свойствами которыми обладают массивы массивов. Так что эмулировать многомерные массивы на массивах массивов можно, а не оборот нет.
Что до реализации, то массивы массивов могут быть реализованы только одним способом. Мномерные же разными, но эффективная реализация именно единым блоком памяти. Так что слова Quintanar неверны только с очень теоритической точки зрения. На практике же так оно и есть.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
С++ фактически вообще не поддерживает массивы как первокласные сущьности. Массив в С++ — это всего лишь область памяти. Рельная работа же ведется на базе указателей и классов-оберток.
A>Ну понятно. Если смотреть в этом плане, то вроде как в си++ действительно нельзя такое сделать напрямую (динамически выделить память под многомерный массив).
В С++ это делается на указателях. Вот пример эмуляции массива массивов:
int** jaggedArray = new int*[10];
jaggedArray[1] = new int[2];
jaggedArray[7] = new int[4];
...
// где-то в глубине программы
jaggedArray[7] = jaggedArray[7];
На работают с такими голыми структурами тольно довольно неразумные люди. Намного проще взять обертку вроде vertor-а и не иметь проблем.
... << RSDN@Home 1.1.4 beta 4 rev. 351>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Кодт, Вы писали:
СГ>>Многомерный массив и массив массивов это в точности одно и тоже — один большой кусок памяти:
К>Это в Обероне одно и то же. А в общем случае — нет.
Кстати!
PROCEDURE WorkWithSlice(VAR a: ARRAY OF REAL);
VAR i: INTEGER;
BEGIN
i := LEN(a);
END WorkWithSlice;
PROCEDURE WorkWithWhole(VAR a: ARRAY OF ARRAY OF REAL);
VAR i,j: INTEGER;
BEGIN
i := LEN(a,0);
j := LEN(a,1);
WorkWithSlice(a[0]); (***)END WorkWithWhole;
PROCEDURE Work();
VAR a: ARRAY(10,20) OF REAL;
BEGIN
WorkWithWhole(a);
END Work;
Если такое (***) возможно, это значит, что в Обероне — массивы массивов. А если невозможно — то чисто многомерные массивы.
Здравствуйте, VladD2, Вы писали:
VD>Чувствую что ты не понимашь о чем говоришь.
Тон смени. Считаю ты невнимательно отнёсся к первоначальному сообщению м моему ответу.
Техническая реализация есть техническая реализация. Несложно организовать массив массивов единым куском памяти и уж тем более работать с элементами (массивами и т.п). Необходимо лишь организовать логическую структуру (ближайшая реализация указатели, куда ж без них).
Позволю себе обратить Ваше, сэ-э-э-р, внимание на ряд похоже не очевидных для Вас фактов:
— речь идёт не о динамических массивах
— я вовсе не претендую на абсолютную инстанцию
(так что не надо пытаться меня прилюдно распять за базар отвечаю )
Здравствуйте, VladD2, Вы писали:
VD>Что до реализации, то массивы массивов могут быть реализованы только одним способом. Мномерные же разными, но эффективная реализация именно единым блоком памяти. Так что слова Quintanar неверны только с очень теоритической точки зрения. На практике же так оно и есть.
Можно сделать jagged array в цельном блоке памяти — правда, реализация будет мучительной донельзя, с кучей ограничений и т.д.
Зачем это может потребоваться? Не знаю.
Может быть, какой-то формат файла, с которым удобно работать как с проекцией в память.
Или когда нужно выжать все капли — программирование для микроконтроллеров.
Но разумеется, эффективная реализация — у jagged array это массив указателей на массивы, а у матрицы — линеаризация.
Здравствуйте, kiamor, Вы писали:
K>Техническая реализация есть техническая реализация. Несложно организовать массив массивов единым куском памяти и уж тем более работать с элементами (массивами и т.п). Необходимо лишь организовать логическую структуру (ближайшая реализация указатели, куда ж без них).
Я бы не стал связываться с языком, который будет пытаться работать с массивом массивов как с единым куском памяти. Душевное здоровье дороже.
Перекуём баги на фичи!
)
