Coders' city Nasza pasja to programowanie!    Pomoc   Szukaj   Użytkownicy   Grupy  Rejestracja  Archiwum starego forum + teoria    RSS & Panel/SideBar  Profil   Zaloguj się, by sprawdzić wiadomości   Zaloguj  Potrzebuję szybkiej odpowiedzi na moje pytanie... Skrócony regulamin Algorytm strassena dla macierzy prostokątnych      Forum Coders' city Strona Główna -> Algorytmy + inżynieria oprogramowania Zobacz poprzedni temat :: Zobacz następny temat   Autor Wiadomość Hashedone Dołączył: 23 Sie 2008 Posty: 853 Wysłany: Nie Lis 20, 2011 8:39 pm      Temat postu: Algorytm strassena dla macierzy prostokątnych Witam, implementuję włąśnie algorytm strassena. Jednak nie mogę znaleźć żadnej informacji na temat tego algorytmu dla macierzy o wymiarach nie będących potęgą dwójki ani macierzy prostokątnych. Ma ktoś jakieś źródła na ten temat? _________________ PWr, WPPT, Informatyka "Two or more? - use a for", Dijkstra Powrót do góry marcin_an Site Admin Dołączył: 26 Maj 2005 Posty: 17278 Skąd: z drugiej strony Kabla Wysłany: Nie Lis 20, 2011 8:50 pm      Temat postu: opis w pierwszym źródle Jak ja już dawno nie słyszałem tej nazwy... :D _________________ Matematyka to taki twór, który pozwala opisać sokowirówkę jako urządzenie pobierające ujemne odpadki i produkujące z nich sok. "Lameria atakuje" | RTFM | UMLet - edytor UML inaczej | Wykłady ks.Pawlukiewicza Powrót do góry Hashedone Dołączył: 23 Sie 2008 Posty: 853 Wysłany: Nie Lis 20, 2011 9:59 pm      Temat postu: Ale to jest dla macierzy kwadratowych, których wymiar jest potęgą dwójki. Patrząc na algorytm podejżewam (a wręcz jestem tego prawie pewien), że dało by się to uogólnić na macierze dowolne i pytam czy ktoś o tym słyszał. Biorąc pod uwagę, że mój program jest dwa lub trzy tygodnie spóźniony, a laborant ponoć już się pytał o mnie, podejżewam że każda dodatkowa wiedza o implementowanym algorytmie będzie dobra do poprawienia sobie sytuacji:D _________________ PWr, WPPT, Informatyka "Two or more? - use a for", Dijkstra Powrót do góry marcin_an Site Admin Dołączył: 26 Maj 2005 Posty: 17278 Skąd: z drugiej strony Kabla Wysłany: Pon Lis 21, 2011 2:29 am      Temat postu: Ugh... przeczytaj drugie zdanie wskazanego opisu... _________________ Matematyka to taki twór, który pozwala opisać sokowirówkę jako urządzenie pobierające ujemne odpadki i produkujące z nich sok. "Lameria atakuje" | RTFM | UMLet - edytor UML inaczej | Wykłady ks.Pawlukiewicza Powrót do góry Hashedone Dołączył: 23 Sie 2008 Posty: 853 Wysłany: Pon Lis 21, 2011 10:35 am      Temat postu: Boże, jaki ja jestem ślepy -.- Dzięki wielkie:) === EDIT === Faktycznie uogólnienie bardzo proste, tym bardziej do implementacji w Octave. Jeszcze raz dzięki, może jednak mi sie te numerki uda zaliczyć:D _________________ PWr, WPPT, Informatyka "Two or more? - use a for", Dijkstra Powrót do góry hurgadion Dołączył: 06 Kwi 2011 Posty: 143 Skąd: Kraków Wysłany: Wto Lis 22, 2011 1:25 pm      Temat postu: Witam, zainteresowałem się tematem mnożenia macierzy. Temat raczej standardowy, ale podczas implementacji klasycznego algorytmu mnożenia macierzy 100 x 100 dostałem ciekawe wyniki "szybkościowe." Dla tego samego algorytmu napisałem trzy makra (Excel VBA): Kod: Sub Mnozenie1() Dim i&, j&, k&, l& Dim tbl(), tbl1() Dim s As Single, t As Single s = Timer tbl = Range("A1:CV100") ReDim tbl1(1 To 100, 1 To 100) For j = 1 To 100   For i = 1 To 100     l = 0     For k = 1 To 100        l = l + tbl(i, k) * tbl(k, j)     Next k     tbl1(i, j) = l   Next i Next j Cells(105, 1).Resize(100, 100) = tbl1 t = Timer MsgBox t - s End Sub Sub Mnozenie2() Dim i&, j&, k& Dim t As Single, s As Single Dim tbl(), tbl100(), tbl200() ReDim tbl(1 To 100, 1 To 100) ReDim tbl100(1 To 100) ReDim tbl200(1 To 100) t = Timer For k = 1 To 100   tbl100(k) = Range(Cells(k, 1), Cells(k, 100))   tbl200(k) = Range(Cells(1, k), Cells(100, k)) Next k For i = 1 To 100   For j = 1 To 100     tbl(i, j) = Application.SumProduct(tbl100(i), Application.Transpose(tbl200(j)))   Next j Next i Cells(105, 1).Resize(100, 100) = tbl s = Timer MsgBox s - t End Sub Sub Mnozenie3() Dim i&, j&, k&, l& Dim s As Single, t As Single s = Timer ReDim tbl1(1 To 100, 1 To 100) For j = 1 To 100   For i = 1 To 100     l = 0     For k = 1 To 100        l = l + Cells(i, k).Value * Cells(k, j).Value     Next k     Cells(i + 104, j).Value = l   Next i Next j t = Timer MsgBox t - s End Sub Czas działania makra: Mnozenie1: 1,2 sek, Mnozenie2: 1,9 sek, Mnozenie3: 28 sekund. Wniosek: od samego algorytmu może być także istotny, jeżeli nie bardziej istotny sposób implementacji algorytmu, dobór właściwych "obiektów"/funkcji danego języka programowania oraz przede wszystkim dobór optymalnego języka (środowiska programistycznego). Są to rzeczy w miarę oczywiste, ale często się o nich nie wspomina w kontekście implementacji algorytmów, a są to rzeczy bardzo ważne... Hashedone: da się/próbowałeś mnożyć macierze np. w Prologu ? Pozdrawiam i sorki, jeżeli moja wypowiedź za bardzo podryfowała od głównego kierunku wyznaczonego przez temat wątku 100na100.rar  Opis: Pobierz  Nazwa pliku:  100na100.rar  Wielkość pliku:  12.63 KB  Pobierano:  10 raz(y) Powrót do góry Hashedone Dołączył: 23 Sie 2008 Posty: 853 Wysłany: Wto Lis 22, 2011 3:55 pm      Temat postu: W Prologu wszystko się da, a to jest akurat dość łatwe: Kod: transpose([], []). transpose([F|Fs], Ts) :-     transpose(F, [F|Fs], Ts). transpose([], _, []). transpose([_|Rs], Ms, [Ts|Tss]) :-         lists_firsts_rests(Ms, Ts, Ms1),         transpose(Rs, Ms1, Tss). lists_firsts_rests([], [], []). lists_firsts_rests([[F|Os]|Rest], [F|Fs], [Os|Oss]) :-         lists_firsts_rests(Rest, Fs, Oss). dot_product(L1, L2, DP) :-   dot_product(L1, L2, DP, 0), !. dot_product([], [], Acc, Acc) :- !. dot_product([A | L1], [B | L2], DP, Acc) :-   NAcc is Acc + A * B,   dot_product(L1, L2, DP, NAcc), !. mulmatrix_row(_, [], []) :- !. mulmatrix_row(A, [B | BTail], [DP | RTail]) :-   dot_product(A, B, DP),   mulmatrix_row(A, BTail, RTail), !.    mulmatrix_cols([], _, []) :- !. mulmatrix_cols([A | ATail], B, [Row | CTail]) :-   mulmatrix_row(A, B, Row),   mulmatrix_cols(ATail, B, CTail), !. mulmatrix(A, B, C) :-   transpose(B, BT),   mulmatrix_cols(A, BT, C), !. Jeśli masz SWI-Prologa możesz olać predykat traspose, a zamiast niego załadować sobie moduł clpfd (jest tam zdefiniowany dokładnie w ten sam sposób). Działa i to dla małych macierzy wystarczająco szybko. Nie chciało mi się sprawdzać jak sobie radzi z dużymi, ale jako że to są liczby to zawsze można przerobić ten program dość łatwo na technologię więzów - ale nie wiem czy w tym przypadku da to jakiekolwiek przyspieszenie (brak kolizji więzów), chyba że chciało by się taki predykat wykorzystać do szukania macierzy odwrotnej (wtedy już więzy byłyby konieczne). _________________ PWr, WPPT, Informatyka "Two or more? - use a for", Dijkstra Powrót do góry Wyświetl posty z ostatnich: Wszystkie Posty1 Dzień7 Dni2 Tygodnie1 Miesiąc3 Miesiące6 Miesięcy1 Rok Najpierw StarszeNajpierw Nowsze     Forum Coders' city Strona Główna -> Algorytmy + inżynieria oprogramowania Wszystkie czasy w strefie CET (Europa) Strona 1 z 1   Skocz do: Wybierz forum Podział tematyczny----------------Algorytmy + inżynieria oprogramowaniaBazy danychBibliotekiOprogramowanie biuroweWebmasterstwoElektronika, programowanie niskopoziomoweSprawy dotyczące forumSerwis vb4all.pl Środowiska i języki----------------C i C++Visual StudioPascal, Delphi, ...JavaPHPJavaScriptPythonInne języki skryptowe, przetwarzanie danychRodzina BASICInne języki Luźne działy----------------Sieci komputerowe i InternetKomputeryPraca oferowana / współpracaGiełdaPole do popisu (beta testy)Inne  Możesz pisać nowe tematy Możesz odpowiadać w tematach Nie możesz zmieniać swoich postów Nie możesz usuwać swoich postów Nie możesz głosować w ankietach Możesz dodawać załączniki na tym forum Możesz pobierać pliki z tego forum Debug: strone wygenerowano w 0.18551 sekund, zapytan = 9

| Darmowe programy i porady Jelcyna | VB4all | Tansze zakupy w Helionie |