Представление двухмерного массива в виде динамического списка

← →
теркин © (2012-03-22 19:43) [0]

Объясните пожалуйста, как можно представить двухмерный массив в виде динамического списка, так чтобы к списку можно было обращаться по индексам.

← →
begin...end © (2012-03-22 19:51) [1]

Ваш вопрос не совсем ясен. Вы о динамических массивах?

var A: array of array of Integer; // двумерный динамический массив I, J: Integer; begin // A - массив из двух массивов, каждый из которых содержит 10 элементов // Выделение памяти SetLength(A, 2, 10); // Заполнение массива for I := Low(A) to High(A) do for J := Low(A[I]) to High(A[I]) do A[I, J] := I + J end

← →
теркин © (2012-03-22 20:29) [2]

Возможно вопрос задан не корректно. Есть динамический список объектов, к которому надо обратится по индексам. изначально массив объявлен как
UnitRebro:array of array of TrebroList;
У массива есть особенность он симметричен относительно главной диагонали, и получается так что значения повторяются и его размер можно сократить почти в два раза.

← →
Jeer © (2012-03-22 20:37) [3]

Тем более непонятно - при чем тут обращение к элементам и компактное хранение ?
Вам надо компактное хранение или обращение к двумерному, как к одномерному ?

← →
теркин © (2012-03-22 20:43) [4]

Желательно представить этот массив в виде одномерного списка, но так чтобы при необходимости элементы этого списка можно было получить по двойному индексу.

← →
Германн © (2012-03-22 21:32) [5]

> Желательно представить этот массив в виде одномерного списка,
> но так чтобы при необходимости элементы этого списка можно
> было получить по двойному индексу.

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

← →
теркин © (2012-03-22 21:40) [6]

Или иными словами если написать функция при использовании индексов ну например
function F(i,j:integer): TrebroList; begin result:= List.TrebroList.items[i*N+j]; end;
где N размерность, то получим нужный элемент по двойному индексу?

← →
Sha © (2012-03-22 21:40) [7]

> теркин © (22.03.12 20:29) [2]

1. вместо двумерного A создай одномерный B
2. вместо A[i,j] обращайся к B[i*(i+1) div 2 + j]

← →
теркин © (2012-03-22 22:26) [8]

Господин Sha

> вместо A[i,j] обращайся к B[i*(i+1) div 2 + j]

это решение уже с учетом симметрии?

← →
Jeer © (2012-03-22 22:43) [9]

Чисто для демонстрации твоего случая:

Size := Rows*Cols;
SetLength(arXY, Rows, Cols);

// Заполнение двумерного массива
for row := 0 to Rows-1 do
for col := 0 to Cols-1 do
arXY[row,col] := Cols*row + col;

// Заполнение двумерного, как одномерного
for idx := 0 to (Rows*Cols-1) do begin
row := idx div Rows;
col := idx - row*Cols;
arXY[row, col] := idx;
end;

← →
Sha © (2012-03-22 22:44) [10]

да
a[0,0] <--> b[0]
a[1,0] <--> b[1]
a[1,1] <--> b[2]
a[2,0] <--> b[3]
a[2,1] <--> b[4]
a[2,2] <--> b[5]
a[3,0] <--> b[6]
...

← →
Sha © (2012-03-22 22:51) [11]

естественно, при этом ты имеешь право обращаться
только к тем a[i,j], у которых 0<=j<=i

← →
теркин © (2012-03-22 22:55) [12]

Огромное спасибо ребята. Правду говорят -"Все гениальное -ПРОСТО". И как сразу не додумался использовать Div. Мне бы наверно чукчи сказали "Тупой ты однако".

← →
Jeer © (2012-03-22 22:58) [13]

"Вся тупость еще впереди, не забывай об этом" (С) Jeer

← →
Sha © (2012-03-22 22:58) [14]

Выражение i*(i+1) div 2 + j для неотрицательных чисел
быстрее будет вычислить как i*(i+1) shr 1 + j

← →
теркин © (2012-03-22 23:11) [15]

> естественно, при этом ты имеешь право обращаться
> только к тем a[i,j], у которых 0<=j<=i

или изменить само обращение if j>i then B[j*(j+1) div 2 +i]

← →
Sha © (2012-03-22 23:14) [16]

конечно

← →
Jeer © (2012-03-22 23:19) [17]

Для диагонально-симметричных матриц (особенно большого размера) имеет смысл еще экономить в 2 раза на размещении.

← →
теркин © (2012-03-22 23:56) [18]

> имеет смысл еще экономить в 2 раза на размещении.

Да именно за эту экономию и идет натуральная война. Размерность матриц главных циклов 450х2500. Необходимо находить произведение этой матрицы на себя транспонированную, на каждом шаге итерационного процесса. По смыслу это произведение равносильно нахождению пересечения двух множеств ребер для двух циклов. На прямом произведении через циклы for программа тратит много времени, пришлось искать пересечения, работать стала на много быстрее. Сейчас найденные пересечения буду сохранять в массиве, правда за счет память, но итераций требуется много, сходимость метода медленная, поэтому думаю игра стоит свеч. Кстати любопытная матрица попалась, верхняя релаксация сходится медленней чем нижняя.

← →
Anatoly Podgoretsky © (2012-03-23 07:59) [19]

> В памяти массив любой размерности все равно расположен как
> одномерный.

Кроме динамических

← →
Anatoly Podgoretsky © (2012-03-23 08:02) [20]

И еще, двумерный динамический массив не обязан быть квадратным, симметричнум
Вполне может быть

123 1 12 1234

← →
Jeer © (2012-03-23 09:37) [21]

> Anatoly Podgoretsky © (23.03.12 07:59) [19]
> Anatoly Podgoretsky © (23.03.12 08:02) [20]

Так и есть.
Отсюда вывод ?
Двумерным динамическим массивом можно смоделировать треугольную матрицу с экономией памяти ~ в два раза.
Скорость работы с таким массивом вряд ли увеличится, но скорость обработки - возможно.

← →
Sha © (2012-03-23 12:21) [22]

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

procedure TForm1.Button1Click(Sender: TObject); const len= 10000; var a: array of array of integer; i, j, sum: integer; t: cardinal; begin; t:=GetTickCount; sum:=0; SetLength(a,len,len); //копирование элементов из одного треугольника в другой for i:=1 to len-1 do for j:=0 to i-1 do a[j,i]:=a[i,j]; //сумма строк for i:=0 to len-1 do for j:=0 to len-1 do sum:=sum+a[i,j]; a:=nil; t:=GetTickCount-t; Memo1.Lines.Add(Format("2 измерения с копированием, %d мсек, результат %d",[t,sum])); end; procedure TForm1.Button2Click(Sender: TObject); const len= 10000; var a: array of array of integer; i, j, sum: integer; t: cardinal; begin; t:=GetTickCount; sum:=0; SetLength(a,len,len); //сумма строк for i:=0 to len-1 do begin; //идем по строке for j:=0 to i do sum:=sum+a[i,j]; //идем по столбцу for j:=i+1 to len-1 do sum:=sum+a[j,i]; end; a:=nil; t:=GetTickCount-t; Memo1.Lines.Add(Format("2 измерения без копирования, %d мсек, результат %d",[t,sum])); end; procedure TForm1.Button3Click(Sender: TObject); const len= 10000; last= (len-1) * len shr 1 + (len-1); var b: array of integer; i, j, k, sum: integer; t: cardinal; begin; t:=GetTickCount; sum:=0; SetLength(b,last+1); //сумма строк for i:=0 to len-1 do begin; //идем по строке k:=(i * i + i) shr 1; for j:=0 to i do sum:=sum+b[k+j]; //идем по столбцу k:=k+i; for j:=i+1 to len-1 do begin; k:=k+j; sum:=sum+b[k]; end; end; b:=nil; t:=GetTickCount-t; Memo1.Lines.Add(Format("1 измерениe, %d мсек, результат %d",[t,sum])); end;

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

2 измерения с копированием, 5234 мсек, результат 0 2 измерения без копирования, 4110 мсек, результат 0 1 измерениe, 2250 мсек, результат 0

← →
Jeer © (2012-03-23 15:18) [23]

Ок, поступим еще честнее:

1. Двумерный полный массив
2. Моделирование полного двумерного одномерным половинным
3. Двумерный половинный массив.

1.1. Суммирование всех элементов выполняется как у Sha (Button2Click)
2D-full Sha , 1217 мсек, сумма 100000000

1.2. Суммирование выполняется стандартно

for i:=0 to len-1 do
for j:=0 to len-1 do
sum := sum + a[i,j];

2D-full Std, 577 мсек, сумма 100000000

2. Суммирование как у Sha ( Button3Click )
1D, 1263 мсек, сумма 100000000

3. Двумерный половинный массив

procedure TfmStatusForm.Button4Click(Sender: TObject);
const
len= 10000;
var
a: array of array of integer;
i, j, sum: integer;
t: cardinal;
begin
t:=GetTickCount;
sum:=0;
SetLength(a, len);
for j:=0 to len-1 do begin
SetLength(a[j], len - j);
end;

for j:=0 to len-1 do
for i:=0 to len-j-1 do
a[j,i] := 1;

for j:=0 to len-1 do
for i:=0 to len-j-1 do
sum:=sum +a[j,i];

a:=nil;
t:=GetTickCount-t;
Memo1.Lines.Add(Format("2D-half переменная длина строки, %d мсек, сумма %d",[t,sum]));

2D-half переменная длина строки, 405 мсек, сумма 50005000

← →
Jeer © (2012-03-23 15:24) [24]

После исключения кода инициализации

1. Двумерный полный
1.1. Суммирование всех элементов выполняется как у Sha (Button2Click)
2D-full Sha , 1123 мсек, сумма 0

1.2. Суммирование выполняется стандартно
2D-full Std, 468 мсек, сумма 0

2. Одномерный, суммирование как у Sha ( Button3Click )
1D, 717 мсек, сумма 0

3. Двумерный половинный массив
2D-half переменная длина строки, 374 мсек, сумма 0

← →
Sha © (2012-03-23 15:52) [25]

> Jeer © (23.03.12 15:24) [24]

Ты ищешь самый быстрый вариант для суммирования элементов матрицы.
Я знаю способ еще быстрее.

Но задача у нас другая.
Требуется перебрать все N*N элементов симметричной матрицы,
проходя все строки по очереди. Зачем - это другой вопрос. Надо.
Другие варианты обхода просто не рассматриваются.
Т.е. надо найти структуру хранения, дающую минимальное время обхода.

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

Оптимизация алгоритма обхода при различных вычислениях -
отдельный и довольно интересный вопрос.

← →
Jeer © (2012-03-23 16:00) [26]

> Я знаю способ еще быстрее.

Это понятно/известно мне тоже.

> Зачем - это другой вопрос. Надо.

Ну и ладно - ТС вроде хотел еще экономию увидеть, хотя не всегда зеркало вредно, можно его использовать для промежуточных вычислений, но это другая тема.

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

← →
Sha © (2012-03-23 16:07) [27]

> ТС вроде хотел еще экономию увидеть

в Button3Click массив половинного размера

> в Button3Click массив половинного размера

Согласен.

last= (len-1) * len shr 1 + (len-1) + 1;

==

last = (len shr 1)*(len + 1);

> Jeer © (23.03.12 16:53) [29]

Неверно.
В процедуре Button3Click: last = (len-1) * len shr 1 + (len-1)
и, следовательно, при len=3 получаем last=5.

У тебя по формуле1 last=6,
по формуле2 last=8.

> Sha © (23.03.12 18:38) [30]
>
> > Jeer © (23.03.12 16:53) [29]
>
> Неверно.

Наоборот, верно.
Просто ты разнес вычисление размера массива на две операции:

last= (len-1) * len shr 1 + (len-1);
SetLength(b,last+1);

Что дает в итоге:
size= last + 1 = (len-1) * len shr 1 + (len-1) + 1;

А больше last нигде у тебя не используется - впрочем, это арифметика и не суть.

Размер массива для хранения верхней треугольной матрицы + диагональных элементов (N == len)
size = 0.5*N*(N+1) = (N shr 1) * (N + 1)

SetLength( b, size );

Значит мы по разному или не об одном и том же думаем.
Бывает.

N=3
size = 0.5*3*(3+1) = 6
N=4
size = 0.5*4*(4+1) = 10
N=10000
size = 0.5*10000*(10000+1) = 50 005 000

Я даже не знаю, какую еще арифметику использовать :)

при N=3 должно быть size=6
а (N shr 1) * (N + 1) = 4

Тьфу.. зарапортовался :)
Ес-сно, shr целочисленного <> деление на два в плавающем.

Таки, да..

size := (N shl 1)*(N+1) shr 2;

> Ес-сно, shr целочисленного <> деление на два в плавающем.

Не всегда :)

> Anatoly Podgoretsky © (23.03.12 07:59) [19]
>
>
> > В памяти массив любой размерности все равно расположен
> как
> > одномерный.
>
> Кроме динамических

Вот отсюда и до обеда. Но, пожалуйста, детально! :)

> Германн © (24.03.12 04:29) [37]

Пусть A - динамический массив array of array of Integer. Тогда A является ссылкой на тело одномерного массива указателей, которые ссылаются на тела одномерных массивов целых чисел. Эти последние массивы вовсе не должны находиться в памяти последовательно друг за другом.

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