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

> 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.
Pozostałe są w macierzy X :D
Pozdrawiam


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

do góry

W dniu 2012-04-02 00:11, M.M. pisze:
> bartekltg<b...@g...com> napisał(a):
>> Nie, to wzor na 'zlozenie', nie sume.
> Czym sie rozni zlozenie od sumy?

Suma jest wtedy, gdy raz losujesz zmienną k z rozkładu,
a potem zmienną g z drugiego (być może identycznego).
Suma jest g+k

Jeśli k ~ B(n,p) (ten zapis oznacza, że zmienna losowa
k ma rozkład dwumianowy z n kulkami i przwdopodobieństwem p)
g ~ B (m,p)

to suma (to też zmienna losowa) ma rozkłąd
g+k ~ B (m+n,p)

Jest to własność intuicyjna. Rozkład B(n,p) opisuje
liczbę pozytywnych wyników n prob o prawdopodobieństwie
sukcesu p.

Rozkład ilość reszek w próbie 10 rzutów + ilość reszek
w 12 rzutach jest taki sam jak rozkąłd ilośći reszek
w 22 rzutach.

To, co nazwałem 'złożeniem' polega na tym, że najpierw
losujemy jedną liczbę k ~ B(n,p), a następnie, mając
już k robimu losowanie liczby g z rozkąłdu g~B(k,q)
(poprzednio w obu losowaniach musiało być to samo p).

Okazuje się, że g ~ B (n,p*q)

Mamy 50 kuleczek i każdą losujemy w jedną z 6 szuflad.
Kuleczki wpadające w szuflady 1-3 z prawdopodobienstwem
1/2. Rozkład ilości kulek w 1-3 k ~ B (50, 1/2 ).

Mamy teraz k kuleczek w 1-3. Prawdopodobieństwo, że
wpadła akurat w 1 to 1/3.
Ilość g ma rozkład g ~ B(k,1/3)


Ale ze wzorku g ~ B (50, 1/2*1/3) = B (50,1/6)
czyli tak, jakbyśmy od razu badali trafianie do
szuflady 1. Robienie tego (w ten sposób!) na raty
nie zmienia wyniku.

pzdr
bartekltg

do góry

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

> W dniu 2012-04-02 00:11, M.M. pisze:
> > bartekltg<b...@g...com> napisał(a):
> >> Nie, to wzor na 'zlozenie', nie sume.
> > Czym sie rozni zlozenie od sumy?
>

> Suma jest wtedy, gdy raz losujesz zmienną k z rozkładu,
> a potem zmienną g z drugiego (być może identycznego).
> Suma jest g+k
No tak.

> Jeśli k ~ B(n,p) (ten zapis oznacza, że zmienna losowa
> k ma rozkład dwumianowy z n kulkami i przwdopodobieństwem p)
> g ~ B (m,p)
Ok.

> to suma (to też zmienna losowa) ma rozkłąd
> g+k ~ B (m+n,p)
> Jest to własność intuicyjna. Rozkład B(n,p) opisuje
> liczbę pozytywnych wyników n prob o prawdopodobieństwie
> sukcesu p.
> Rozkład ilość reszek w próbie 10 rzutów + ilość reszek
> w 12 rzutach jest taki sam jak rozkąłd ilośći reszek
> w 22 rzutach.
Ok.


> To, co nazwałem 'złożeniem' polega na tym, że najpierw
> losujemy jedną liczbę k ~ B(n,p), a następnie, mając
> już k robimu losowanie liczby g z rozkąłdu g~B(k,q)
> (poprzednio w obu losowaniach musiało być to samo p).
No tak. Dzieląc jeden zbiór o liczności n na dwa
podzbiory o liczności k i n-k, schodzimy rekurencyjnie
w dół. Ale czemu za drugim razem jest B(k,q), a nie
B(k,p)?

Np. mamy 11 szufladek i n kulek. Szufladki dzielimy
mniej/więcej po równo, czyli na 5 i 6. Prawdopodobieństwo
że kulka wleci do pierwszych pięciu to 5/11, a że do
pozostałych 6/11. Czyli zmienną k losujemy z
rozkładu B(n,5/11). W ten sposób podzieliliśmy zbiór
na dwa podzbiory o liczności k i n-k. Następnie schodzimy
rekurencyjnie w dół dla "5 szufladek i k kulek" i "6 szufladek i
n-k kulek". O to chodzi?


> Okazuje się, że g ~ B (n,p*q)
Hmmm nie wiem i nie wiem do czego to jest potrzebne. Chyba
się gubię w symbolach p i q.


> Mamy 50 kuleczek i każdą losujemy w jedną z 6 szuflad.
> Kuleczki wpadające w szuflady 1-3 z prawdopodobienstwem
> 1/2. Rozkład ilości kulek w 1-3 k ~ B (50, 1/2 ).
No tak.


> Mamy teraz k kuleczek w 1-3. Prawdopodobieństwo, że
> wpadła akurat w 1 to 1/3.
> Ilość g ma rozkład g ~ B(k,1/3)
Jasne.


> Ale ze wzorku g ~ B (50, 1/2*1/3) = B (50,1/6)
> czyli tak, jakbyśmy od razu badali trafianie do
> szuflady 1. Robienie tego (w ten sposób!) na raty
> nie zmienia wyniku.
Czyli można liczyć albo rekurencyjnie, albo iteracyjnie:
k1 ~ B(50,1/6)
k2 ~ B(50-k1,1/5)
k3 ~ B(50-k1-k2,1/4)
k4 ~ B(50-k1-k2-k3,1/3)
k5 ~ B(50-k1-k2-k3-k4,1/2)
k6 = 50-k1-k2-k3-k4-k5
Jeśli B jest jakimkolwiek prawidłowym rozkładem to nie
widzę powodu aby to mogło nie działać.

Pozdrawiam i dzięki :)



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

do góry

>
> Jeśli już tak optymalizujesz, to powiedz mi czy warto zamienić
> obliczenia z typu double na inta? W programie jest macierz kwadratowa.
> Mieści się ona w całości L2.


a skad wiesz ze miesci sie ona w calosci w L2?

(co do tych optymalizacji to mowilem (byla tam blad bo
napisalem ze za 1 razem przyspieszylo mi przepisanie 4
floatow na 4 inty a bylo to przepisanie 4 intow na 4 floaty
- za drugim razem odwrotnie - nie inty i floaty zdaja sie
najwiekszym problemem tylko konwersje z float na int
(defakto jest to bug spolki fpu+kompilatory)







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

do góry

W dniu 2012-03-31 16:15, generał kenobi pisze:
> 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

Moim zdaniem właśnie tu możesz poprawić.
Iteracje są z równym krokiem, są to więc funkcje liniowe,
ściśle monotoniczne. Jak rysujesz wiersz to wystarczy, że jeden piksel
wyjdzie Ci poza ekran, a już wiesz, że cała końcówka wyszła i nie musisz
tego dalej renderować, idziesz do nast. wiersza.
Niby trochę gorzej z lewą stroną, bo musisz wiedzieć, kiedy 'wejść
na ekran', jak Ci obcina początek. Ale w gruncie rzeczy to jest
podobny problem, wystarczy znaleźć jeden piksel, który jest w ekranie i
jechać w prawo i w lewo od niego tak długo, aż nie wylezie poza ekran,
reszta nas nie interesuje.

Jak mi się zdaje, Twoje tekstury są bardzo duże, więc potencjalnie
zawsze duża część może wyłazić poza ekran.

A tak ogólnie, to imo najlepiej z góry sprawdzić, czy tekstura
musi być poobcinana (clip), czy mieści się cała. Jak będziesz
miał dużo małych tekstur i większość będzie całkowicie wchodzić
w ekran to bez sensu jest robić te warunki. Robisz dwie
osobne procedury - na maksa wydajna bez clippowania i ta, co
masz wyżej - obcinająca. Przed renderowaniem sprita robisz
test położenia wszystkich wierzchołków, jeśli wszystkie
są w ekranie, to odpalasz bez żadnego clipowania maksymalnie
prostą.

A tak w ogóle, to Twój algorytm bym 'odwrócił'. Ty poszedłeś
w kierunku takim, że każdy piksel tekstury wyświetlasz
raz na ekranie. Ten algorytm wyklucza np. powiększanie a nawet
przy samym obrocie jestem pewien, że już będziesz miał sitko
z dziurkami. Przy pomniejszaniu będzie masakrycznie niewydajnie.

Dlatego powinieneś robić to od drugiej strony: iterować
po x/y ekranowych, a dx i dy powinny wskazywać kroki
w teksturze. Dla każdego piksela ekranowego pobierasz
z tekstury kolor i tyle. Wtedy clipowanie będzie również
prostsze.
Przy takim podejściu masz tylko troszeczkę trudniej, bo x i y
ekranowe idą skosami, więc jest trochę więcej roboty w ustalaniu
pierwszego x kolejnego wiersza.

do góry

> - za drugim razem odwrotnie - nie inty i floaty zdaja sie
> najwiekszym problemem tylko konwersje z float na int
> (defakto jest to bug spolki fpu+kompilatory)
>

testy u mnie na starym p4


for(int i=0; i<100000000; i++)
{
// int_ = (int) i; // 140 ms

//int_ = i * 80; // 180 ms
// int_ = i/40 ; // 2500 ms

// float_ = (float) i; // 230 ms

// float_ = ((float) i/ (i+23)); // 1800
// float_ = sqrt(float(i) ); // 2300
// float_ = cos(float(i) ); // 9600
// float_ = ((float) i/ 3.3345); // 420
// float_ = (float) i * float(i); // 350

// int_ = (float) i; // 6900 ms

}

konwersja floata na int kosztuje tyle co kilka dzielen, i tyle co
sinus jest to rodzaj buga bo konwersja z floata na int dziala normalnie
a po takim wyrazeniu malo kto sie spodziewa ze to tak wolno dziala
- jest to bug (choc nie wiem ilu i jakoch prockow/kompilatorow to dotyczy)





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

do góry

On Monday, April 2, 2012 9:46:54 AM UTC+1, wrote:
> > - za drugim razem odwrotnie - nie inty i floaty zdaja sie
> > najwiekszym problemem tylko konwersje z float na int
> > (defakto jest to bug spolki fpu+kompilatory)
> >
>
> testy u mnie na starym p4
>
>
> for(int i=0; i<100000000; i++)
> {
> // int_ = (int) i; // 140 ms
>
> //int_ = i * 80; // 180 ms
> // int_ = i/40 ; // 2500 ms
>
> // float_ = (float) i; // 230 ms
>
> // float_ = ((float) i/ (i+23)); // 1800
> // float_ = sqrt(float(i) ); // 2300
> // float_ = cos(float(i) ); // 9600
> // float_ = ((float) i/ 3.3345); // 420
> // float_ = (float) i * float(i); // 350
>
> // int_ = (float) i; // 6900 ms
>
> }
>
> konwersja floata na int kosztuje tyle co kilka dzielen, i tyle co
> sinus jest to rodzaj buga bo konwersja z floata na int dziala normalnie
> a po takim wyrazeniu malo kto sie spodziewa ze to tak wolno dziala
> - jest to bug (choc nie wiem ilu i jakoch prockow/kompilatorow to dotyczy)

Pomysl sobie o tym, w jakiej postaci jest przechowywana liczba typu float, to
zrozumiesz czemu to musi troche trwac. Tylko ktos naiwny bedzie sie spodziewal, ze to
nic nie kosztuje.

Aha, i OIMW to na procesorach P4 i nowszych dzialania na liczbach double sa szybsze
niz na float. Ale moze sie myle.

RW

do góry

> - jest to bug (choc nie wiem ilu i jakoch prockow/kompilatorow to dotyczy)
>

u mnie np jedno rzutowanie floata na inta w centralnej petli kosztuje
wiecej niz cala reszta tej petli (plus dodatkowo czyszczenie okna i blit)
- spowalnia cala aplikacje ponad dwa razy - dwa rzutowania spowalniaja
trzy razy

for(int i=from_x; i<to_x; i++)
{
// intt = float(i); // <-- kosztuje wiecej niz cala
//reszta nizej


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

// 3 ms
if(!( yy<0 || yy>=sprite_height || xx<0 ||
xx>=sprite_width ))
{

// 5 ms
if(0)
{
unsigned color = sprites_buf_[sprite_bitmap_posy + yy]
[sprite_bitmap_posx + xx];

// 6 ms

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

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


}


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

do góry

On Monday, April 2, 2012 10:46:55 AM UTC+1, wrote:
> > - jest to bug (choc nie wiem ilu i jakoch prockow/kompilatorow to dotyczy)
> >
>
> u mnie np jedno rzutowanie floata na inta w centralnej petli kosztuje
> wiecej niz cala reszta tej petli (plus dodatkowo czyszczenie okna i blit)
> - spowalnia cala aplikacje ponad dwa razy - dwa rzutowania spowalniaja
> trzy razy

Silnie Ci radze skupic sie na optymalizacji algorytmow, a nie takich niskopoziomowych
pierdol.

RW

do góry

W dniu 2012-04-02 02:58, M.M. pisze:

>> To, co nazwałem 'złożeniem' polega na tym, że najpierw
>> losujemy jedną liczbę k ~ B(n,p), a następnie, mając
>> już k robimu losowanie liczby g z rozkąłdu g~B(k,q)
>> (poprzednio w obu losowaniach musiało być to samo p).
> No tak. Dzieląc jeden zbiór o liczności n na dwa
> podzbiory o liczności k i n-k, schodzimy rekurencyjnie
> w dół. Ale czemu za drugim razem jest B(k,q), a nie
> B(k,p)?

Bo podział między zbiory 'weszło' i 'nie weszło'
może być inny. Jak w przykładzie z 6 szufladkami,
najpierw dzielimy po 3, czyli jest 1/2 sanszy że wejdzie
do wyróżnionego zbioru, a następnie z tych 3 wybieramy jedną
więc szansa jest tylko 1/3.

>
> Np. mamy 11 szufladek i n kulek. Szufladki dzielimy
> mniej/więcej po równo, czyli na 5 i 6. Prawdopodobieństwo
> że kulka wleci do pierwszych pięciu to 5/11, a że do
> pozostałych 6/11. Czyli zmienną k losujemy z
> rozkładu B(n,5/11).

Tak.

> W ten sposób podzieliliśmy zbiór
> na dwa podzbiory o liczności k i n-k. Następnie schodzimy
> rekurencyjnie w dół dla "5 szufladek i k kulek" i "6 szufladek i
> n-k kulek". O to chodzi?

Tak. Podzieliliśmy te kulki między te zbiory tak, jakby każda
z osobna była losowana i z równym prawdopodobieństwem
lądowała w każdej z szuflad.


>> Okazuje się, że g ~ B (n,p*q)
> Hmmm nie wiem i nie wiem do czego to jest potrzebne. Chyba
> się gubię w symbolach p i q.

Masz swoje wylosowane k i 5 szuflad. Wybierasz szufladę
nr 2. Losujesz liczbę kul w tej szufladzie z rozkładu B(k,1/5)

Wzorek mówi, że liczba ta ostatecznie będzie (gdy zapomnimy o k)
z rozkładu B(n,1/5 * 5/11) = B (n,1/11)
więc jakbyś od razu losował dla tej jednej.


>> Ale ze wzorku g ~ B (50, 1/2*1/3) = B (50,1/6)
>> czyli tak, jakbyśmy od razu badali trafianie do
>> szuflady 1. Robienie tego (w ten sposób!) na raty
>> nie zmienia wyniku.
> Czyli można liczyć albo rekurencyjnie, albo iteracyjnie:
> k1 ~ B(50,1/6)
> k2 ~ B(50-k1,1/5)
> k3 ~ B(50-k1-k2,1/4)
> k4 ~ B(50-k1-k2-k3,1/3)
> k5 ~ B(50-k1-k2-k3-k4,1/2)
> k6 = 50-k1-k2-k3-k4-k5
> Jeśli B jest jakimkolwiek prawidłowym rozkładem to nie
> widzę powodu aby to mogło nie działać.

Tak, to jest właśnie pierwszy algorytm z postu.

>> n = N; //ile kulek jeszcze zostało.
>> for( i=0 ; i<M ; i++ )
>> {
>> int k = generuj_liczbę_losową_B ( n, 1.0/(M-i) );
>> x[i]+=k;
>> n-=k;
>> }

Tylko trzeba mieć poprawny generator.
Druga wersja, dzieląca na połowy, potrafi przy dużym n (w porównaniu
do liczby szuflad) zadowolić się przybliżeniem opartym o generator
normalny (jeśli chcesz rozkład 'podobny', a nie są to jakieś ścisłe
symulacje opierające poprzwność o ten rozkład:)

W sumie nie jest trudne przy takich warunkach 'naprawić'
to metodą eliminacji (jak ona się po angielsku nazywa?)
algo od początku zbudować swoją za pomocą metody 'alias'.

pzdr
bartekltg

do góry