bartekltg <b...@g...com> napisał(a):

> W dniu 2012-04-01 19:37, M.M. pisze:
>
> > W oryginalnym kodzie mam coś innego. Mam dane zero-jedynkowe i buduję z nic
> h
> > układ równań normalnych. Dane mam upakowane. Upakowanie polega
> > na tym Ĺźe zamiast zer i jedynek trzymam numery pozycji na ktĂłrych
> > są jedynki. Dane są trudne, mają znamiona funkcji losowej, dlatego
>
> Jedna ze standardowych metod zapisu macierzy rzadkich,
> dość rozsądnie.
>
> > w przykładzie dałem rand. Mniej/więcej coś takiego:
>
> Ale te indeksy jedynek trzymasz chyba posortowane
> po długiej wspołrzednej dla każej 'krótkiej' osobno?
Tak, są posortowane, akurat taką przyjemną cechę ma algorytm
który te dane podaje na wyjściu. W przeciwnym razie druga
pętla by musiała zaczynać się od j=0, a nie od j=i.

> > for( int i=0 ; i<N ; i++ )
> > for( int j=i ; j<N ; j++ )
> > macierz[ jedynki[i] * rozmiar_wiersza + jedynki[j] ] ++;
>
>
> 'Macierz' to juĹź ta X^t X?
> Oznaczenia
> http://en.wikipedia.org/wiki/Numerical_methods_for_l
inear_least_squares#The_gen
> eral_problem
>
>
> A skompresowane za pomocą indeksów jest samo X?
Hmmm a co jeszcze można skompresować w ten sposób w zadaniu
najmniejszych kwadratów?

> Coś tu jest nie tak;)
W sumie mogę jeszcze wrzucić do innego środowiska i sprawdzić czy
da te same wyniki. Ale na wyrywki sprawdzałem i było ok. Podejrzewasz
jakiś błąd optymalizacyjny? Jest szybszy algorytm do zbudowania układu
równań normalnych?

Pozdrawiam


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

do góry

W dniu 2012-04-01 20:53, M.M. pisze:
> bartekltg<b...@g...com> napisał(a):
>
>> W dniu 2012-04-01 19:37, M.M. pisze:
>>
>>> W oryginalnym kodzie mam coś innego. Mam dane zero-jedynkowe i buduję z nic
>> h
>>> układ równań normalnych. Dane mam upakowane. Upakowanie polega
>>> na tym Ĺźe zamiast zer i jedynek trzymam numery pozycji na ktĂłrych
>>> są jedynki. Dane są trudne, mają znamiona funkcji losowej, dlatego
>>
>> Jedna ze standardowych metod zapisu macierzy rzadkich,
>> dość rozsądnie.
>>
>>> w przykładzie dałem rand. Mniej/więcej coś takiego:
>>
>> Ale te indeksy jedynek trzymasz chyba posortowane
>> po długiej wspołrzednej dla każej 'krótkiej' osobno?
> Tak, są posortowane, akurat taką przyjemną cechę ma algorytm
> który te dane podaje na wyjściu. W przeciwnym razie druga
> pętla by musiała zaczynać się od j=0, a nie od j=i.
>
>>> for( int i=0 ; i<N ; i++ )
>>> for( int j=i ; j<N ; j++ )
>>> macierz[ jedynki[i] * rozmiar_wiersza + jedynki[j] ] ++;
>>
>>
>> 'Macierz' to juĹź ta X^t X?
>> Oznaczenia
>> http://en.wikipedia.org/wiki/Numerical_methods_for_l
inear_least_squares#The_gen
>> eral_problem
>>
>>
>> A skompresowane za pomocą indeksów jest samo X?
> Hmmm a co jeszcze można skompresować w ten sposób w zadaniu
> najmniejszych kwadratów?
>
>> Coś tu jest nie tak;)
> W sumie mogę jeszcze wrzucić do innego środowiska i sprawdzić czy
> da te same wyniki. Ale na wyrywki sprawdzałem i było ok. Podejrzewasz
> jakiś błąd optymalizacyjny? Jest szybszy algorytm do zbudowania układu
> równań normalnych?

Trochę skromnie to opisałeś i nie do koca widzę, jak to robisz.

Jak dokładnie zapisujesz X i ma m*n. jedynki[] to tablica
z którymi pozycjami?

pzdr
bartekltg

do góry

bartekltg <b...@g...com> napisał(a):

> Równoważność z kodem MM zapewnia nam ta własność
> en.wikipedia.org/wiki/Binomial_distribution#Conditio
nal_binomials
Jeśli jest wzór na sumę zmiennych losowych o dobrej
zbieżności to faktycznie można wyliczy od razu dla całej połowy
tablicy i potem rekurencyjnie. Ładne :)

Pozdrawiam


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

do góry

bartekltg <b...@g...com> napisał(a):
> Trochę skromnie to opisałeś i nie do koca widzę, jak to robisz.
>
> Jak dokładnie zapisujesz X i ma m*n. jedynki[] to tablica
> z ktĂłrymi pozycjami?

Pisząc z pamięci:

Dla jednej pary x i y:
x to wektor zer i jedynek.
y to wartość skalarna którą chcemy aproksymować.
m to macierz układu równań normalnych

x ma rozmiar x.size // notacja za Cormenem
m ma rozmiar x.size wierszy i (x.size+1) kolumn, ostatnia kolumna to wyrazy
wolne równania.

Na początku m jest wyzerowane.

Rozszerzam x przez przylaczenie na koniec y:
x[x.size] = y;
x.size = x.size+1

potem w dwóch pętlach:
for( i=0 ; i<x.size-1 ; i++ )
for( j=0 ; j<x.size ; j++ )
m[i][j] += x[i] * x[j];

I tak dla każdego wektora. Potem oddzielna sprawa rozwiązać ten układ
równań.

Pierwsza optymalizacja:
Ze względu na to że macierz jest symetryczna, to można wyliczyć tylko
jeden trójkąt:
for( i=0 ; i<x.size-1 ; i++ )
for( j=i ; j<x.size ; j++ )
m[i][j] += x[i] * x[j];

I druga optymalizacja:
ze względu na to że dane to zera i jedynki, zapamiętuję w
jedynki[] pozycje jedynek (posortowane) i wychodzi:
for( i=0 ; i<jedynki.size ; i++ ) {
for( j=i ; j<jedynki.size ; j++ )
m[ jedynki[i] ][ jedynki[j] ] ++ ; // x[ jedynki[i] ] * x[ jedynki[j] ];
m[i][x.size-1] += y;
}

Można coś ulepszyć?
Pozdrawiam


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

do góry

W dniu 2012-04-01 22:09, M.M. pisze:
> bartekltg<b...@g...com> napisał(a):
>
>> Równoważność z kodem MM zapewnia nam ta własność
>> en.wikipedia.org/wiki/Binomial_distribution#Conditio
nal_binomials
> Jeśli jest wzór na sumę zmiennych losowych o dobrej
> zbieżności

?
NIe ma potrzeby żadnego wzoru na sumę. O co chodzi z dobrą
zbieżnioćśią też nei wiem.

> to faktycznie można wyliczy od razu dla całej połowy
> tablicy i potem rekurencyjnie. Ładne :)


Nie, to wzór na 'złożenie', nie sumę.
I to właśnie złożenie jest potrzebne w tej rekurencji;)
Wersja rekurencyjna korzystająca z tego samego wzrou była
pod koniec postu.

pzdr
bartekltg

do góry

W dniu 2012-04-01 22:29, M.M. pisze:
> bartekltg<b...@g...com> napisał(a):
>> Trochę skromnie to opisałeś i nie do koca widzę, jak to robisz.
>>
>> Jak dokładnie zapisujesz X i ma m*n. jedynki[] to tablica
>> z ktĂłrymi pozycjami?
>
> Pisząc z pamięci:
>
> Dla jednej pary x i y:
> x to wektor zer i jedynek.
> y to wartość skalarna którą chcemy aproksymować.
> m to macierz układu równań normalnych
>
> x ma rozmiar x.size // notacja za Cormenem
> m ma rozmiar x.size wierszy i (x.size+1) kolumn, ostatnia kolumna to wyrazy
> wolne równania.


I właśnie o to x się pytam. Co to jest i jak się ma do X
z zagadnienia najmniejszych kwadratów
min (X beta - y)^2



> Można coś ulepszyć?


Nie wiem, bo dalej nie odcyfrowałem.

Wyjdź z opisu zagadnienia linkowanego w wiki,
napisz, jak trzymasz te dane.

Algorytm możesz mi pokazywać jak będe wiedział, co siedzi
w literkach:)


pzdr
bartekltg

do góry

<f...@N...gazeta.pl> napisał(a):

> <f...@N...gazeta.pl> napisał(a):
>
> > <f...@N...gazeta.pl> napisał(a):
> >
> > > =?ISO-8859-2?Q?_genera=B3_kenobi?= <f...@W...gazeta.pl> napisał(a):
> > >
> > > > ten sposob rysowania rotowanej bitmapy jest fenomenalny
> > > > swoja prostota
> > > >
> > > > for(int j=0; j<sprite_height; j++)
> > > > {
> > > > for(int i=0; i<sprite_width; i++)
> > > > {
> > > > SetPixel( x>>20, y>>20, sprite[j][i] );
> > > >
> > > > x += dxdx; // skosy/ poprawki dla ruchu pixele na fiz ekranie
> > > > y += dydx; // dla ruchu po tekselach x++
> > > > }
> > > >
> > > > x += dxdy; // skosy dla y++
> > > > y += dydy;
> > > > }
> > > >
> > > > tu raczej nie da sie nic poprawic - ale chcialbym jakos moze
> > > > poprawic sama funkcje stawiania pixela
> > > >
> > > > inline void SetPixelInDibInt(int x, int y, unsigned color)
> > > > {
> > > >
> > > > int yc = CLIENT_Y-y;
> > > >
> > > >
> > > > if(!pBits) return;
> > > >
> > > > if(yc<0) return;
> > > > if(yc>=CLIENT_Y) return;
> > > >
> > > > if(x<0) return;
> > > > if(x>=CLIENT_X) return;
> > > >
> > > >
> > > > int adr = (yc*CLIENT_X+x);
> > > >
> > > > ((unsigned*)pBits)[adr] = color;
> > > >
> > > > }
> > > >
> > > > mam tutaj cala mase warunkow, zabezpieczajacych wprost przed
> > > > postawieniem pixela poza pamiecia ekranu - samo filtrowanie
> > > > sprite'ow robie bardzo zgrubne (odrzucam sprity o srodku iles tam
> > > > dalej poza ekranem ) tak ze przez to przechodzi cala masa
> > > > pixeli ze sprite'ow ktore sa tylko czesciowo w ekranie --
> > > >
> > > > jak przerobic kod tej funkcji by bylo szybciej?
> > > >
> > > wychodzi na to ze wlasnie nalezaloby odwrocic proces - o ile
> > > teraz jake po calej tekturze (a duza tekstura w prog2.exe ma 1000x1000
> > > pixeli ) i czestokroc wypadam poza ekran to po obroceniu mozna
> > > iterowac bez problemu po obruconej teksturze tylko w tym kawalku
> > > ktory lezy w ekranie - tak ze to mogloby nawet przyspieszyc
> > >
> > > (choc sa dodatkowe koszty albo zapisywania tych krawedzi dla sylwetki
> > > albo iterowania po wiekszych kwadratach) - tak ze zarazem moze
> przyspieszyc
> > > jak i moze zwolnic
> > >
> >
> > troche sie zmeczylem ale wieczorem moze sprobuje (z ciekawosci czy
> > przyspieszy) uruchomic prostrsza wersji z odwrotna transformacja
> > (tj bez sylwetek)
> >
> >
>
> napisalem
>
> int from_x = max( min(xAfiz,xBfiz,xCfiz,xDfiz), 0);
> int to_x = min( max(xAfiz,xBfiz,xCfiz,xDfiz), CLIENT_X);
> int from_y = max( min(yAfiz,yBfiz,yCfiz,yDfiz), 0);
> int to_y = min( max(yAfiz,yBfiz,yCfiz,yDfiz), CLIENT_Y);
>
>
> for(int j=from_y; j<to_y; j++)
> {
> int fy = j - yAfizInt;
>
> int dxdy_fy = dxdy_ * fy;
> int dydy_fy = dydy_ * fy;
>
> for(int i=from_x; i<to_x; i++)
> {
> int fx = i - xAfizInt;
>
> int logX = ( dxdx_ * fx - dxdy_fy)>>20;
> int logY = (-dydx_ * fx + dydy_fy)>>20;
>
> if( logY<0 || logY>=sprite_height || logX<0 ||
> logX>=sprite_width );
> else
> {
> unsigned color = sprites_buf_[sprite_bitmap_posy + logY]
> [sprite_bitmap_posx + logX];
>
> if(!color==0)
> ((unsigned*)pBits)[((CLIENT_Y-1-j)*CLIENT_X+i)] = color;
>
> }
>
> }
>
> }
>
>
> zniknely artefakty (choc one bywaly fajne jak kropki w druku
> gazetowym ) i cholerstwo jeszcze troche przyspieszylo - przyspiesza na
> wyraznych przypadkach clippingu bo w tę strone jest automatyczny i nie
> stawia sie ani nawet jednego pixela poza ekranem,
> moglbym jeszcze zrobic te sylwetki i przepisac petle z mnoznej na
> dodawczą ale to moze kiedy indziej
>
> martwi mnie teraz inna rzecz - plynnosc jest slaba bo czasy ramek
> oscylują jak szum, przy tym nie mam pewnosci czy plynnosc przestrzenna
> jest ok - tj np czy obracaniu nie kwantyzuje malych roznic miedzy katami
> obrotu - trzebaby sie przyjrzec kodu - ale to tez ew raczej kiedy indziej
> - dziala tylko rwie (nie jest oleiscie plynnie)
>

jeszcze poprawilem, i znowu nawet wyraznie przyspieeszylo


int fy = from_y - yAfizInt;
int fx = from_x - xAfizInt;

int logX = ( dxdx_ * fx - dxdy_ * fy);
int logY = (-dydx_ * fx + dydy_ * fy);

int dj_logX = ( ( -dxdy_) - ( dxdx_)*(to_x-from_x));
int dj_logY = ( ( dydy_) - (-dydx_)*(to_x-from_x));

for(int j=from_y; j<to_y; j++)
{


for(int i=from_x; i<to_x; i++)
{

int xx = logX>>16;
int yy = logY>>16;

if(!( yy<0 || yy>=sprite_height || xx<0 ||
xx>=sprite_width ))
{
unsigned color = sprites_buf_[sprite_bitmap_posy + yy]
[sprite_bitmap_posx + xx];

if(!color==0) //SetPixelInDibInt(i, j, color);
((unsigned*)pBits)[((CLIENT_Y-1-j)*CLIENT_X+i)] = color;

}

logX += ( dxdx_) ;
logY += (-dydx_) ;


}

logX += dj_logX;
logY += dj_logY;

}
}

moze nawet troche mniej narzekam na plynnosc, te szarpania sa glownie
chyba tylko temporalne - kiedys by trzeba pocwiczyc wyrownywanie czasow
ramek - finalnie od wersji z poczatku watku o rotowaniu bitmap
przyspieszylo prawie 10 razy




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

do góry

bartekltg <b...@g...com> napisał(a):

> W dniu 2012-04-01 22:29, M.M. pisze:
> > bartekltg<b...@g...com> napisał(a):
> >> Trochę skromnie to opisałeś i nie do koca widzę, jak to robisz.
> >>
> >> Jak dokładnie zapisujesz X i ma m*n. jedynki[] to tablica
> >> z ktĂłrymi pozycjami?
> >
> > Pisząc z pamięci:
> >
> > Dla jednej pary x i y:
> > x to wektor zer i jedynek.
> > y to wartość skalarna którą chcemy aproksymować.
> > m to macierz układu równań normalnych
> >
> > x ma rozmiar x.size // notacja za Cormenem
> > m ma rozmiar x.size wierszy i (x.size+1) kolumn, ostatnia kolumna to wyrazy
> > wolne rĂłwnania.
>
>
> I właśnie o to x się pytam. Co to jest i jak się ma do X
> z zagadnienia najmniejszych kwadratĂłw
> min (X beta - y)^2
Duże X to macierz wektorów które oznaczyłem jako małe x.
Pozdrawiam


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

do góry

W dniu 2012-04-01 23:56, M.M. pisze:
> bartekltg<b...@g...com> napisał(a):
>
>> W dniu 2012-04-01 22:29, M.M. pisze:
>>> bartekltg<b...@g...com> napisał(a):
>>>> Trochę skromnie to opisałeś i nie do koca widzę, jak to robisz.
>>>>
>>>> Jak dokładnie zapisujesz X i ma m*n. jedynki[] to tablica
>>>> z ktĂłrymi pozycjami?
>>>
>>> Pisząc z pamięci:
>>>
>>> Dla jednej pary x i y:
>>> x to wektor zer i jedynek.
>>> y to wartość skalarna którą chcemy aproksymować.
>>> m to macierz układu równań normalnych
>>>
>>> x ma rozmiar x.size // notacja za Cormenem
>>> m ma rozmiar x.size wierszy i (x.size+1) kolumn, ostatnia kolumna to wyrazy
>>> wolne rĂłwnania.
>>
>>
>> I właśnie o to x się pytam. Co to jest i jak się ma do X
>> z zagadnienia najmniejszych kwadratĂłw
>> min (X beta - y)^2
> Duże X to macierz wektorów które oznaczyłem jako małe x.

Ale x w twoim opisie to jeden wektor. Gdzie pozostałe.

Dobra, nie chce Ci się tego porządnie opisać, nie ma sprawy.

pzdr
bartekltg

do góry

bartekltg <b...@g...com> napisał(a):
> Nie, to wzor na 'zlozenie', nie sume.
Czym sie rozni zlozenie od sumy?
Pozdrawiam




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

do góry