On 2010-01-21, Wit Jakuczun <w...@g...com> wrote:
> On 21 Sty, 14:23, thrunduil <t...@w...pl> wrote:
>> On 21 Sty, 11:40, Mariusz Kruk <M...@e...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.
>
> Sformułowanie "bardziej optymalne" jest błędne w języku Polskim!

Podobnie jak pisanie "język Polski" ;>

--
Secunia non olet.
Stanislaw Klekot

do góry

On 21 Sty, 16:14, "Stachu 'Dozzie' K."
<d...@g...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

do góry

On 21 Sty, 16:10, bartekltg <b...@g...com> wrote:
> On 21 Sty, 10:08, thrunduil <t...@w...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

do góry

On 21 Sty, 09:18, bartekltg <b...@g...com> wrote:
> On 19 Sty, 07:15, Mariusz Marszałkowski <m...@g...com> wrote:
>
> > On 19 Sty, 02:52, bartekltg <b...@g...com> wrote:
>
> > > On 18 Sty, 20:26, Mariusz Marszałkowski <m...@g...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;)

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

do góry

On 21 Sty, 09:28, Wit Jakuczun <w...@g...com> wrote:
> On 21 Sty, 09:18, bartekltg <b...@g...com> wrote:
> 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.

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

do góry

On 21 Sty, 16:10, bartekltg <b...@g...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];

(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.

do góry

On 21 Sty, 19:20, Mariusz Marszałkowski <m...@g...com> wrote:
> On 21 Sty, 09:28, Wit Jakuczun <w...@g...com> wrote:
>
> > On 21 Sty, 09:18, bartekltg <b...@g...com> wrote:
> > 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.
>
> 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.
>
Mógłbyś doprecyzować wypowiedź bo nie bardzo załapałem co chciałeś
przekazać?

Pozdrawiam,
Wit Jakuczun

do góry

On 21 Sty, 19:21, thrunduil <t...@w...pl> wrote:
> On 21 Sty, 16:10, bartekltg <b...@g...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

do góry

On 21 Sty, 18:53, Mariusz Marszałkowski <m...@g...com> wrote:
> On 21 Sty, 16:10, bartekltg <b...@g...com> wrote:
>
> > On 21 Sty, 10:08, thrunduil <t...@w...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.

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

do góry

On 21 Sty, 20:00, Wit Jakuczun <w...@g...com> wrote:
> On 21 Sty, 19:20, Mariusz Marszałkowski <m...@g...com> wrote:
>
> > On 21 Sty, 09:28, Wit Jakuczun <w...@g...com> wrote:
>
> > > On 21 Sty, 09:18, bartekltg <b...@g...com> wrote:
> > > 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.
>
> > 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.
>
> Mógłbyś doprecyzować wypowiedź bo nie bardzo załapałem co chciałeś
> przekazać?

Odnoszę wrażenie iż autorzy "wprowadzenie do algorytmów" twierdzą iż
złożonosć
jest jednak mniejsza niż N^3.

Pozdrawiam

do góry