matlab taki wydajny?
Mariusz Marszałkowski
Od dość dawna słyszę opinie że procedury zaimplementowane w
matlabie są bardzo wydajne. Nie znam matlaba, ale wczoraj przez
przypadek miałem go pod ręką, no i tyle ile można się nauczyć
przez godzinę sprawdziłem.
Program w matlabie robił coś takiego:
for i=1:20000
v = a * m1;
a = v * m2;
end;
Gdzie v i a to wektory double po 1000 elementów, a
m1 i m2 to macierze po 1000 na 1000 elementów.
Zainicjalizowane były losowymi liczbami.
Program wykonywał się około 100 sekund.
Na tym samym sprzęcie odpaliłem podobny
program napisany w C, skompilowany gcc.
Program w C był podobny, a nie taki sam,
gdyż robił ciut więcej obliczeń. No i w C
wykonywało to 70s.
Więc to tylko plotki że matlab jest taki wydajny?
Pozdrawiam
Stachu 'Dozzie' K.
> Od do�� dawna s�ysz� opinie �e procedury zaimplementowane w
> matlabie sďż˝ bardzo wydajne. Nie znam matlaba, ale wczoraj przez
> przypadek mia�em go pod r�k�, no i tyle ile mo�na si� nauczy�
> przez godzin� sprawdzi�em.
>
> Program w matlabie robiďż˝ coďż˝ takiego:
> for i=1:20000
> v = a * m1;
> a = v * m2;
> end;
>
> m1 i m2 to macierze po 1000 na 1000 element�w.
>
> Zainicjalizowane by�y losowymi liczbami.
>
> Program wykonywa� si� oko�o 100 sekund.
>
> Na tym samym sprz�cie odpali�em podobny
> program napisany w C, skompilowany gcc.
> gdy� robi� ciut wi�cej oblicze�. No i w C
> wykonywa�o to 70s.
>
> Wi�c to tylko plotki �e matlab jest taki wydajny?
Jak siďż˝ nie wie do czego Matlab jest przewidziany to potem siďż˝ robi
g�upie testy i niepoprawnie interpretuje wyniki. Matlab dobrze sobie
radzi z operacjami na macierzach, ale �le znosi p�tle (w ko�cu to j�zyk
interpretowany). Poza tym ile czasu sp�dzi�e� na pisaniu programu
w C i ile mu po�wi�cisz przy ewentualnej zmianie oblicze� wewn�trz
p�tli?
--
Secunia non olet.
Stanislaw Klekot
Mariusz Marszałkowski
<doz...@go.eat.some.screws.spammer.invalid> wrote:
> On 2010-01-18, Mariusz Marsza kowski <mmars...@gmail.com> wrote:
>
>
>
> > Od do dawna s ysz opinie e procedury zaimplementowane w
> > matlabie s bardzo wydajne. Nie znam matlaba, ale wczoraj przez
> > przypadek mia em go pod r k , no i tyle ile mo na si nauczy
> > przez godzin sprawdzi em.
>
> > Program w matlabie robi co takiego:
> > for i=1:20000
> > v = a * m1;
> > a = v * m2;
> > end;
>
> > m1 i m2 to macierze po 1000 na 1000 element w.
>
> > Zainicjalizowane by y losowymi liczbami.
>
> > Program wykonywa si oko o 100 sekund.
>
> > Na tym samym sprz cie odpali em podobny
> > program napisany w C, skompilowany gcc.
> > gdy robi ciut wi cej oblicze . No i w C
> > wykonywa o to 70s.
>
> > Wi c to tylko plotki e matlab jest taki wydajny?
>
> Jak si nie wie do czego Matlab jest przewidziany to potem si robi
> g upie testy i niepoprawnie interpretuje wyniki.
Naprawdę uważasz że matlab robi 20tys pętli przez ponad 30
sekund, czy robisz sobie jaja ze mnie?
Pozdrawiam
Stachu 'Dozzie' K.
><doz...@go.eat.some.screws.spammer.invalid> wrote:
>> On 2010-01-18, Mariusz Marsza kowski <mmars...@gmail.com> wrote:
>>
>>
>>
>> > Od do dawna s ysz opinie e procedury zaimplementowane w
>> > matlabie s bardzo wydajne. Nie znam matlaba, ale wczoraj przez
>> > przypadek mia em go pod r k , no i tyle ile mo na si nauczy
>> > przez godzin sprawdzi em.
>>
>> > Program w matlabie robi co takiego:
>> > for i=1:20000
>> > �a = v * m2;
>> > end;
>>
>> > Gdzie v i a to wektory double po 1000 element w, a
>> > m1 i m2 to macierze po 1000 na 1000 element w.
>> > Wi c to tylko plotki e matlab jest taki wydajny?
>>
>> Jak si nie wie do czego Matlab jest przewidziany to potem si robi
>> g upie testy i niepoprawnie interpretuje wyniki.
>
> sekund, czy robisz sobie jaja ze mnie?
Naprawd� testowa�e� Matlaba puszczaj�c co� kr�tkiego w d�ugiej p�tli czy
sobie jaja ze mnie robisz?
U�yj jakiego� czytnika news, bo pliterki rozpieprzasz.
Mariusz Marszałkowski
<doz...@go.eat.some.screws.spammer.invalid> wrote:
> On 2010-01-18, Mariusz Marszałkowski <mmars...@gmail.com> wrote:
>
>
>
> > On 18 Sty, 13:37, "Stachu 'Dozzie' K."
> ><doz...@go.eat.some.screws.spammer.invalid> wrote:
> >> On 2010-01-18, Mariusz Marsza kowski <mmars...@gmail.com> wrote:
>
> >> > Od do dawna s ysz opinie e procedury zaimplementowane w
> >> > matlabie s bardzo wydajne. Nie znam matlaba, ale wczoraj przez
> >> > przypadek mia em go pod r k , no i tyle ile mo na si nauczy
> >> > przez godzin sprawdzi em.
>
> >> > Program w matlabie robi co takiego:
> >> > for i=1:20000
> >> > end;
>
> >> > Gdzie v i a to wektory double po 1000 element w, a
> >> > m1 i m2 to macierze po 1000 na 1000 element w.
> [...]
> >> > Wi c to tylko plotki e matlab jest taki wydajny?
>
> >> Jak si nie wie do czego Matlab jest przewidziany to potem si robi
> >> g upie testy i niepoprawnie interpretuje wyniki.
>
> > sekund, czy robisz sobie jaja ze mnie?
>
> sobie jaja ze mnie robisz?
Dwukrotne mnożenie macierzy [1x100] * [1000x1000] używasz za coś
krótkiego? Przecież to 2mln mnożeń, 2mln dodawań i 2mln kopiowań
liczb podwójnej precyzji. Jakie znaczenie ma jedna pętla na 6mln
innych
operacji? Uważasz że w matlabie tak schrzanili ten język
interpretowany
że jena pętla działa wolniej niż 6mln operacji, bo pętla jest
interpretowana?
Ja matlabem nigdy się nie interesowałem i go nie znam, ale Ty to
chyba
masz zupełnie błędne wyobrażenie o nim i o programowaniu w ogóle.
> Użyj jakiegoś czytnika news, bo pliterki rozpieprzasz.
W tej kwestii pretensje do ludzi z google i(lub) fire fox.
Grzegorz Niemirowski
> > U�yj jakiego� czytnika news, bo pliterki rozpieprzasz.
> W tej kwestii pretensje do ludzi z google i(lub) fire fox.
Kto� Ci� zmusza do u�ywania Google?
--
Grzegorz Niemirowski
http://www.grzegorz.net/
OE PowerTool i Outlook Express: http://www.grzegorz.net/oe/
Uptime: 17 days, 20 hours, 34 minutes and 31 seconds
Mariusz Marszałkowski
wrote:
> Mariusz Marszałkowski <mmars...@gmail.com> napisał(a):
>
> > > Użyj jakiegoś czytnika news, bo pliterki rozpieprzasz.
> > W tej kwestii pretensje do ludzi z google i(lub) fire fox.
>
Najwyrazniej czytnik google taki dobry jak
matlab wydajny.
Krzysiek Kowaliczek
> Ja matlabem nigdy si� nie interesowa�em i go nie znam, ale Ty to
> chyba
> masz zupe�nie b��dne wyobra�enie o nim i o programowaniu w og�le.
Nie pomy�la�e�, �e Matlab ma *uniwersaln�* implementacj� mno�enia
macierzy? Wi�c nie dziw si�, �e twoja skrojona na miar� implementacja
jest szybsza.
Pozdrawiam
KK
Mariusz Marszałkowski
<krzysiek.kowaliczek.remov...@gmail.com> wrote:
> U ytkownik Mariusz Marsza kowski napisa :
>
> > Ja matlabem nigdy si nie interesowa em i go nie znam, ale Ty to
> > chyba
> > masz zupe nie b dne wyobra enie o nim i o programowaniu w og le.
>
> Nie pomy la e , e Matlab ma *uniwersaln * implementacj mno enia
> macierzy? Wi c nie dziw si , e twoja skrojona na miar implementacja
> jest szybsza.
Powiedzialbym ze nie jest szybsza, ale duzo szybsza. I nie jest
skrojona na miare, bo jak juz nadmienialem, moja procedura w C
realizuje troche inny algorytm , ale mnozenie takich samych dwoch
wektorow przez dwie macierze sa w niej czescia dominujaca. Stawiam
ze czas matlaba do jezya C i gcc jest jak 10:6 w tym tescie.
Dlaczego mam sie nie dziwic? Matlab chyba jest cholernie drogi?
Za te pieniadze chlopaki od matlaba z pewnoscia mieli mozliwosc
napisania stu wersji procedur mnozenia macierzy. Kazda wersje
na inna architekture i na inne rozmiary macierzy. Srodowisko za
takie pieniadze powinno rozpoznac jaki jest procesor, ile ma pamieci
cache, jakie sa rozmiary macierzy i wskoczyc do skrojonych
na miare i zoptymalizowanych na dana platforme procedur.
Pozdrawiam serdecznie
bartekltg
> Witam
>
> Od dość dawna słyszę opinie że procedury zaimplementowane w
> matlabie są bardzo wydajne. Nie znam matlaba, ale wczoraj przez
> przypadek miałem go pod ręką, no i tyle ile można się nauczyć
> przez godzinę sprawdziłem.
>
> Program w matlabie robił coś takiego:
> for i=1:20000
> v = a * m1;
> a = v * m2;
> end;
U mnie 520 (tzn petla do 2000 zajela 52).
Natomiast rownowazne
tic;a=a*(m1*m2)^(20000-1); v = a * m1; a = v * m2; toc
zajelo 50s. Czyli 10 razy mniej:)
> gdyż robił ciut więcej obliczeń. No i w C
> wykonywało to 70s.
100 do 70? cos mierna ta roznica.
> Więc to tylko plotki że matlab jest taki wydajny?
Po pierwsze, porownaj powazne procedury. Chocby mnozenie maciezy.
Po drugie, czy matlab w tym miejscy nie korzysta z c blas/lapack?
Ze napisales ogolne procedury wydajniejsze - nie wierze;)
Sprawa zapewne rozbija sie o lepsze uzycie procesora,
programiki z c je wykorzystuje, matlab raczej nie
(czy daja wersje pod rozne procesory, nie wiem, moj jest uczelniany
i bebecham malo mnie obchodza, ale watpie).
Skontaktuj sie z nimi i zapytaj o podiane bibliotek na superprocek.
Po trzecie. Wydajnosc matlaba to sprawa drugorzedna. 70% to
niezly wynik. Procedura quad (adaptatywne calkowanie simpsonem),
gdy uzyjesz jej na niedrogiej obliczeniowo funkcji bedzie koszmarnie
wolna w porownaniu do jakiegokolwiek jezyka kompilowanego*).
Matlab to taka pierwsza linia frontu:) Mozesz sobie poeksperymentowac,
wszytko masz pod reka, a jesli dane do obliczen/symulacji/obrobki
beda duze i zalezec Ci bedzie na tym czynniku rzedu 2, posiedzisz
dwa tygodnia lub miesiace i napiszesz to w c/c++/fortranie.
pozdrawiam
bartekltg
*) kolezanka sie na to naciela. Wynika to oczywiscie ze skryptowosci,
w kazdym kroku procedura liczy wartosci funkcji w jedynie 3 (a moze
pieciu) punktach i za kazdym razem ciagnie za soba cala nadbudowe
(sprawdzanie rodzaju funkcji i poprawnosci wyrazenia..).
Na szybko napisalismy romberga (kilkanascie linijek, grubo 20 minut)
i dalo sie pracowac.
Wiktor S.
Mnie zastanawia, jakie sa zastosowania, w kt�rych sie faktycznie OPLACA
wybulic TAKI majatek na Matlaba... bo jakies chyba sa, skoro program zyje?
--
Azarien
Mariusz Marszałkowski
> On 18 Sty, 13:15, Mariusz Marszałkowski <mmars...@gmail.com> wrote:
>
> > Witam
>
> > Od dość dawna słyszę opinie że procedury zaimplementowane w
> > matlabie są bardzo wydajne. Nie znam matlaba, ale wczoraj przez
> > przypadek miałem go pod ręką, no i tyle ile można się nauczyć
> > przez godzinę sprawdziłem.
>
> > Program w matlabie robił coś takiego:
> > for i=1:20000
> > v = a * m1;
> > a = v * m2;
> > end;
>
> U mnie 520 (tzn petla do 2000 zajela 52).
> Natomiast rownowazne
> tic;a=a*(m1*m2)^(20000-1); v = a * m1; a = v * m2; toc
>
> zajelo 50s. Czyli 10 razy mniej:)
czasu do 6mln operacji. Może matlab użył innego algorytmu?
Albo czegos nie zrozumialem....
> > gdyż robił ciut więcej obliczeń. No i w C
> > wykonywało to 70s.
>
> 100 do 70? cos mierna ta roznica.
>
> > Więc to tylko plotki że matlab jest taki wydajny?
>
> Po pierwsze, porownaj powazne procedury. Chocby mnozenie maciezy.
Nie rozumie, a co ja porównałem jak nie mnożenie macierzy?
> Po drugie, czy matlab w tym miejscy nie korzysta z c blas/lapack?
> Ze napisales ogolne procedury wydajniejsze - nie wierze;)
Napisałem wydajniej to co opisałem: mnożenie macierzy o
rozmiarze Nx1 przez macierz MxN. Super wydajny pakiet powinien
mieć specjalną implementację do takich macierzy.
> Sprawa zapewne rozbija sie o lepsze uzycie procesora,
> programiki z c je wykorzystuje, matlab raczej nie
> (czy daja wersje pod rozne procesory, nie wiem, moj jest uczelniany
> i bebecham malo mnie obchodza, ale watpie).
Też mnie to nie bardzo obchodzi, ale od co najmniej roku slysze
ze matlab jest baaardzo wydajny i jak uzyje jego procedur to
bede mail szybsze niz swoje. A tu prosze, podstawowa procedura i
jest prawie dwa razy wolniej. Nie bawilem sie opcjami gcc, moze by
wyszlo ponad dwa razy. Slyszalem nawet ze matlab wykorzystuje
CUDA, a na tamtym kompie byla karta grafiki z ta technologia.
> Skontaktuj sie z nimi i zapytaj o podiane bibliotek na superprocek.
Nie chce mi sie, pokazalem ze na najprostszym przykladzie radzi
sobie gorzej, wiec dlaczego mam dawac waire ze na zaawansowanych
procedurach radzi sobie lepiej?
> Po trzecie. Wydajnosc matlaba to sprawa drugorzedna. 70% to
> niezly wynik.
To inna sprawa z ktora sie zgadzam. Po prostu czesto mnie
zasypywano informacjami o super wydajnosci matlaba, a teraz
wiem ze wydajnosc raczej ma przecietna.
> Matlab to taka pierwsza linia frontu:) Mozesz sobie poeksperymentowac,
> wszytko masz pod reka, a jesli dane do obliczen/symulacji/obrobki
> beda duze i zalezec Ci bedzie na tym czynniku rzedu 2, posiedzisz
> dwa tygodnia lub miesiace i napiszesz to w c/c++/fortranie.
Z tym sie tez zawsze zgadzalem, to inna sprawa.
Pozdrawiam serdecznie
Grzegorz Niemirowski
> Mnie zastanawia, jakie sa zastosowania, w kt�rych sie faktycznie OPLACA
> wybulic TAKI majatek na Matlaba... bo jakies chyba sa, skoro program zyje?
Matlab ma pierdyliard funkcji, sporo zastosowaďż˝ siďż˝ znajdzie :)
--
Grzegorz Niemirowski
http://www.grzegorz.net/
OE PowerTool i Outlook Express: http://www.grzegorz.net/oe/
Uptime: 0 days, 1 hours, 6 minutes and 21 seconds
Mariusz Marszałkowski
> > Dlaczego mam sie nie dziwic? Matlab chyba jest cholernie drogi?
>
> wybulic TAKI majatek na Matlaba... bo jakies chyba sa, skoro program zyje?
>
Nie wiem... może są, może nie ma... Dziś do jednego zadania czesto
istnieje
dużo rozwiązań, od darmowych po cholernie drogie, albo wrecz po pisane
specjalnie
na zamowienienie. Ciekzko powiedziec obiektywnie w jakim stopniu zycie
drogich pakietow zalezy od niewiedzy klientow, a w jakim od
faktyczniej
przydatnosci i braku alternatywnego taniszego rozwiazania. Zycie
pokazuje
ze dobry i tani produkt moze umrzec z powodu zlego marketingu, a
kiepski i
drogi moze przynosic zyski dzieki dobrej reklamie.
Pozdrawiam
Michoo
>
>> Po trzecie. Wydajnosc matlaba to sprawa drugorzedna. 70% to
>> niezly wynik.
> To inna sprawa z ktora sie zgadzam. Po prostu czesto mnie
> zasypywano informacjami o super wydajnosci matlaba, a teraz
> wiem ze wydajnosc raczej ma przecietna.
Napisz teraz to samo mno�enie macierzy w javie i por�wnaj wyniki. Oka�e
si�, �e matlab jest wyj�tkowo szybki. ;)
--
Pozdrawiam
Michoo
Wiktor S.
>> OPLACA wybulic TAKI majatek na Matlaba... bo jakies chyba sa, skoro
>> program zyje?
> Matlab ma pierdyliard funkcji, sporo zastosowaďż˝ siďż˝ znajdzie :)
Ale nie za fafdziesi�t tysi�cy... no chyba �e piracimy, wtedy tak.
--
Azarien
bartekltg
> Niemożliwe aby jedna pętla zajmowała porównywalną ilość
> czasu do 6mln operacji. Może matlab użył innego algorytmu?
> Albo czegos nie zrozumialem....
Tak, liczymy to inaczaj. Macierz potegowana jest matoda
binarna. Obliczenia k tej potegi zajmuje cos rzedu log_2 k
mnozej naszych kwadratowych macierzy n*n. (chyba 3log k)
Czyli mamy n^3 *log k + nieistotne
Dla duzych k moze byc to szybsze niz Twoja metoda,
czyli k*n^2.
[i tu znow wychodzi glowna zaleta takich pakietow, napisanie
tego uzywajac np BLAS'a zajelo by chwile, jesli nie masz w tej
bibliotece wprawy, nie mowiac juz o napisanie calosci samemu.]
> Nie rozumie, a co ja porównałem jak nie mnożenie macierzy?
Porownales wektor * macierz. Ja zastanawialem sie nad porownaniem
mnozenia 2 macierzy kwadratowych (i nieco wiekszych niz 1000).
> Napisałem wydajniej to co opisałem: mnożenie macierzy o
> rozmiarze Nx1 przez macierz MxN. Super wydajny pakiet powinien
> mieć specjalną implementację do takich macierzy.
A nie jest to wydajne? Masz czas tego samego rzedu co w jezyku
kompilowalnym (i to skompilowanem pod swoj system i procek!).
Chcesz z maksymalna moca swojego komputera robic ceizkie
obliczenia gdzie te 30% jest istotne.. chyba bedzie trzeba
zatrudnic programiste. Albo doktoranta:)
A skad te glosy ze jest super wydajne? Moze od ludzi,
ktorzy robili to w Ja.. jakims podejrzanym jezyku skryptowym
bez uzycia bilioteki. Albo od ludzi, ktorym mnozenie macierzy
pisal ow doktorant:)
Porownalem z pythonem i bibliotekami numpy i scipy,
mnozenie 2 macierzy. Wyniki identyczne jak w matlabie.
BTW, rozumeim, ze pusciels oba parokrotnie i porownales
najlepszy z najlepszym.
> > Sprawa zapewne rozbija sie o lepsze uzycie procesora,
> > programiki z c je wykorzystuje, matlab raczej nie
> > (czy daja wersje pod rozne procesory, nie wiem, moj jest uczelniany
> > i bebecham malo mnie obchodza, ale watpie).
>
> Też mnie to nie bardzo obchodzi, ale od co najmniej roku slysze
> ze matlab jest baaardzo wydajny i jak uzyje jego procedur to
> bede mail szybsze niz swoje. A tu prosze, podstawowa procedura i
> jest prawie dwa razy wolniej. Nie bawilem sie opcjami gcc, moze by
Moze rzeczywiscie pisali mnozenie macierzy w javie;)
A jestes pewien, ze niewielkim nakladem pracy zbudujesz dobry
algorytm numeryczny. Wydajne PCG dla macierzy rzadkich,
roznego rodzaju rozklady, czy uniwersalna szukaczke minimow.
To, ze podstawowe operacje sa ciut wolniejsze nie oznacza,
ze osoba majaca kontakt z numeryka tylko przy okazji
napisze szybszy kod.
> wyszlo ponad dwa razy. Slyszalem nawet ze matlab wykorzystuje
> CUDA, a na tamtym kompie byla karta grafiki z ta technologia.
Podejrzewam, ze trzeba mu kazac (byc moze sa to osobne funkcje).
I miec wersje (toolboxa?) pozwalajaca na to.
> > Skontaktuj sie z nimi i zapytaj o podiane bibliotek na superprocek.
>
> Nie chce mi sie, pokazalem ze na najprostszym przykladzie radzi
> sobie gorzej, wiec dlaczego mam dawac waire ze na zaawansowanych
> procedurach radzi sobie lepiej?
Szczerze mowiac, wybrales zagadneinie nad ktorym srednio sie
pochylali. Patrz koniec postu.
A bardziej zaawansowane algorytmy to cos wiecej niz dwie/trzy petle.
Jak chesz naprawde porownac matlaba i swoj kod, zrob to
na czyms powazniejszym, LUP (wbudowana), znajdowanie
wektortow wlasnych (wbudowana, cholski i QZ) albo PCG (skrypt).
Pewnie da sie napisac w c szybiej (trzecia na pewno;))
zwlaszcza na konkretny procek, ale wymagac bedzie juz odrobiny
wysilku.
> > Po trzecie. Wydajnosc matlaba to sprawa drugorzedna. 70% to
> > niezly wynik.
>
> To inna sprawa z ktora sie zgadzam. Po prostu czesto mnie
> zasypywano informacjami o super wydajnosci matlaba, a teraz
> wiem ze wydajnosc raczej ma przecietna.
Ja nadal uwazam, ze jesli pakiet numeryczny daje ten sam rzad
wielkosci, to jest przyzwoity wynik.
W miare mozliwosci (trzeba napisac) zrob to porownanie przy mnozeniu
dwuch macierzy 1000x1000. Roznica powinna sie znacznie zmniejszyc.
Przy okazji:
Zrobilem tez prosty test. Macierz 1000x1000 mnoze przez
256 wektorow, ale na rozne sposoby. Mnoze 2^j razy paczki
po 256/2^j wektorow.
a=rand(1000);
t=[];
for j=8:-1:2,
v=rand(2^(8-j),1000);
tic;
for k=1:2^j,
v*a;
end;
t=[t;toc];
end;
Wyniki:
petli wektorow w pakiecie czas
256 1 3.6121
128 2 2.2496
64 4 1.3139
32 8 0.80334
16 16 0.65687
8 32 0.53299
4 64 0.5166
Za kazdym razem mnozylismy tyle samo wektorow.
Sredni czas na wektor dosc mocno spadal, jesli robilismy
to na raz. Przyszpieszylismy szesciokrotnie!
Teraz zaczynam sie dziwic, dlaczego Twoj program
byl tylko niecale dwa raza szybszy (jemu wszytko jedno
czy mnozymy po koleji, czy hurtem).
pozdrawiam
bartekltg
bartekltg
> >> Mnie zastanawia, jakie sa zastosowania, w których sie faktycznie
> >> OPLACA wybulic TAKI majatek na Matlaba... bo jakies chyba sa, skoro
> >> program zyje?
>
> Ale nie za fafdziesiąt tysięcy... no chyba że piracimy, wtedy tak.
A moze uzyc dosc czestego tu argumentu z watków
'czemu nikt nie pisze wydfajengo oprogramowania'
Mamy jajoglowego. Jego praca tez cos kosztuje.
Lepiej, aby marnowal czas babrzac sie w kodowanie
po raz n-ty w skali swiata algorytmu kogostam-kogostam,
wynajac programiste*), czy kupic mu narzedzie, ktore
jest znacznie prostrze (nie mowie prostrze, ale jajoglowy
to sie nauczy) a zaoszczedzi czas na grzebanie sie
nie tam gdzie trzeba.
*) jesli bawimy sie w symulowanie, modelowanie etc
na odpowiednim pozioime, to i oni beda konieczni,
ale na etapie posrednim bardziej przydaje sie ktos
obaznany z numeryka, a i wtedy ma raczej myslec
nad algorytmami a nie bawic sie w kodowanie.
pozdrawiam
bartekltg
Mariusz Marszałkowski
> On 18 Sty, 20:26, Mariusz Marszałkowski <mmars...@gmail.com> wrote:
>
> > Nie rozumie, a co ja porównałem jak nie mnożenie macierzy?
>
> Porownales wektor * macierz. Ja zastanawialem sie nad porownaniem
> mnozenia 2 macierzy kwadratowych (i nieco wiekszych niz 1000).
Nie wiem czy się skuszę (mam masę innych rzeczy do testowana) na
taki test, ale może... Nie znam tego algorytmu który ma mniejszą
złożoność niż N^3. Obecnie jakie jest dokładne teoretyczne
ograniczenie?
Może jakbym miał przystępnie opisany ten algorytm to bym napisał w
gołym C.
Zapodajcie linka do dobrego algorytmu, może spróbuję.
> > Napisałem wydajniej to co opisałem: mnożenie macierzy o
> > rozmiarze Nx1 przez macierz MxN. Super wydajny pakiet powinien
> > mieć specjalną implementację do takich macierzy.
>
> A nie jest to wydajne? Masz czas tego samego rzedu co w jezyku
> kompilowalnym (i to skompilowanem pod swoj system i procek!).
Zależy jak oceniać. Słyszałem opinie z których wynikało że
matlab to wszystko robi z 50 razy szybciej. W świetle tamtych
opinii wypadł śmiesznie, i głównie to chciałem sprawdzić. A
czy jest 2 razy szybszy czy 2 razy wolniejszy to osobiście
zgadzam się że nie powód do oceniania pakietu. Chciałem się
tylko upewnić czy nie jest 50 razy lepszy :)
> Chcesz z maksymalna moca swojego komputera robic ceizkie
> obliczenia gdzie te 30% jest istotne.. chyba bedzie trzeba
> zatrudnic programiste. Albo doktoranta:)
Przy jednym z moich projektów miesięczny rachunek za energię
na komputery liczące to około 1000zł. Dużo nie brakuje aby
starczyło na wypłatę dla nastepnego programisty...
> A skad te glosy ze jest super wydajne? Moze od ludzi,
> ktorzy robili to w Ja.. jakims podejrzanym jezyku skryptowym
> bez uzycia bilioteki. Albo od ludzi, ktorym mnozenie macierzy
> pisal ow doktorant:)
Właśnie od różnych ludzi i z różnych środowisk, w
końcu mnie sprowokowali.
> BTW, rozumeim, ze pusciels oba parokrotnie i porownales
> najlepszy z najlepszym.
Tak. Właściwie mój brat jeszcze zaczął kompilować projekt w
gcc z różnymi opcjami aby jeszcze przyspieszyć, ale już
nic nie pomagało.
> Moze rzeczywiscie pisali mnozenie macierzy w javie;)
Sadze ze w ogole nie pisali i w ogole nie porownywali czasow,
tylko ulegli marketingowi matlaba.
> A jestes pewien, ze niewielkim nakladem pracy zbudujesz dobry
> algorytm numeryczny. Wydajne PCG dla macierzy rzadkich,
> roznego rodzaju rozklady, czy uniwersalna szukaczke minimow.
Niewielkim to niemozliwe, no chyba ze znam algorytm i juz
kiedys go implementowalem.
> Podejrzewam, ze trzeba mu kazac (byc moze sa to osobne funkcje).
> I miec wersje (toolboxa?) pozwalajaca na to.
Nie wiem, mozliwe.
> > > Skontaktuj sie z nimi i zapytaj o podiane bibliotek na superprocek.
>
> > Nie chce mi sie, pokazalem ze na najprostszym przykladzie radzi
> > sobie gorzej, wiec dlaczego mam dawac waire ze na zaawansowanych
> > procedurach radzi sobie lepiej?
>
> Szczerze mowiac, wybrales zagadneinie nad ktorym srednio sie
> pochylali. Patrz koniec postu.
Ale mogil sie postarac a wrecz powinni. Wystarczy rozpoznac
ze mnozymy wektor przez macierz i dac goto do wyspecjalizowanej
procedurki. Tak samo jesli mnozymy macierz [NxK] przez [KxM] dla
M i N znacznie wiekszych niz K, to jakas wyspecjalizowana procedura
wymnozylaby duzo szybciej niz ogolna.
> A bardziej zaawansowane algorytmy to cos wiecej niz dwie/trzy petle.
> Jak chesz naprawde porownac matlaba i swoj kod, zrob to
> na czyms powazniejszym, LUP (wbudowana), znajdowanie
> wektortow wlasnych (wbudowana, cholski i QZ) albo PCG (skrypt).
> Pewnie da sie napisac w c szybiej (trzecia na pewno;))
> zwlaszcza na konkretny procek, ale wymagac bedzie juz odrobiny
> wysilku.
Zgadza sie, nigdy temu nie zaprzeczalem.
> Ja nadal uwazam, ze jesli pakiet numeryczny daje ten sam rzad
> wielkosci, to jest przyzwoity wynik.
Ja tez tak podejrzewam, ale teraz tez wiem ze nie ma
implementacji 50 razy wydajniejszych.
> W miare mozliwosci (trzeba napisac) zrob to porownanie przy mnozeniu
> dwuch macierzy 1000x1000. Roznica powinna sie znacznie zmniejszyc.
Nie obiecuje, ale sprobuje, tylko zapodajcie dobry opis algorytmu,
nigdy
nie implementowalem lepszego algorytmu mnozenia macierzy.
Może mieć algorytm o lepszej zlozonosci niż N^3 i
jego moc się nie ujawnia gdy mnozymy macierze
podobne do wierszowych.
Pozdrawiam serdecznie
Maciej Pilichowski
<wswiktor&poczta,f...@no.spam> wrote:
>> Matlab ma pierdyliard funkcji, sporo zastosowań się znajdzie :)
>
>Ale nie za fafdziesi±t tysięcy... no chyba że piracimy, wtedy tak.
To zalezy ile pakietow sobie dokupisz. Matlab edu to koszt az 400
zlotych bodajze. Bez przesady.
milego dnia, hej
Mariusz Marszałkowski
> Mariusz Marszałkowski pisze:
>
>
>
> >> Po trzecie. Wydajnosc matlaba to sprawa drugorzedna. 70% to
> >> niezly wynik.
> > To inna sprawa z ktora sie zgadzam. Po prostu czesto mnie
> > zasypywano informacjami o super wydajnosci matlaba, a teraz
> > wiem ze wydajnosc raczej ma przecietna.
>
> się, że matlab jest wyjątkowo szybki. ;)
Gdy testowałem ostatnio wydajnosc javy, to czesto czasy wykonania
na "czesciach obliczeniowych" algorytmu nie roznily sie w ogole od C+
+.
Szczegolnie na architekturze 64-bitowej java rzadko odstaje od C++.
Przez czesci obliczeniowe rozumiem cos takiego, gdzie w petetlach
sa wykonywane obliczenia arytmetyczono logiczne. Gdy sie pojawia
wywolywanie duzej ilosci metod do dopiero java wyraznie traci.
Pozdrawiam
Wiktor S.
>>
>> Ale nie za fafdziesi±t tysięcy... no chyba że piracimy, wtedy tak.
>
> To zalezy ile pakietow sobie dokupisz.
Interesowały mnie bilbioteki do projektowania filtrów cyfrowych.
> Matlab edu to koszt az 400 zlotych bodajze. Bez przesady.
edu mnie "nie urządza".
--
Azarien
Adam Przybyla
w toolkitach do specjalizowanych obliczen z danych dziedzin.
Z powazaniem
Adam Przybyla
Maciej Pilichowski
<wswiktor&poczta,f...@no.spam> wrote:
>Interesowały mnie bilbioteki do projektowania filtrów cyfrowych.
Czyli ograniczony zakres.
>> Matlab edu to koszt az 400 zlotych bodajze. Bez przesady.
>
>edu mnie "nie urządza".
Wiesz, jezeli bedziesz zarabial na tym, to i bedzie Cie stac, zeby
dodac jedno zero na koniec kwoty. Poza tym bez przesady -- rownie
kosztowne sa pelne wersje softu bylego Borlanda, czy Microsoftu.
milego dnia, hej
thrunduil
> Program wykonywał się około 100 sekund.
>
> Na tym samym sprzęcie odpaliłem podobny
> program napisany w C, skompilowany gcc.
> Program w C był podobny, a nie taki sam,
> gdyż robił ciut więcej obliczeń. No i w C
> wykonywało to 70s.
>
> Więc to tylko plotki że matlab jest taki wydajny?
bardzo chcialbym zobaczyc ten kod. Jakos nie wierze, ze ad hoc
napisany kod mnozenia macierzy jest szybszy od MKLa.
Nie zapomniales przypadkiem o jednym zerze w petli w kodzie C?
Mariusz Marszałkowski
Wręcz przeciwnie. Kod w C tak naprawdę przeliczał ogromną
sztuczną sieć neuronową, więc macierze w C były o jeden
element większy i dodatkowo obliczał funkcję: 2/( 1 + exp( -x ) ) - 1.
Ale oczywiście mogłem się gdzieś pomylić, nie mam kodu na
tym komputerze, poproszę żeby mi przysłali i go wkleję.
Pozdrawiam
bartekltg
> On 19 Sty, 02:52, bartekltg <bartek...@gmail.com> wrote:
>
> > On 18 Sty, 20:26, Mariusz Marszałkowski <mmars...@gmail.com> wrote:
>
> > > Nie rozumie, a co ja porównałem jak nie mnożenie macierzy?
>
> > Porownales wektor * macierz. Ja zastanawialem sie nad porownaniem
> > mnozenia 2 macierzy kwadratowych (i nieco wiekszych niz 1000).
>
> Nie wiem czy się skuszę (mam masę innych rzeczy do testowana) na
> taki test, ale może... Nie znam tego algorytmu który ma mniejszą
> złożoność niż N^3. Obecnie jakie jest dokładne teoretyczne
> ograniczenie?
Coppersmitha-Winograda daje n^2.376, ale stala jest tak duza,
za na razie komputery nie bawia sie takimi macierzami pelnymi.
Niby mozna uzywac algorytmu Strassena (n^log_2 7 = log^2.807),
ale ma on klopoty z numeryczna stabilnoscia. Blas uzywa n^3
(jeszcze do tego wroce).
> Może jakbym miał przystępnie opisany ten algorytm to bym napisał w
> gołym C.
> Zapodajcie linka do dobrego algorytmu, może spróbuję.
http://en.wikipedia.org/wiki/Strassen_algorithm
ale IHMO nie ma sensu n^3 starczy.
> > > Napisałem wydajniej to co opisałem: mnożenie macierzy o
> > > rozmiarze Nx1 przez macierz MxN. Super wydajny pakiet powinien
> > > mieć specjalną implementację do takich macierzy.
>
> > A nie jest to wydajne? Masz czas tego samego rzedu co w jezyku
> > kompilowalnym (i to skompilowanem pod swoj system i procek!).
>
> Zależy jak oceniać. Słyszałem opinie z których wynikało że
> matlab to wszystko robi z 50 razy szybciej. W świetle tamtych
http://ubuntuforums.org/archive/index.php/t-1295370.html
:)
> opinii wypadł śmiesznie, i głównie to chciałem sprawdzić. A
> czy jest 2 razy szybszy czy 2 razy wolniejszy to osobiście
> zgadzam się że nie powód do oceniania pakietu. Chciałem się
> tylko upewnić czy nie jest 50 razy lepszy :)
50 na dzien dobry brzmi smiesznie.
Ale nadal bede mowic, ze sprawdziles to dla
danych nieso spoza zakresu w ktorym matlab jest dobry.
> Przy jednym z moich projektów miesięczny rachunek za energię
> na komputery liczące to około 1000zł. Dużo nie brakuje aby
> starczyło na wypłatę dla nastepnego programisty...
Teraz polowe zaoszczedzisz.. Student na pol etatu na to pojdzie?
> Właśnie od różnych ludzi i z różnych środowisk, w
> końcu mnie sprowokowali.
Skoro sprowokowali, to zrob uczciwy test na duzych
maciezach a nie pitu-pitu wektorkami po 1000 elementow:)
> > Moze rzeczywiscie pisali mnozenie macierzy w javie;)
>
> Sadze ze w ogole nie pisali i w ogole nie porownywali czasow,
> tylko ulegli marketingowi matlaba.
:)
> Ale mogil sie postarac a wrecz powinni. Wystarczy rozpoznac
> ze mnozymy wektor przez macierz i dac goto do wyspecjalizowanej
> procedurki. Tak samo jesli mnozymy macierz [NxK] przez [KxM] dla
> M i N znacznie wiekszych niz K, to jakas wyspecjalizowana procedura
> wymnozylaby duzo szybciej niz ogolna.
Dla bardzo malych K mozna by sie bawic w rozwijanie petli.
Dla wiekszych - nie ma znaczenia przy algorytmie n^3.
> > Ja nadal uwazam, ze jesli pakiet numeryczny daje ten sam rzad
> > wielkosci, to jest przyzwoity wynik.
>
> Ja tez tak podejrzewam, ale teraz tez wiem ze nie ma
> implementacji 50 razy wydajniejszych.
Za to sa 50razy mniej wydajne;)
> > W miare mozliwosci (trzeba napisac) zrob to porownanie przy mnozeniu
> > dwuch macierzy 1000x1000. Roznica powinna sie znacznie zmniejszyc.
>
> Nie obiecuje, ale sprobuje, tylko zapodajcie dobry opis algorytmu,
> nigdy
> nie implementowalem lepszego algorytmu mnozenia macierzy.
> Może mieć algorytm o lepszej zlozonosci niż N^3 i
> jego moc się nie ujawnia gdy mnozymy macierze
> podobne do wierszowych.
Nie. Matlab, (mimo mojego natkniecia sie na informacje,
ze jednak) nie korzysta z szybszych algorytmow
(przynajmniej dla macierzy rzedu 1000-2000).
Dowod literaturowy. Matlab korzysta z BLASa jako
silnika do operacji na macierzach:
http://www.mathworks.com/access/helpdesk/help/techdoc/ref/mtimes.html
[*]
Wiki gdzies wsponilala, ze BLAS uzywa dla duzych macierzy jakios
modyfikacji
Strassena, jadnak w kodzie tego nie widac:
http://www.netlib.org/blas/dgemm.f (macierz macierz).
Dowod statystyczny (12 macierzy o wielkosciach ciut ponizej 1000 do
ok2000):
wyn=[];for j=95:110; n=floor(2^(j/10)); a=rand(n); b=rand(n);
tic;a*b;wyn=[wyn;n,toc], end;
plot(log(wyn(:,1)),log(wyn(:,2)),'*' ) %poogladajmy sobie
[s,serr]=lscov([x,ones(size(x))],y)
Czas algorytmu to n^k hdzie k= 2.99 +- 0.06
Wiec n^3. Przynajmniej nie bede sie bac o stabilnosc numeryczna.
Jednak polecam napisanie tego n^3 i porownaine z matlabem.
Moze ci 'z roznych srodowisk' nie mylili sie tak bardzo
i kombajn bedize szybszy od napredce zmajstrowanego
programiku (pomijajac wspolczynnik 50 wziety z sufitu;)
pozdrawiam
bartekltg
[*] z tego linku wynika tez, ze jednak uzywa dgemv, czyli
specjalizowanej procedury macierz-wektor.
Czyzby 1000 bylo nadl tam mala liczba.
Moze porwnajmy monzenie M_kxn * wektor_n
gdzie n rzedu 10^6 a k rzedu kilkadziesiat.
thrunduil
> Wręcz przeciwnie. Kod w C tak naprawdę przeliczał ogromną
> sztuczną sieć neuronową, więc macierze w C były o jeden
> element większy i dodatkowo obliczał funkcję: 2/( 1 + exp( -x ) ) - 1.
>
> Ale oczywiście mogłem się gdzieś pomylić, nie mam kodu na
> tym komputerze, poproszę żeby mi przysłali i go wkleję.
To jest w zasadzie niemozliwe. Kod mnozenia macierzy jest bardzo
zlozony. Bez naprawde dobrze stuningowanego memory use, wstaweg
asemblerowych
i dlugiego testowania parametrow optymalizacyjnych nie ma szans na
zblizenie sie do wydajnosci Matlaba. Istnieja szybsze implementacje
mnozenia macierzy,
np GOTO blas jest ok 10% szybszy, ale i tak to jest w zasadzue
technologiczny limit na dzisiaj.
Kod Matlabla (tj bibliteka MKL, matlab nie napisal tego kodu sam)
jest o rzad wielkosci szybszy od dobrze stuningowanego kodu w C.
Wit Jakuczun
> > Ale mogil sie postarac a wrecz powinni. Wystarczy rozpoznac
> > ze mnozymy wektor przez macierz i dac goto do wyspecjalizowanej
> > procedurki. Tak samo jesli mnozymy macierz [NxK] przez [KxM] dla
> > M i N znacznie wiekszych niz K, to jakas wyspecjalizowana procedura
> > wymnozylaby duzo szybciej niz ogolna.
>
> Dla bardzo malych K mozna by sie bawic w rozwijanie petli.
> Dla wiekszych - nie ma znaczenia przy algorytmie n^3.
>
Może to rzuci jakieś światło na całą dyskusję (slaj 16ty):
http://www-users.mat.uni.torun.pl/~bala/wyklad_arch/wshop2000.pdf
Złożoność ciągle jest N^3 ale działa szybciej niż pętelki.
Blokowe mnożenie wykorzystuje ATLAS. Idea jest taka, żeby
cache maskymalnie efektywnie wykorzystać.
Ja kiedyś robiłem porównania ATLAS vs ręczny kod i ATLAS był
dużo szybszy. Z tego co pamiętam to oprócz mnożenia rozwiązywałem
układy równań.
Pozdrawiam,
Wit Jakuczun
Wit Jakuczun
bartekltg
> To jest w zasadzie niemozliwe. Kod mnozenia macierzy jest bardzo
Nie mow za wczesnie niemozliwe, bo pozniej trzeba bedzie odkrecac:)
U mnie dzieje sie to samo, przy parametrach jakie podal Mariusz
mnozenia te nie sa robione zbyt wydajnie.
> zlozony. Bez naprawde dobrze stuningowanego memory use, wstaweg
> asemblerowych
> i dlugiego testowania parametrow optymalizacyjnych nie ma szans na
> zblizenie sie do wydajnosci Matlaba. Istnieja szybsze implementacje
> mnozenia macierzy,
> np GOTO blas jest ok 10% szybszy, ale i tak to jest w zasadzue
> technologiczny limit na dzisiaj.
> Kod Matlabla (tj bibliteka MKL, matlab nie napisal tego kodu sam)
> jest o rzad wielkosci szybszy od dobrze stuningowanego kodu w C.
Dwie rownowazne operacje (1000 wektorow mnozymy przez macierz 1000 na
1000),
tylko raz w petli, a raz zwijamy w paczuszke. Jak wynikalo z
sasiedniego
postu, algorytm jest ten sam bo matlab korzysta z n^3.
>> tic;a*b;toc
Elapsed time is 2.585347 seconds.
>> tic,for j=1:1000,a*v;end;toc
Elapsed time is 15.379616 seconds.
No to sie okazuje, ze narzut matlaba dla niewielkich wektorkow jest
spory.
Intelowski BLAS pokazuje skrzydla dopiero dla konkretnej ilosci
danych.
Sam uwzam, ze nie jest to szczegolnie uciezliwe, nie zdarzylo mi sie
na to narzekac, to nadal malutkie macierze a mnozyc ciagle
wektor chce raczej przez macierz rzadka (a wektor ma megabajty)
ale moge sobie wyobrazic zagadnienia, gdzie taka operacja bedzie
dominujaca.
pozdrawiam
bartekltg
bartekltg
Zgoda. Ale to nadal ten sam algorytm, wykonuje sie dokaldnie te same
mnozenie, jedynie w rozsadniejszej dla procesora kolejnosci.
> http://www.mimuw.edu.pl/~przykry/matmult.php
Szkoda, ze nie wiedzialem;)
pozdrawiam
bartekltg
Wit Jakuczun
> > Może to rzuci jakieś światło na całą dyskusję (slaj 16ty):http://www-users.mat.uni.torun.pl/~bala/wyklad_arch/wshop2000.pdf
> > Złożoność ciągle jest N^3 ale działa szybciej niż pętelki.
> > Blokowe mnożenie wykorzystuje ATLAS. Idea jest taka, żeby
> > cache maskymalnie efektywnie wykorzystać.
> > Ja kiedyś robiłem porównania ATLAS vs ręczny kod i ATLAS był
> > dużo szybszy. Z tego co pamiętam to oprócz mnożenia rozwiązywałem
> > układy równań.
>
> Zgoda. Ale to nadal ten sam algorytm, wykonuje sie dokaldnie te same
> mnozenie, jedynie w rozsadniejszej dla procesora kolejnosci.
>
Czyli nie ten sam :). Teoretyczna złożoność taka sama ale praktycznie
to są różne algorytmy.
> >http://www.mimuw.edu.pl/~przykry/matmult.php
>
> Szkoda, ze nie wiedzialem;)
>
Ja wiedziałem ale to wiele nie zmieniło... :D
Pozdrawiam,
Wit Jakuczun
bartekltg
> Czyli nie ten sam :). Teoretyczna złożoność taka sama ale praktycznie
> to są różne algorytmy.
Nie tylko zlozonosc. Nawet ilosc operacji mnozenia doubli
taka sama:)
> > >http://www.mimuw.edu.pl/~przykry/matmult.php
>
> > Szkoda, ze nie wiedzialem;)
>
> Ja wiedziałem ale to wiele nie zmieniło... :D
Popatrzylem na najszybszy kod. Odechcailo mi sie:)
pozdrawiam
bartekltg
thrunduil
> U mnie dzieje sie to samo, przy parametrach jakie podal Mariusz
> mnozenia te nie sa robione zbyt wydajnie.
Co to znaczy, ze nie sa robione zbyt wydajnie?
MKL jest pisany tak, zeby byc bardzo optymalnym juz przy macierzach
rzedu 30x30.
To jest blisko dolnego limitu wielkosci blokow wykorzystywanych w
Lapacku u musi byc optymalne.
> No to sie okazuje, ze narzut matlaba dla niewielkich wektorkow jest
> spory.
To nie ma nic wspolnego z narzutem Matlaba.
To sie nie skaluje liniowo. Kod mnozenia gdy prawa strona jest
macierza robi pewna sztuczke - blocking, podstawowy kod mnozenia ma
conajmniej szesc zagniezdzonych petli w taki sposob aby potrzebne
rzeczy byly w pamieci cache.
Cache misses dla L2 to koszt rzedu 200-300 cykli procesora. Unikniecie
wiec koniecznosci czytania pamieci daje duze oszczednosci.
Da sie to zrobic gdy prawa strona jest macierza, Gdy mnozy sie
wielkokrotnie przez wektor z prawej strony wykorzystanie pamieci jest
duzo gorsze, stad roznica efektywnosci. Narzut petli powinien byc
zaniedbywalny.
> Intelowski BLAS pokazuje skrzydla dopiero dla konkretnej ilosci
> danych.
Nie specjalnie pokazuje, peak jest dla macierzy ok 1.5tys x 1.5 tys.
Pozniej nastepuje pewne zalamanie.
thrunduil
> Popatrzylem na najszybszy kod. Odechcailo mi sie:)
http://lwn.net/Articles/255364/
tutaj duzo lepiej widac co sie dzieje
Wit Jakuczun
Dobry artykuł. Dzięki.
Pozdrawiam,
Wit Jakuczun
Mariusz Kruk
>MKL jest pisany tak, zeby byc bardzo optymalnym juz przy macierzach
>rzedu 30x30.
Co to znaczy "bardzo optymalnym"?
--
[------------------------]
[ Kr...@epsilon.eu.org ]
[ http://epsilon.eu.org/ ]
[------------------------]
Stachu 'Dozzie' K.
> epsilon$ while read LINE; do echo \>"$LINE"; done < "thrunduil"
>>MKL jest pisany tak, zeby byc bardzo optymalnym juz przy macierzach
>>rzedu 30x30.
>
> Co to znaczy "bardzo optymalnym"?
W wolnym t�umaczeniu: "bardzo najlepszy".
--
Secunia non olet.
Stanislaw Klekot
thrunduil
> Co to znaczy "bardzo optymalnym"?
wezmy dowolny problem optymalizacji praktycznej -> jest funkcja i
zbior solverow numerycznych.
Kazdy solver daje rozwiazanie optymalne, ale jedne bardziej inne mniej.
Mariusz Kruk
>wezmy dowolny problem optymalizacji praktycznej -> jest funkcja i
>zbior solverow numerycznych.
>Kazdy solver daje rozwiazanie optymalne, ale jedne bardziej inne mniej.
Sorry, ale to jest bzdura. Kt�re� solvery (BTW, jest na to jakie�
porz�dne polskie s�owo?) daj� rozwi�zania suboptymalne.
--
\.\.\.\.\.\.\.\.\.\.\.\.\.\
.\.Kr...@epsilon.eu.org.\.\.
\.http://epsilon.eu.org/\.\
.\.\.\.\.\.\.\.\.\.\.\.\.\.
thrunduil
> Sorry, ale to jest bzdura. Któreś solvery (BTW, jest na to jakieś
> porządne polskie słowo?) dają rozwiązania suboptymalne.
Kazdy, chyba ze rozumiesz ta jedyna optymalnosc jako optymalnosc z
dokladnoscia do epsilona (nieznanego)
i wydruk wyniku jako pelny dowod.
Mariusz Kruk
>Kazdy, chyba ze rozumiesz ta
"tďż˝"
>jedyna optymalnosc jako optymalnosc z
>dokladnoscia do epsilona (nieznanego)
Nie ma "optymalno�� z dok�adno�ci�". Optymalny oznacza "najlepszy przy
zadanych kryteriach". A z podstaw TM pewnie pami�tasz, �e w zbiorze
uporz�dkowanym nie ma dwu najwi�kszych element�w.
thrunduil
> epsilon$ while read LINE; do echo \>"$LINE"; done < "thrunduil"
>
> >Kazdy, chyba ze rozumiesz ta
>
>
> >jedyna optymalnosc jako optymalnosc z
> >dokladnoscia do epsilona (nieznanego)
>
> zadanych kryteriach". A z podstaw TM pewnie pamiętasz, że w zbiorze
> uporządkowanym nie ma dwu największych elementów.
Nie. Optymalny znaczy rozwiazujacy problem optymalizacji (w matematyce
tylko). Optymalny to nie jest funkcja: kryteria->wynik.
Jezeli solvery problemow optymalizacyjnych nie daja wyniku optymalnego
(bo wynik jest zwiazany z dokladnoscia i moze nawet lezy w malym
otoczeniu rozwiazania, przynajmniej mozna w to gleboko wierzyc)
to co daja?
Co oznacza optymalny wszedzie poza matematyka?
Moze zaproponujesz jakis slownik pojec matematyki praktycznej?
Mariusz Kruk
>> >Kazdy, chyba ze rozumiesz ta
>> >jedyna optymalnosc jako optymalnosc z
>> >dokladnoscia do epsilona (nieznanego)
>> zadanych kryteriach". A z podstaw TM pewnie pami�tasz, �e w zbiorze
>> uporz�dkowanym nie ma dwu najwi�kszych element�w.
>tylko). Optymalny to nie jest funkcja: kryteria->wynik.
A problem optymalizacji polega na znalezieniu ekstremum funkcji celu.
Ekstremum.
>Jezeli solvery problemow optymalizacyjnych nie daja wyniku optymalnego
>(bo wynik jest zwiazany z dokladnoscia i moze nawet lezy w malym
>otoczeniu rozwiazania,
Ale piszesz o optymalizacji, czy numeryce? Optymalizacja to jedno,
a numeryka z jej zabawami z dok�adno�ci�, to jednak co� innego.
(cho� owszem, mo�na zaprz�ga� jedno do drugiego)
>przynajmniej mozna w to gleboko wierzyc)
>to co daja?
Rozwi�zania suboptymalne. Mo�liwe, �e z powodu istnienia czynnik�w
zewn�trznych akceptowalne w danym zastosowaniu, ale jednak suboptymalne.
>Co oznacza optymalny wszedzie poza matematyka?
To samo, co w matematyce. http://sjp.pwn.pl/lista.php?co=optymalny
--
/\-\/\-\/\-\/\-\/\-\/\-\/\
\ Kr...@epsilon.eu.org /
/ http://epsilon.eu.org/ \
\/-/\/-/\/-/\/-/\/-/\/-/\/
Krzysiek Kowaliczek
> Nie. Optymalny znaczy rozwiazujacy problem optymalizacji (w matematyce
> tylko). Optymalny to nie jest funkcja: kryteria->wynik.
Nie, optymalny znaczy najlepszy.
> Jezeli solvery problemow optymalizacyjnych nie daja wyniku optymalnego
> (bo wynik jest zwiazany z dokladnoscia i moze nawet lezy w malym
> otoczeniu rozwiazania, przynajmniej mozna w to gleboko wierzyc)
> to co daja?
Proste, daje wynik zbli�ony do optymalnego.
Pozdrawiam
KK
thrunduil
<krzysiek.kowaliczek.remov...@gmail.com> wrote:
> Proste, daje wynik zbli ony do optymalnego.
ta terminologia cieszy sie ogromnym powodzeniem, wszedzie mozna ja
spotkac.)
rozwazmy problem prostszy. Optymalizujemy kod z flagami O1, O2, O3.
Uzyskujemy kod zoptymalizowany ale nie optymalny.
Wynikiem zastosowania procedury optymalizacji, ktora zakonczyla sie
sukcesem uzyskujemy cos co nie jest optymalne.
Spojnosc z terminologia matematyczna jest naprawde powalajaca :)
Czy moze zglosiles bug report: zly wording?
Wit Jakuczun
Sformułowanie "bardziej optymalne" jest błędne w języku Polskim!
Jeśli solver daje rozwiazanie optymalne to z definicji inny nie może
dać rozwiązania
lepszego, to znaczy takiego, że funkcja celu przyjmuje większą/
mniejszą wartość (w zależności
od tego czy maksymalizujemy czy minimalizujemy).
Jeśli solver nie daje rozwiązania optymalnego to znaczy, że daje
rozwiązanie
nieoptymalne.
W mowie potocznej rzeczywiście mówi się, że ktoś coś zrobił bardziej
optymalnie niż
ktoś inny. Ale mowa potoczna często nie jest poprawna...
Pozdrawiam,
Wit Jakuczun
Wit Jakuczun
> > Proste, daje wynik zbli ony do optymalnego.
>
> ta terminologia cieszy sie ogromnym powodzeniem, wszedzie mozna ja
> spotkac.)
>
To oczywiste, gdyż ta terminologia jest poprawna.
> rozwazmy problem prostszy. Optymalizujemy kod z flagami O1, O2, O3.
> Uzyskujemy kod zoptymalizowany ale nie optymalny.
> Wynikiem zastosowania procedury optymalizacji, ktora zakonczyla sie
> sukcesem uzyskujemy cos co nie jest optymalne.
Normalka w praktyce.
> Spojnosc z terminologia matematyczna jest naprawde powalajaca :)
>
Gdzie tu widzisz brak spójności? Nie każda metoda optymalizacji zwraca
rozwiązanie
optymalne. Powiem więcej, w praktyce, o której wspominałeś, metoda ma
zwróć
dobre rozwiązanie (o wysokiej jakości mierzonej funkcją celu) w
krótkim czasie. Nikt
nie oczekuje rozwiązania optymalnego. Wszyscy oczekują rozwiązania
lepszego od tego,
które teraz jest stosowane.
Pozdrawiam,
Wit Jakuczun
bartekltg
> > No to sie okazuje, ze narzut matlaba dla niewielkich wektorkow jest
> > spory.
>
> To nie ma nic wspolnego z narzutem Matlaba.
Zakład?
> To sie nie skaluje liniowo. Kod mnozenia gdy prawa strona jest
> macierza robi pewna sztuczke - blocking, podstawowy kod mnozenia ma
> conajmniej szesc zagniezdzonych petli w taki sposob aby potrzebne
> rzeczy byly w pamieci cache.
> Cache misses dla L2 to koszt rzedu 200-300 cykli procesora. Unikniecie
> wiec koniecznosci czytania pamieci daje duze oszczednosci.
> Da sie to zrobic gdy prawa strona jest macierza, Gdy mnozy sie
> wielkokrotnie przez wektor z prawej strony wykorzystanie pamieci jest
> duzo gorsze, stad roznica efektywnosci. Narzut petli powinien byc
> zaniedbywalny.
To nie ma nic wspolnego z pamiecia, przynajmniej nie tak, jak
sugerujesz.
Jesli by mialo, to moj prosty kod (podany na koncu) tez by mizernie
dzialal.
Ale on nie chec, 1000 roznych mnozen wektorka dlugosci 1000
przez macierz 1000x1000 liczy w niecale 6s.
Dwa razy wolniej niz matlab liczac iloczyn 2 macierzy,
ale tez ponad dwa razy szybciej niz analogiczne petla
w matlabie:
||>> tic,for j=1:1000,a*v;end;toc
||
||Elapsed time is 15.379616 seconds.
Czyli rozdrabnianie wywoluje jakis narzyt nie tylko
przez gorsze wykorzystywanie pamieci.
Chyba, ze cos w kodzie jest zle. Wektor wejsciowy zalezy od
tego, co sie wpisze, wynik jest takze wypisywany ('potrzebny').
W kazdej petli korzystam z innego wektora (kawalka znacznie
dluzszego wektora)..
pozdrawiam
bartekltg
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
void mnoz (double *w,double *M,double *v,int n)
{
for (int j=0;j<n;j++)
{
double t=0;
for (int i=0;i<n;i++)
t+=v[i]*M[j+2*i];
w[j]=t;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
double *w;double *M;double *v;
clock_t start,end;
double dif;
int n,r;
scanf("%d %d",&n,&r);
srand(r);//coby jakos dziwnie nie zoptymalizowalo
w=new double [n*n];
v=new double [n*n];
M=new double [n*n];
for (int i=0;i<n*n;i++)
v[i]=rand()*1.024894;
for (int i=0;i<n*n;i++)
M[i]=rand()*1.894;
start=clock();
for (int i=0;i<n;i++) //n razy podrzucamy rozne wektorki
mnoz(&w[i*n],M,&v[i*n],n);
end=clock();
double aku=1;
for (int i=1;i<n*n;i++)
aku+=w[i]*w[i-1]; //coby wynik byl potrzebny i kod nie wyparowal
printf("\n%.2le \n",aku);
dif = difftime (end,start);
printf ("\n%.2lf \n", double(end-start)/double(CLOCKS_PER_SEC) );
return 0;
}
Stachu 'Dozzie' K.
> On 21 Sty, 14:23, thrunduil <thrund...@wp.pl> wrote:
>> On 21 Sty, 11:40, Mariusz Kruk <Mariusz.K...@epsilon.eu.org> wrote:
>>
>> > Co to znaczy "bardzo optymalnym"?
>>
>> wezmy dowolny problem optymalizacji praktycznej -> jest funkcja i
>> zbior solverow numerycznych.
>> Kazdy solver daje rozwiazanie optymalne, ale jedne bardziej inne mniej.
>
Podobnie jak pisanie "j�zyk Polski" ;>
Wit Jakuczun
<doz...@go.eat.some.screws.spammer.invalid> wrote:
> > Sformu owanie "bardziej optymalne" jest b dne w j zyku Polskim!
>
> Podobnie jak pisanie "j zyk Polski" ;>
>
Fakt ;).
Pozdrawiam,
Wit Jakuczun
Mariusz Marszałkowski
> On 21 Sty, 10:08, thrunduil <thrund...@wp.pl> wrote:
> Czyli rozdrabnianie wywoluje jakis narzyt nie tylko
> przez gorsze wykorzystywanie pamieci.
Jest lepszy algorytm mnozenia macierzy niż N^3. Jeśli
matlab go uzywa, to im wieksze macierze tym lepiej
wypada.
Pozdrawiam serdecznie
Mariusz Marszałkowski
>
> > On 19 Sty, 02:52, bartekltg <bartek...@gmail.com> wrote:
>
> > > On 18 Sty, 20:26, Mariusz Marszałkowski <mmars...@gmail.com> wrote:
>
> > > > Nie rozumie, a co ja porównałem jak nie mnożenie macierzy?
>
> > > Porownales wektor * macierz. Ja zastanawialem sie nad porownaniem
> > > mnozenia 2 macierzy kwadratowych (i nieco wiekszych niz 1000).
>
> > Nie wiem czy się skuszę (mam masę innych rzeczy do testowana) na
> > taki test, ale może... Nie znam tego algorytmu który ma mniejszą
> > złożoność niż N^3. Obecnie jakie jest dokładne teoretyczne
> > ograniczenie?
>
> Coppersmitha-Winograda daje n^2.376, ale stala jest tak duza,
> za na razie komputery nie bawia sie takimi macierzami pelnymi.
>
> Niby mozna uzywac algorytmu Strassena (n^log_2 7 = log^2.807),
> ale ma on klopoty z numeryczna stabilnoscia. Blas uzywa n^3
> (jeszcze do tego wroce).
>
> > Może jakbym miał przystępnie opisany ten algorytm to bym napisał w
> > gołym C.
> > Zapodajcie linka do dobrego algorytmu, może spróbuję.
>
> http://en.wikipedia.org/wiki/Strassen_algorithm
> ale IHMO nie ma sensu n^3 starczy.
>
> > > > Napisałem wydajniej to co opisałem: mnożenie macierzy o
> > > > rozmiarze Nx1 przez macierz MxN. Super wydajny pakiet powinien
> > > > mieć specjalną implementację do takich macierzy.
>
> > > A nie jest to wydajne? Masz czas tego samego rzedu co w jezyku
> > > kompilowalnym (i to skompilowanem pod swoj system i procek!).
>
> > Zależy jak oceniać. Słyszałem opinie z których wynikało że
> > matlab to wszystko robi z 50 razy szybciej. W świetle tamtych
>
> http://ubuntuforums.org/archive/index.php/t-1295370.html
> :)
>
> > opinii wypadł śmiesznie, i głównie to chciałem sprawdzić. A
> > czy jest 2 razy szybszy czy 2 razy wolniejszy to osobiście
> > zgadzam się że nie powód do oceniania pakietu. Chciałem się
> > tylko upewnić czy nie jest 50 razy lepszy :)
>
> 50 na dzien dobry brzmi smiesznie.
> Ale nadal bede mowic, ze sprawdziles to dla
> danych nieso spoza zakresu w ktorym matlab jest dobry.
>
> > Przy jednym z moich projektów miesięczny rachunek za energię
> > na komputery liczące to około 1000zł. Dużo nie brakuje aby
> > starczyło na wypłatę dla nastepnego programisty...
>
> Teraz polowe zaoszczedzisz.. Student na pol etatu na to pojdzie?
>
> > Właśnie od różnych ludzi i z różnych środowisk, w
> > końcu mnie sprowokowali.
>
> Skoro sprowokowali, to zrob uczciwy test na duzych
> maciezach a nie pitu-pitu wektorkami po 1000 elementow:)
>
> > > Moze rzeczywiscie pisali mnozenie macierzy w javie;)
>
> > Sadze ze w ogole nie pisali i w ogole nie porownywali czasow,
> > tylko ulegli marketingowi matlaba.
>
> :)
>
> > Ale mogil sie postarac a wrecz powinni. Wystarczy rozpoznac
> > ze mnozymy wektor przez macierz i dac goto do wyspecjalizowanej
> > procedurki. Tak samo jesli mnozymy macierz [NxK] przez [KxM] dla
> > M i N znacznie wiekszych niz K, to jakas wyspecjalizowana procedura
> > wymnozylaby duzo szybciej niz ogolna.
>
> Dla bardzo malych K mozna by sie bawic w rozwijanie petli.
> Dla wiekszych - nie ma znaczenia przy algorytmie n^3.
>
> > > wielkosci, to jest przyzwoity wynik.
>
> > Ja tez tak podejrzewam, ale teraz tez wiem ze nie ma
> > implementacji 50 razy wydajniejszych.
>
> Za to sa 50razy mniej wydajne;)
>
> > > W miare mozliwosci (trzeba napisac) zrob to porownanie przy mnozeniu
> > > dwuch macierzy 1000x1000. Roznica powinna sie znacznie zmniejszyc.
>
> > Nie obiecuje, ale sprobuje, tylko zapodajcie dobry opis algorytmu,
> > nigdy
> > nie implementowalem lepszego algorytmu mnozenia macierzy.
> > Może mieć algorytm o lepszej zlozonosci niż N^3 i
> > jego moc się nie ujawnia gdy mnozymy macierze
> > podobne do wierszowych.
>
> Nie. Matlab, (mimo mojego natkniecia sie na informacje,
> ze jednak) nie korzysta z szybszych algorytmow
> (przynajmniej dla macierzy rzedu 1000-2000).
>
> Dowod literaturowy. Matlab korzysta z BLASa jako
> silnika do operacji na macierzach:http://www.mathworks.com/access/helpdesk/help/techdoc/ref/mtimes.html
> [*]
> Wiki gdzies wsponilala, ze BLAS uzywa dla duzych macierzy jakios
> modyfikacji
> Strassena, jadnak w kodzie tego nie widac:http://www.netlib.org/blas/dgemm.f (macierz macierz).
>
> Dowod statystyczny (12 macierzy o wielkosciach ciut ponizej 1000 do
> ok2000):
> wyn=[];for j=95:110; n=floor(2^(j/10)); a=rand(n); b=rand(n);
> tic;a*b;wyn=[wyn;n,toc], end;
> plot(log(wyn(:,1)),log(wyn(:,2)),'*' ) %poogladajmy sobie
> [s,serr]=lscov([x,ones(size(x))],y)
>
> Czas algorytmu to n^k hdzie k= 2.99 +- 0.06
>
> Wiec n^3. Przynajmniej nie bede sie bac o stabilnosc numeryczna.
>
> Jednak polecam napisanie tego n^3 i porownaine z matlabem.
> Moze ci 'z roznych srodowisk' nie mylili sie tak bardzo
> i kombajn bedize szybszy od napredce zmajstrowanego
> programiku (pomijajac wspolczynnik 50 wziety z sufitu;)
Zgoda, jesli zapewniles mnie ze matlab uzywa tego algorytmu
n^3 to sprawdze na macierzach o roznych rozmiarach. Wkrotce
podam czasy wykonania.
A co do 50 razy to wrecz zaczynalem czuc presje, ze
powinienem uzyc matlaba. To chyba znak ze matlab
naprawde niezle jest rozreklamowany.
Pozdrawiam
Mariusz Marszałkowski
> Złożoność ciągle jest N^3 ale działa szybciej niż pętelki.
W Cormenie strona 869 jest taki tekst:
Pojawienie sie algorytmu strassena w 1969r spowodowalo duze
poruszenie.
Wczeniej bowiem trudno bylo wyobrazic sobie istnienie algorytmum
lepszego niz
standardowy. Asymptotoczne ograniczenie gorne zlozonosci czasowej
algorytmu
monozenia macierzy zostalo od tego czasu znaczaco poprawione. Obecnie
asymptotycznie najbardziej wydajny algorytm mnozenia macierzy n x m,
dzialajacy w czasie O( n^2.376 ), podali Coppersmith i Winograd.
Graficzne
przedstawienei algorytmu strassena zawdzieczamy patersonowi. Fiszer i
Meyer
dostosowali algorytm Strassena do macierzy bolowskich.
Pozdrawiam
thrunduil
> To nie ma nic wspolnego z pamiecia, przynajmniej nie tak, jak
> sugerujesz.
> Jesli by mialo, to moj prosty kod (podany na koncu) tez by mizernie
> dzialal.
> Ale on nie chec, 1000 roznych mnozen wektorka dlugosci 1000
> przez macierz 1000x1000 liczy w niecale 6s.
nie do konca rozumiem:
Matlab: A * B =>
0.18sec
Matlab: for i:1000; A*v; end => 1.84sec
kod c for i:1000; A*v; end, wersja bledna => 1,33 sec
kod c for i:1000; A*v; end, wersja poprawna => 7.00 sec
A = 1000x1000, B = 1000x1000; v =1000x1
jest blad w kodzie, ma byc
t+=v[i]*M[j+n*i]; zamiast t+=v[i]*M[j+2*i];
(VS, /Ox /Oi /Ot /GL /I \Projects\test\test" /D "WIN32" /D "NDEBUG" /D
"_CONSOLE" /D "_UNICODE" /D "UNICODE" /FD /EHsc /MD /Gy /arch:SSE2 /
Fo"Release\\" /Fd"Release\vc90.pdb" /W3 /nologo /c /Zi /TP /
errorReport:prompt )
co to ma pokazywac oprocz tego, ze pamiec ma znaczenie? Blad w kodzie
nie zmienia liczby wykonanych operacji.
zreszta
dla A = 3000x1000; B =1000x1000; v = 1000x1
Matlab: A * B =>
0.537sec
Matlab: for i:1000; A*v; end => 5.33sec
W obu wersjach mnozenie przez wektor w petli jest 10x wolniejsze.
Petla jest wykonywana 1000 razy, wiec roznica nie moze miec
nic wspolnego z narzutem petli.
Wit Jakuczun
przekazać?
Pozdrawiam,
Wit Jakuczun
bartekltg
> On 21 Sty, 16:10, bartekltg <bartek...@gmail.com> wrote:
>
> > To nie ma nic wspolnego z pamiecia, przynajmniej nie tak, jak
> > sugerujesz.
> > Jesli by mialo, to moj prosty kod (podany na koncu) tez by mizernie
> > dzialal.
> > Ale on nie chec, 1000 roznych mnozen wektorka dlugosci 1000
> > przez macierz 1000x1000 liczy w niecale 6s.
>
> nie do konca rozumiem:
> Matlab: A * B =>
> 0.18sec
> Matlab: for i:1000; A*v; end => 1.84sec
> kod c for i:1000; A*v; end, wersja bledna => 1,33 sec
> kod c for i:1000; A*v; end, wersja poprawna => 7.00 sec
>
> A = 1000x1000, B = 1000x1000; v =1000x1
>
> jest blad w kodzie, ma byc
> t+=v[i]*M[j+n*i]; zamiast t+=v[i]*M[j+2*i];
O kurde, jaki wstyd przed ryskiem;/
Wersja poprawione idzie u mnie prawie 50s.
Ale w koncu uwierzylem w portege matlaba;)
Pozostaje pytanie, dlaczego Mariuszowi wychodzilo szybiej.
> co to ma pokazywac oprocz tego, ze pamiec ma znaczenie? Blad w kodzie
> nie zmienia liczby wykonanych operacji.
rzeczywiscie, masz racje, latam tam po obszarze pamieci
3000*8 a nie 10^6*8 i to jedyna roznica.
> zreszta
> dla A = 3000x1000; B =1000x1000; v = 1000x1
> Matlab: A * B =>
> 0.537sec
> Matlab: for i:1000; A*v; end => 5.33sec
>
> W obu wersjach mnozenie przez wektor w petli jest 10x wolniejsze.
> Petla jest wykonywana 1000 razy, wiec roznica nie moze miec
> nic wspolnego z narzutem petli.
pozdrawiam
bartekltg
bartekltg
Juz o tym bylo - nie korzysta, przynajmniej dla tak malych macierzy.
Co do mojego wyniku, thrunduil znalazl blad. Tak naprawde dzial to
10 razy dluzej (i 3 razy dluzej niz petla w matlabie).
Teraz pytanie, dlaczego u Ciebie wyniki sa tak dziwne.
pozdrawiam
bartekltg
Mariusz Marszałkowski
Odnoszę wrażenie iż autorzy "wprowadzenie do algorytmów" twierdzą iż
złożonosć
jest jednak mniejsza niż N^3.
Pozdrawiam
Wit Jakuczun
algortymie o
złożoności N^3. Jego wersja blokowa też jest N^3.
Pozdrawiam,
Wit Jakuczun
Mariusz Marszałkowski
Aha, to źle zrozumiałem :)
Pozdrawiam
lolo
>> t+=v[i]*M[j+n*i]; zamiast t+=v[i]*M[j+2*i];
>
> O kurde, jaki wstyd przed ryskiem;/
>
> Wersja poprawione idzie u mnie prawie 50s.
> Ale w koncu uwierzylem w portege matlaba;)
i już wiesz za co się płaci ?
sprawdzony, przetestowany, wiarygodny kod, wyjątki, przypadki
szczególne, optymalizacje, uniwersalność, modułowość itd.
Mariusz Marszałkowski
Wiemy to od dawna wszyscy. Mnie chodziło o to, że słyszę
dużo plotek na temat wydajności matlaba.
Poza tym sprawdzony i przetestowany kod własnego autorstwa
używa się równie wygodnie jak matlabowego a = b * c.
A jeszcze inna kwestia: Ktoś zapodał link do turnieju i osiągów
w wydajności mnożenia macierzy. Wyniki zaprezentowane
tam, potwierdzają że w tym prostym algorytmie różnica w
wydajności może wynosić np. 50 razy.
Pozdrawiam serdecznie
bartekltg
Alez ja jestem wielkim milosnikiem matlaba, czego wyraz dawalem
takze w tym watku:)
pozdrawiam
bartekltg
thrunduil
> Wiemy to od dawna wszyscy. Mnie chodziło o to, że słyszę
> dużo plotek na temat wydajności matlaba.
jakich plotek?, ktore operacje w matlabie sa nieefektywne?
Sa takie ale dotycza przede wszystkim operacji na macierzach rzadkich.
> A jeszcze inna kwestia: Ktoś zapodał link do turnieju i osiągów
> w wydajności mnożenia macierzy. Wyniki zaprezentowane
> tam, potwierdzają że w tym prostym algorytmie różnica w
> wydajności może wynosić np. 50 razy.
raczej to, ze wlasnorecznie napisane mnozenie macierzy nawet
wykorzystujac watki
sa wielokrotnie wolniejsze od serial version dobrze zoptymalizowanego
atlasa.
Atlas do tego nie jest najlepsza implementacja.
Mariusz Marszałkowski
> On 22 Sty, 10:15, Mariusz Marszałkowski <mmars...@gmail.com> wrote:
>
> > Wiemy to od dawna wszyscy. Mnie chodziło o to, że słyszę
> > dużo plotek na temat wydajności matlaba.
> jakich plotek?, ktore operacje w matlabie sa nieefektywne?
> Sa takie ale dotycza przede wszystkim operacji na macierzach rzadkich.
> > A jeszcze inna kwestia: Ktoś zapodał link do turnieju i osiągów
> > w wydajności mnożenia macierzy. Wyniki zaprezentowane
> > tam, potwierdzają że w tym prostym algorytmie różnica w
> > wydajności może wynosić np. 50 razy.
>
> raczej to, ze wlasnorecznie napisane mnozenie macierzy nawet
> wykorzystujac watki
> sa wielokrotnie wolniejsze od serial version dobrze zoptymalizowanego
> atlasa.
> Atlas do tego nie jest najlepsza implementacja.
Nie mam matlaba a nie chce instalować pirata. Gdy znow
bede mial okazje przysiasc na kompie gdzie jest gcc i matlab
to zrobie test mnozenia wiekszych macierzy. Wyniki i
kod zrodlowy podam w nowym watku.
Pozdrawiam
Mariusz Marszałkowski
> On 21 Sty, 09:05, Mariusz Marszałkowski <mmars...@gmail.com> wrote:
>
> > Wręcz przeciwnie. Kod w C tak naprawdę przeliczał ogromną
> > sztuczną sieć neuronową, więc macierze w C były o jeden
> > element większy i dodatkowo obliczał funkcję: 2/( 1 + exp( -x ) ) - 1.
>
> > Ale oczywiście mogłem się gdzieś pomylić, nie mam kodu na
> > tym komputerze, poproszę żeby mi przysłali i go wkleję.
>
> To jest w zasadzie niemozliwe. Kod mnozenia macierzy jest bardzo
> zlozony. Bez naprawde dobrze stuningowanego memory use, wstaweg
> asemblerowych
> i dlugiego testowania parametrow optymalizacyjnych nie ma szans na
> zblizenie sie do wydajnosci Matlaba. Istnieja szybsze implementacje
> mnozenia macierzy,
> np GOTO blas jest ok 10% szybszy, ale i tak to jest w zasadzue
> technologiczny limit na dzisiaj.
> Kod Matlabla (tj bibliteka MKL, matlab nie napisal tego kodu sam)
> jest o rzad wielkosci szybszy od dobrze stuningowanego kodu w C.
Przy mnozeniu macierzy wierszowej przez prostokatna juz wiem
na 100% ze matlab nie jest o zaden rzad wielkosci szybszy, tylko
jest dwa razy wolniejszy od procedury napisanej doslownie na
kolanie w C++.
W nowym watku zamiescilem kod mnozenia wiekszych macierzy
niz wierszowe, zobaczymy jak wypadnie tym razem. Nie mam
matlaba aby sprawdzic osobiscie, czekam az ktos sprawdzi.
Pozdrawiam
Wit Jakuczun
> Przy mnozeniu macierzy wierszowej przez prostokatna juz wiem
Co to jest macierz wierszowa?
Pozdrawiam,
Wit Jakuczun
Mariusz Marszałkowski
> On 23 Sty, 10:11, Mariusz Marszałkowski <mmars...@gmail.com> wrote:
>
> > Przy mnozeniu macierzy wierszowej przez prostokatna juz wiem
>
> Co to jest macierz wierszowa?
>
Pozdrawiam
Wit Jakuczun
Ok. Czyli to jest po prostu wektor :).
Pozdrawiam,
Wit Jakuczun
Mariusz Marszałkowski
thrunduil
> Przy mnozeniu macierzy wierszowej przez prostokatna juz wiem
> na 100% ze matlab nie jest o zaden rzad wielkosci szybszy, tylko
> jest dwa razy wolniejszy od procedury napisanej doslownie na
> kolanie w C++.
to bylo sprawdzane czy sa to tylko domysly?
bo podany kod mnozenia macierzy byl >10x wolniejszy od matlaba.
i to nawet dla tablic o statycznie znanych rozmiarach bedacych potega
2.
W tym przypadku kompilator generuje bardzo optymalne indeksowanie.
W ogolnym kodzie takie optymalizacje sa niemozliwe.
bartekltg
> On 23 Sty, 10:11, Mariusz Marszałkowski <mmars...@gmail.com> wrote:
>
> > Przy mnozeniu macierzy wierszowej przez prostokatna juz wiem
> > na 100% ze matlab nie jest o zaden rzad wielkosci szybszy, tylko
> > jest dwa razy wolniejszy od procedury napisanej doslownie na
> > kolanie w C++.
>
> to bylo sprawdzane czy sa to tylko domysly?
>
> bo podany kod mnozenia macierzy byl >10x wolniejszy od matlaba.
To byl moj kod wiecz czuje sie wywolany do usprawiedliwien.
Tamten kod byl napisany przed odrobieniem lekcji i skakal
po macierzy nie w tej kolejnosci, w jakiej lubi to cache.
Napisalem trzy wersje mnozenia poziomego wektora przez macierz
naiwna ze zla kolejnoscia petli, naiwna z dobra kolejnoscia
i wariacje na temat blokowego mnozenia macierzy.
n=960. Wszystko, program w cpp i matlab dostawaly piorytet real time.
naiwny, złe petle 51.345
naiwny, ok 7.923
blok32 8.705
blok16 6.865
blok8 4.886
blok4 5.476
MATLAB 8.899
tic,for j=1:960,w=v*M;end;toc
Mam nadzieje, ze tym razem nie strzelilem babola;)
void mnoz (double *w,double *M,double *v,int n)
{//petle ok
for (int i=0;i<n;i++)
{
v[i]=0;
}
for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
v[j]=w[i]*M[n*i+j];
}
}
void mnoz_naiw(double *w,double *M,double *v,int n)
{//zle petle
for (int i=0;i<n;i++)
{
v[i]=0;
}
for (int j=0;j<n;j++)
for (int i=0;i<n;i++)
v[j]=w[i]*M[n*i+j];
}
template<class T, int SN>
void blokmnoz (T *w,T *M,T *v,int n)
{
for (int i=0;i<n;i++)
{
v[i]=0;
}
for (int i=0;i<n;i+=SN)
{
for (int j=0;j<n;j+=SN)
{
for (int ii=i;ii<i+SN;ii++)
{
for (int jj=j;jj<j+SN;jj++)
v[jj]=w[ii]*M[n*ii+jj];
}
}
}
}
pozdrawiam
bartekltg
Adam Piotrowski
>> Dlaczego mam sie nie dziwic? Matlab chyba jest cholernie drogi?
>
> Mnie zastanawia, jakie sa zastosowania, w kt�rych sie faktycznie OPLACA
> wybulic TAKI majatek na Matlaba... bo jakies chyba sa, skoro program zyje?
>
Stosowany jest czesto do obliczen inzynierskich na uczelniach -
wystarczy podstawowa wiedza na temat programowania a mozna pisac
zaawansowane programy symulujace rozne zjawiska. Z ciekawszych
zastosowan Matlaba jak dla mnie to ... sterowanie praca akceleratora
liniowego
Adam
Mariusz Marszałkowski
> Wiktor S. pisze:
>
> >> Dlaczego mam sie nie dziwic? Matlab chyba jest cholernie drogi?
>
> > wybulic TAKI majatek na Matlaba... bo jakies chyba sa, skoro program zyje?
>
> Stosowany jest czesto do obliczen inzynierskich na uczelniach -
> wystarczy podstawowa wiedza na temat programowania a mozna pisac
> zaawansowane programy symulujace rozne zjawiska. Z ciekawszych
> zastosowan Matlaba jak dla mnie to ... sterowanie praca akceleratora
> liniowego
Ciekawi mnie ta matalbowa uniwersalna szukaczka minimow funkcji.
Np. mam plik testowy z miliardem wierszy (albo jeszcze wiecej) i
kilkudziesięcioma
kolumnami. Trzeba zrobic z tego uklad rownan normalnych i podac
współczynniki
liniowe. Domyslam sie ze z tak zdefiniowanym zadaniem nie ma problemu,
ale
po jednym rozwiazaniu trzeba utworzyc dodatkowa kolumne przez poddanie
nieliniowej funkcji kilku innych kolumny (na chybil tafil, albo
systematycznie wszystkie
kombinacjie) i podac najlepsze dopasowanie.
Pozdrawiam
Roman Werpachowski
> Wiktor S. pisze:
>
> >> Dlaczego mam sie nie dziwic? Matlab chyba jest cholernie drogi?
>
> > wybulic TAKI majatek na Matlaba... bo jakies chyba sa, skoro program zyje?
>
> Stosowany jest czesto do obliczen inzynierskich na uczelniach -
> wystarczy podstawowa wiedza na temat programowania a mozna pisac
> zaawansowane programy symulujace rozne zjawiska. Z ciekawszych
> zastosowan Matlaba jak dla mnie to ... sterowanie praca akceleratora
> liniowego
W ogole to przeciez Matlab nie jest taki drogi, zeby jakis bank czy
hedge fund nie mogl kupic po licencji dla kazdego analityka (ktory nie
musi byc programista, zeby napisac calkiem wydajny kod numeryczny).
Druga potezna zaleta Matlaba jest latwa wizualizacja danych, to czesto
wazniejsze niz predkosc mnozenia macierzy.
RW
Adam Przybyla
na matlaba;-) Z powazaniem
Adam Przybyla
Mariusz Marszałkowski
W Pytonie też są takie gotowce jak uniwersalna szukaczka minimów?
Pozdrawiam
bartekltg
> liniowe. Domyslam sie ze z tak zdefiniowanym zadaniem nie ma problemu,
> ale
> po jednym rozwiazaniu trzeba utworzyc dodatkowa kolumne przez poddanie
> nieliniowej funkcji kilku innych kolumny (na chybil tafil, albo
> systematycznie wszystkie
> kombinacjie) i podac najlepsze dopasowanie.
Jesli masz na mysli fminsearch, to znajduje lokalne minimum
i chyba nie najlepiej radzi sobie ze zbyt duza liczba zmiennych.
http://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method
Jesli dobrze rozumiem, chcesz miec jakis wklad kombinatoryczny.
Tego ta funkcja nie zrobi. Jesli jednak dopuszczasz, aby w
rozwiazaniu
byly wszytkie, to niepotrzebne beda mialy maly wspolczynnik i tyle
(rozumiem, ze przez 'nieliniowosc' rozumiesz np to, ze wspolrzynnik
jest odchyleniem rozkaldu gaussa, a nie, ze do symy wchodzi
parametr*funkcja(wartosc kolumny) )
Miliardy wierszy to gigabajty. Matlab nie musi byc wtedy najlepszym
wyborem (trzymasz wzytko w pamieci, a co jakis czas, potrzeba
podwoijnej
ilosci pamieci! Dosc beztrosko tworzy sobie kopie danych).
pozdrwiam
bartekltg
bartekltg
> W Pytonie też są takie gotowce jak uniwersalna szukaczka minimów?
Pewnie znajda sie lepsze szukaczki, ale ogolnie do abaw numerycznych
masz pakiety numpy i scipy.
pozdrawiam
bartekltg
Mariusz Marszałkowski
To bede musial sie rozejrzec, ile mozna pisac samemu ;)
Pozdrawiam
Mariusz Marszałkowski
> On 3 Lut, 22:19, Mariusz Marszałkowski <mmars...@gmail.com> wrote:
>
> > liniowe. Domyslam sie ze z tak zdefiniowanym zadaniem nie ma problemu,
> > ale
> > po jednym rozwiazaniu trzeba utworzyc dodatkowa kolumne przez poddanie
> > nieliniowej funkcji kilku innych kolumny (na chybil tafil, albo
> > systematycznie wszystkie
> > kombinacjie) i podac najlepsze dopasowanie.
>
> Jesli masz na mysli fminsearch, to znajduje lokalne minimum
>
> Jesli dobrze rozumiem, chcesz miec jakis wklad kombinatoryczny.
Nastepnie rozszerzam parametry wejsciowe o jeden dodatkowy
przez poddanie nieliniowej funkcji kazdej kombinacji funkcja( x_i ,
x_j ).
Jesli mam 50 parametrow wejsciowych, to wychodzi 2500 kombinacji.
WIec trzeba 2500 razy ulozyc uklad rownan normalnych, kazdy
rozwiazac i podac kombinacje x_i, x_j ktora daje najlepsze
dopasowanie.
To co zwraca funkcja( x_i , x_j ) traktujemy jako 51-szy parametr.
> Tego ta funkcja nie zrobi. Jesli jednak dopuszczasz, aby w
> rozwiazaniu
> byly wszytkie, to niepotrzebne beda mialy maly wspolczynnik i tyle
To też dobra metoda, szczegolnie jesli do glownej przekatnej doda
sie pewne liczby wieksze od zera.
> (rozumiem, ze przez 'nieliniowosc' rozumiesz np to, ze wspolrzynnik
> jest odchyleniem rozkaldu gaussa, a nie, ze do symy wchodzi
> parametr*funkcja(wartosc kolumny) )
Raczej parametr * funkcja( x_i , x_j )
> Miliardy wierszy to gigabajty.
Niestety to moja zmora. Z reguly brakuje dobrych danych przy
data minning. Moje dane nie mieszcza sie na 10 nowoczesnych
dyskach. A moze jakas baza danych ma zaimplementowana
regresje liniowa dla wielu parametrow? Jakis odpowiednik
excelowskiego reglinp?
> Matlab nie musi byc wtedy najlepszym
Hmmm, dziwne, powinien miec opcje ze macierz lezy na
dysku w pliku tekstowym albo binarnym. To raczej
zwykla rzecz ze dane leza na dysku a w pamieci sa
tylko "zmienne algorytmu".
Pozdrawiam
bartekltg
> Mam parametry wejsciowe x_i i np. jeden parametr wyjsciowy y.
> Nastepnie rozszerzam parametry wejsciowe o jeden dodatkowy
> przez poddanie nieliniowej funkcji kazdej kombinacji funkcja( x_i ,
> x_j ).
> Jesli mam 50 parametrow wejsciowych, to wychodzi 2500 kombinacji.
> WIec trzeba 2500 razy ulozyc uklad rownan normalnych, kazdy
> rozwiazac i podac kombinacje x_i, x_j ktora daje najlepsze
> dopasowanie.
> To co zwraca funkcja( x_i , x_j ) traktujemy jako 51-szy parametr.
Nie trzeba za kazdym razem ukladac calego zagadnienia...
> > Tego ta funkcja nie zrobi. Jesli jednak dopuszczasz, aby w
> > rozwiazaniu
> > byly wszytkie, to niepotrzebne beda mialy maly wspolczynnik i tyle
>
> To też dobra metoda, szczegolnie jesli do glownej przekatnej doda
> sie pewne liczby wieksze od zera.
?
> Raczej parametr * funkcja( x_i , x_j )
Czyli to cały czas liniowe zagadneinie najmnieszych kwadratow.
Bawienie sie w nieliniowe solvery tylko dodanarzut.
> > Miliardy wierszy to gigabajty.
>
> Niestety to moja zmora. Z reguly brakuje dobrych danych przy
> data minning. Moje dane nie mieszcza sie na 10 nowoczesnych
> dyskach. A moze jakas baza danych ma zaimplementowana
> regresje liniowa dla wielu parametrow? Jakis odpowiednik
> excelowskiego reglinp?
To wcale nie jest tak duzo danych jak na zadanie, ktore chesz
rozwiazac. Przyjrzyj sie dokladnie zagadnieniu. Jesli nie macie
problemu z tym, ze rozwiazujesz to rownaniem normalnym
(uwarunkowanie etc) to jedyne co musisz zrobic z danymi
to policzyc pewna ilosc iloczynow skalarnych.
1225 <x_i,x_j>, 50 <x_i, y>
125000< x_i, f(x_j,x_k) > i 2500<y,f(x_i,x_j)>
Jesli bys chciel dodac wiecej niz tylko jedna,
'nieliniowa funkcja od tabelek' dojdzie cos rzedu
3mln elementow(chyba, ze .. dluzsza historia;).
Wszytko liczysz w jednym przebiegu odczytywania danych,
nastepnie bawisz sie jedynie z _malymi_ obiektami (51x51)
X.' * X i X.' * y ( X.' -transponowane X).
Samo policzenie tych iloczynow jest wiekszym problemem.
Zajmie to na nowym komputerze cos rzedu wieksze kilka godzin
na miliard danych:)
Sumowac tez trzeba sprytnie (albo odpowiednio podwyzszajac
przecyzje, lepiej sprytnie, nieco to zalezy od danych).
Dobrym pomyslem jest tez zastanowienie sie, czy iloscny skalarnego
mniej istotnych par nie mozna przyblizac, szacowan np za pomoca
znacznie mniejszego podwektora Wtedy i zagadnienie uwzgledniajace
52 parametry na zwyklym PC.
Moze potrzebujecie matematyka z delikatnym zamilowaniem do
numerkow? :-)
> > Matlab nie musi byc wtedy najlepszym
>
> Hmmm, dziwne, powinien miec opcje ze macierz lezy na
> dysku w pliku tekstowym albo binarnym. To raczej
> zwykla rzecz ze dane leza na dysku a w pamieci sa
> tylko "zmienne algorytmu".
To znacznie zwieksza czas. I chyba nie ma za czestych zastosowan.
Zobacz, ile czasu zajeloby mnozenie 2 macierzy kwadratowych
zajmujacych wiekszaosc Twojego ramu. Strzelmy 20000x20000
(3GB). 1000 razy dluzej niz 2000x2000.
Z drugiej storny gugiel sugeruje, ze cos wie o mnozeniu macierzy
na dyskach. Jednak podejrzewam, ze i tak raczej uzywa sie tego do
macierzy rzadkich (jakies guglowskie pozycjonowanie etc).
Twoje zagadnienie jest prostrze, programik czyta, mnozy, dodaje, goto
start;)
pozdrawiam
bartekltg
Mariusz Marszałkowski
> On 5 Lut, 18:17, Mariusz Marszałkowski <mmars...@gmail.com> wrote:
>
> > Mam parametry wejsciowe x_i i np. jeden parametr wyjsciowy y.
> > Nastepnie rozszerzam parametry wejsciowe o jeden dodatkowy
> > przez poddanie nieliniowej funkcji kazdej kombinacji funkcja( x_i ,
> > x_j ).
> > Jesli mam 50 parametrow wejsciowych, to wychodzi 2500 kombinacji.
> > WIec trzeba 2500 razy ulozyc uklad rownan normalnych, kazdy
> > rozwiazac i podac kombinacje x_i, x_j ktora daje najlepsze
> > dopasowanie.
> > To co zwraca funkcja( x_i , x_j ) traktujemy jako 51-szy parametr.
>
> Nie trzeba za kazdym razem ukladac calego zagadnienia...
Chyba jednak trzeba, ponieważ podczas budowania układu w każdym z
równań występuje mnożenie przez nowy element funk( x_i , x_j ) ?
> > To też dobra metoda, szczegolnie jesli do glownej przekatnej doda
> > sie pewne liczby wieksze od zera.
>
> ?
Mamy wektory doświadczalne których elementy to x_1, x_2, y.
Normalnie szukamy najlepszego dopasowania funkcją:
f(x) = a * x_1 + b * x_2 + c
Czyli minimalizujemy sume ( a * x_1 + b * x_2 + c - y )^2
Ale możemy też minimalizować trochę inne wyrażenie:
( a * x_1 + b * x_2 + c - y )^2 + C1 * a^2 + C2 * b^2 + C3 * c^2
Jak policzysz teraz pochodne tego wyrażenia po a,b,c;
przyrównasz do zera, stworzysz układ równań liniowych,
to wyjdzie że główna przekątna została zwiększona o
odpowiednio 2*C1,2*C2,2*C3. W ten sposób automatycznie
dajesz karę za duże wartości parametrów, a wiec parametry
o mniejszym znaczeniu mają stosunkowo mniejsze wartości.
> > Raczej parametr * funkcja( x_i , x_j )
>
> Czyli to cały czas liniowe zagadneinie najmnieszych kwadratow.
> Bawienie sie w nieliniowe solvery tylko dodanarzut.
Tak, to cały czas dopasowanie najmniejszymi kwadratami. Po
zbadaniu siłowym, po wyczuciu intuicyjnym wybiera się
funkcje które dzialaja najlepiej i dopiero za drugim razem
optymalizacja nieliniowa.
> > > Miliardy wierszy to gigabajty.
>
> > Niestety to moja zmora. Z reguly brakuje dobrych danych przy
> > data minning. Moje dane nie mieszcza sie na 10 nowoczesnych
> > dyskach. A moze jakas baza danych ma zaimplementowana
> > regresje liniowa dla wielu parametrow? Jakis odpowiednik
> > excelowskiego reglinp?
>
> To wcale nie jest tak duzo danych jak na zadanie, ktore chesz
> rozwiazac. Przyjrzyj sie dokladnie zagadnieniu. Jesli nie macie
> problemu z tym, ze rozwiazujesz to rownaniem normalnym
> (uwarunkowanie etc)
Pojawiają się problemy ze złym uwarunkowaniem. Wtedy wywalam
całe równanie :)
> Jesli bys chciel dodac wiecej niz tylko jedna,
> 'nieliniowa funkcja od tabelek' dojdzie cos rzedu
> 3mln elementow(chyba, ze .. dluzsza historia;).
Najpierw jedną, później drugą, później trzecią...
W zaleznosci jaka daje jakie efekty, troche zgadywania,
w koncu rozrasta sie i na koniec jeszcze metoda nieliniowa.
> Wszytko liczysz w jednym przebiegu odczytywania danych,
> nastepnie bawisz sie jedynie z _malymi_ obiektami (51x51)
> X.' * X i X.' * y ( X.' -transponowane X).
>
> Samo policzenie tych iloczynow jest wiekszym problemem.
> Zajmie to na nowym komputerze cos rzedu wieksze kilka godzin
> na miliard danych:)
Policzenie tego jest proporcjonalne do odczytu danych z dysku.
Ale czasami mam bardzo dużo zer, wtedy moza skompresowac
i trzymac wszystko w RAM.
> Sumowac tez trzeba sprytnie (albo odpowiednio podwyzszajac
> przecyzje, lepiej sprytnie, nieco to zalezy od danych).
Mozna robic dwie sumy, jedna mala, a druga duza. Jak ta mala
urosnie na tyle, alby miala wplyw na duza to mozna polaczyc
obie. Nie bawilem sie w to nigdy. Ciekawe czy da sie rozwiazac
stabilniej uklad rownan, jakbym kazdy parametr mial wyrazony
jako dwie sumy? Hmmm... moze to prosty sposob na zwiekszenie
stabilnosci?
> Dobrym pomyslem jest tez zastanowienie sie, czy iloscny skalarnego
> mniej istotnych par nie mozna przyblizac, szacowan np za pomoca
> znacznie mniejszego podwektora Wtedy i zagadnienie uwzgledniajace
> 52 parametry na zwyklym PC.
> Moze potrzebujecie matematyka z delikatnym zamilowaniem do
> numerkow? :-)
Raczej potrzebujemy cudu :)
> Twoje zagadnienie jest prostrze, programik czyta, mnozy, dodaje, goto
> start;)
Tak, wiem :)
Pozdrawiam
bartekltg
> Chyba jednak trzeba, ponieważ podczas budowania układu w każdym z
> równań występuje mnożenie przez nowy element funk( x_i , x_j ) ?
Podstaw sobie wirtualnie nowa tabelka x_{51+50j+i}=funk( x_i , x_j )
i nie mysl o niej inaczej.
> Tak, to cały czas dopasowanie najmniejszymi kwadratami. Po
> zbadaniu siłowym, po wyczuciu intuicyjnym wybiera się
> funkcje które dzialaja najlepiej i dopiero za drugim razem
> optymalizacja nieliniowa.
Ale ja w tym zagadnieniu dalej nigdzie nie widze miejsca z
nieliniowoscia.
Liniowosc w regresji dotyczy sie liniowej zaleznosci od parametrow,
a nie danych.
> Policzenie tego jest proporcjonalne do odczytu danych z dysku.
> Ale czasami mam bardzo dużo zer, wtedy moza skompresowac
> i trzymac wszystko w RAM.
Na odczyt 50 zmiennych (jedna linijka danych) wykonujesz
kilkaset tysiecy operacji zmiennoprzecinkowych.
Za to pozniej masz luksusowa sytuacje.
>
> > Sumowac tez trzeba sprytnie (albo odpowiednio podwyzszajac
> > przecyzje, lepiej sprytnie, nieco to zalezy od danych).
>
> Mozna robic dwie sumy, jedna mala, a druga duza. Jak ta mala
> urosnie na tyle, alby miala wplyw na duza to mozna polaczyc
> obie. Nie bawilem sie w to nigdy. Ciekawe czy da sie rozwiazac
Sposobow jest wiele. Ktory wybrac, zalezy nieco od danych.
> stabilniej uklad rownan, jakbym kazdy parametr mial wyrazony
> jako dwie sumy? Hmmm... moze to prosty sposob na zwiekszenie
> stabilnosci?
Niewiele to pomoze.
> Raczej potrzebujemy cudu :)
Atam. Chyba, ze czegos istotnego o problemie nie dopowiedziales.
Propozycje podtrzymuje;p
pozdrawiam
bartek
Mariusz Marszałkowski
> On 6 Lut, 01:26, Mariusz Marszałkowski <mmars...@gmail.com> wrote:
>
> > Chyba jednak trzeba, ponieważ podczas budowania układu w każdym z
> > równań występuje mnożenie przez nowy element funk( x_i , x_j ) ?
>
> Podstaw sobie wirtualnie nowa tabelka x_{51+50j+i}=funk( x_i , x_j )
> i nie mysl o niej inaczej.
nie nie budować tabelki od nowa.
> Ale ja w tym zagadnieniu dalej nigdzie nie widze miejsca z
> nieliniowoscia.
Funkcje nieliniowe mają parametry. Dobierane są one intuicyjnie/siłowo
i
jest rozwiązywane równanie. Jeśli dopasowanie jest dobre, to metodą
nieliniowa dobierane są "dokładnie".
> Atam. Chyba, ze czegos istotnego o problemie nie dopowiedziales.
> Propozycje podtrzymuje;p
Uproscilem wszystko na potrzby szybkiego listu na forum. Te dane
to maskakra. Wydaje się że w danych nie ma wiecej zaleznosci niz
znalezlismy zaraz na poczatku, albo są nadzywczaj skomplikowane.
Pozdrawiam
Roman Werpachowski
Nie wiem, ich się spytaj, na pewno Ci wyjaśnią.
RW
bartekltg
> On 6 Lut, 02:26, bartekltg <bartek...@gmail.com> wrote:> On 6 Lut, 01:26, Mariusz Marszałkowski <mmars...@gmail.com> wrote:
>
> > > Chyba jednak trzeba, ponieważ podczas budowania układu w każdym z
> > > równań występuje mnożenie przez nowy element funk( x_i , x_j ) ?
>
> > Podstaw sobie wirtualnie nowa tabelka x_{51+50j+i}=funk( x_i , x_j )
> > i nie mysl o niej inaczej.
>
> No chyba dokładnie tak robię, ale nie widzę cały czas sposobu aby
> nie nie budować tabelki od nowa.
Obiekt A = X.' * X ma rozmiar tylko 51x51 (50kilka). Nie musisz
powrotnie
przeliczac wszytkiego, a jedynie elementy na 'brzegu'.
Pomysl byl taki, zeby policzyc wiecej roznych elementow dla tej
tabelki w jednym przebiegu po dysku, a dopioero pozniej ukladac z
nich
A= X.' * X i X.' * y
> Funkcje nieliniowe mają parametry. Dobierane są one intuicyjnie/siłowo
> i
> jest rozwiązywane równanie. Jeśli dopasowanie jest dobre, to metodą
> nieliniowa dobierane są "dokładnie".
Pamietaj o sztuczkach z pracowni fizycznej. Czesc 'nieliniowosci'
da sie wyrzucic odpowiednimi sztuczkami.
> Uproscilem wszystko na potrzby szybkiego listu na forum. Te dane
> to maskakra. Wydaje się że w danych nie ma wiecej zaleznosci niz
> znalezlismy zaraz na poczatku, albo są nadzywczaj skomplikowane.
Masz ogrom danych a zaleznosci nie tak wiele. Bardzo prawdopobne,
ze jesli wezmiesz tylko czesc danych dopasowanie bedzie tez dobre.
Wersja naiwna to losowo wybrana pewna ilosc(nadal duza) danych.
W wersji zaawansowanej mozesz pogoglac za ekspanderami.
Na podzbiorze dobierasz dane, poznniej liniowo(zaburzasz liniowo
nieliniowe czlony) sprawdzasz dopasowanie na calych danych.
Jesli sie wiele nie zmienilo, wynik jest dobry.
pzodrawiam
bartekltg