| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Представление двухмерного массива в виде динамического списка [D7, XP]
теркин © (2012-03-22 19:43:00)Объясните пожалуйста, как можно представить двухмерный массив в виде динамического списка, так чтобы к списку можно было обращаться по индексам.
Германн (2012-03-24 16:28:00) [1]
> begin...end © (24.03.12 13:19) [38]
Не знал, спасибо.
begin...end (2012-03-24 13:19:00) [2]> Германн © (24.03.12 04:29) [37]
Пусть A - динамический массив array of array of Integer. Тогда A является ссылкой на тело одномерного массива указателей, которые ссылаются на тела одномерных массивов целых чисел. Эти последние массивы вовсе не должны находиться в памяти последовательно друг за другом.
Германн (2012-03-24 04:29:00) [3]
> Anatoly Podgoretsky © (23.03.12 07:59) [19]
>
>
> > В памяти массив любой размерности все равно расположен
> как
> > одномерный.
>
> Кроме динамических
Вот отсюда и до обеда. Но, пожалуйста, детально! :)
Jeer (2012-03-23 20:50:00) [4]
> Ес-сно, shr целочисленного <> деление на два в плавающем.
Не всегда :)
Jeer (2012-03-23 20:46:00) [5]Тьфу.. зарапортовался :)
Ес-сно, shr целочисленного <> деление на два в плавающем.
Таки, да..
size := (N shl 1)*(N+1) shr 2;
Sha (2012-03-23 19:46:00) [6]при N=3 должно быть size=6
а (N shr 1) * (N + 1) = 4
Jeer (2012-03-23 19:25:00) [7]Значит мы по разному или не об одном и том же думаем.
Бывает.
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
Я даже не знаю, какую еще арифметику использовать :)
Sha (2012-03-23 19:03:00) [8]> Jeer © (23.03.12 18:50) [31]
> (N shr 1) * (N + 1)
И это неверно
Jeer (2012-03-23 18:50:00) [9]
> 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 );
Sha (2012-03-23 18:38:00) [10]> 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.
Jeer (2012-03-23 16:53:00) [11]last= (len-1) * len shr 1 + (len-1) + 1;
==
last = (len shr 1)*(len + 1);
Jeer (2012-03-23 16:48:00) [12]
> в Button3Click массив половинного размера
Согласен.
Sha (2012-03-23 16:07:00) [13]> ТС вроде хотел еще экономию увидеть
в Button3Click массив половинного размера
Jeer (2012-03-23 16:00:00) [14]
> Я знаю способ еще быстрее.
Это понятно/известно мне тоже.
> Зачем - это другой вопрос. Надо.
Ну и ладно - ТС вроде хотел еще экономию увидеть, хотя не всегда зеркало вредно, можно его использовать для промежуточных вычислений, но это другая тема.
Нисколько не сомневаюсь в применимости одномерности - это почти стандарт, тем более в Си.
Всего лишь показал способ моделирования треугольной матрицы формально двумерным динамическим массивом - как вариант.
Sha (2012-03-23 15:52:00) [15]> Jeer © (23.03.12 15:24) [24]
Ты ищешь самый быстрый вариант для суммирования элементов матрицы.
Я знаю способ еще быстрее.
Но задача у нас другая.
Требуется перебрать все N*N элементов симметричной матрицы,
проходя все строки по очереди. Зачем - это другой вопрос. Надо.
Другие варианты обхода просто не рассматриваются.
Т.е. надо найти структуру хранения, дающую минимальное время обхода.
Замечание.
Если при этом переборе мы используем данные из обоих треугольников,
то надо учесть время на копирование их в другой треугольник.
Оптимизация алгоритма обхода при различных вычислениях -
отдельный и довольно интересный вопрос.
Jeer (2012-03-23 15:24:00) [16]После исключения кода инициализации
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
Jeer (2012-03-23 15:18:00) [17]Ок, поступим еще честнее:
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
Sha (2012-03-23 12:21:00) [18]Давайте проверим на примере честного вычисления суммы элементов симметричной матрицы матрицы.
Внешний цикл выполним тупопо строкам, дополнительными свойствами матрицы пользоваться не будем.
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 09:37:00) [19]
> Anatoly Podgoretsky © (23.03.12 07:59) [19]
> Anatoly Podgoretsky © (23.03.12 08:02) [20]
Так и есть.
Отсюда вывод ?
Двумерным динамическим массивом можно смоделировать треугольную матрицу с экономией памяти ~ в два раза.
Скорость работы с таким массивом вряд ли увеличится, но скорость обработки - возможно.
Anatoly Podgoretsky (2012-03-23 08:02:00) [20]И еще, двумерный динамический массив не обязан быть квадратным, симметричнум
Вполне может быть
123
1
12
1234
| |
Страницы: 