On 18 Sty, 20:26, Mariusz Marszałkowski <m...@g...com> wrote:

> 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