Czesc

Jest jakis algorytm do transponowania macierzy w miejscu?
Przejrzalem skorowidz Cormena, przejrzalem pierwsza strone w
googlu i widze tylko trywialny przypadek dla macierzy kwadratowej.


Pozdrawiam

--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

W dniu 28.01.2012 16:57, M.M. pisze:
> Czesc
>
> Jest jakis algorytm do transponowania macierzy w miejscu?
Co rozumiesz przez "w miejscu"? Zmieniają się wymiary, więc to by miało
sens tylko wtedy, gdy masz macierz zaimplementowaną na liniowym buforze.
W takiej sytuacji możesz ustawić flagę "zamień współrzędne" i już masz
transpozycję.

W przypadku gdy chcesz zamienić fizycznie dane to robienie tego w
miejscu (Dla dużej macierzy) jest morderstwem na wydajności ze względu
na cache.

--
Pozdrawiam
Michoo

do góry

Michoo <m...@v...pl> napisał(a):

> W dniu 28.01.2012 16:57, M.M. pisze:
> > Czesc
> >
> > Jest jakis algorytm do transponowania macierzy w miejscu?
> Co rozumiesz przez "w miejscu"?
Z wykorzystaniem stalej dodatkowej pamieci, niezaleznej od rozmiaru
macierzy.

> Zmieniają się wymiary, więc to by miało sens tylko wtedy, gdy
> masz macierz zaimplementowaną na liniowym buforze.
Dokladnie oto chodzi.

> W takiej sytuacji możesz ustawić flagę "zamień współrzędne" i już masz
> transpozycję.
> W przypadku gdy chcesz zamienić fizycznie dane to robienie tego w
> miejscu (Dla dużej macierzy) jest morderstwem na wydajności ze względu
> na cache.
Wlasnie jeden raz macierz ma byc transponowana, po to zeby potem wiele
razy odczyty byly przyjazne dla cache.

Bez transpozycji, na naturalnej strukturze danych, algorytm dziala tak:
for( int i=0 ; i<N ; i++ )
for( wiele-razy )
for( int j=0 ; j<M ; j++ )
obliczenia( macierz[j*N+i] )

Trzeba przetransponowac aby mozna bylo tak:
for( int i=0 ; i<N ; i++ )
for( wiele-razy )
for( int j=0 ; j<M ; j++ )
obliczenia( macierz[i*M+j] )

Pozdrawiam



>


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry