Forum » Znanost in tehnologija » Išče se hiter algoritem za izračun ene čudne matrične operacije.
Išče se hiter algoritem za izračun ene čudne matrične operacije.
ciki57 ::
Definirano imamo operacijo na kvadratnih matrikah velikosti n*n:
C = A * B
c(i,j) = min{ a(i,k) + b(k,j) }, kjer k teče od 1 do n.
Časnovna zahtevnost algoritma za izračun tega je O(n^3).
Zahtevnost običajnega matričnega množenja takisto O(n^3), vendar se ga da s Strassenovo metodo izboljšati na O(n^2.8).
A ma mogoče kdo kakšno idejo če bi se dalo kako izboljšati tudi zahtevnost zgoraj napisane operacije??
A je možna še kakšna dodatna izboljšava, če sta matriki A in B enaki (C = A * A)?
C = A * B
c(i,j) = min{ a(i,k) + b(k,j) }, kjer k teče od 1 do n.
Časnovna zahtevnost algoritma za izračun tega je O(n^3).
Zahtevnost običajnega matričnega množenja takisto O(n^3), vendar se ga da s Strassenovo metodo izboljšati na O(n^2.8).
A ma mogoče kdo kakšno idejo če bi se dalo kako izboljšati tudi zahtevnost zgoraj napisane operacije??
A je možna še kakšna dodatna izboljšava, če sta matriki A in B enaki (C = A * A)?
drejc ::
Mas rad hitre avte?... Spust se mal globje v optimizacijo, pa boš pun ko đajo (če ti kej seveda uspe:).
Thomas ::
Za začetek vzamemo naivni algoritem. O(n^4).
Za vsak par elementov iz A in B matrike preveri, če imata eden isto x, kot drugi y koordinato. Če ja, potem ju seštejemo. Če je vsota manjša od elementa na koordinatah x,y - ga nadomestimo s to vsoto.
Uporabimo pa Cjevsko notacijo, kjer je matrika interpretirana iz enodimenzionalnega niza.
int TAB[1000];int i=0;int j=0;int k=0;int l=0;int m=0;int n=0;int o=0;int p=0;int q=0;int r=0;int s=0;int x=0;
q=3;
p=9;
//C
//F TAB[26]
//R TAB
i=0;
while (i < q) {
Potem dame zadevo v Critical ver. 1.0 beta in čakamo kaj bo ...
Kakršna koda bo že prišla ven - postana bo sem.
Za vsak par elementov iz A in B matrike preveri, če imata eden isto x, kot drugi y koordinato. Če ja, potem ju seštejemo. Če je vsota manjša od elementa na koordinatah x,y - ga nadomestimo s to vsoto.
Uporabimo pa Cjevsko notacijo, kjer je matrika interpretirana iz enodimenzionalnega niza.
int TAB[1000];int i=0;int j=0;int k=0;int l=0;int m=0;int n=0;int o=0;int p=0;int q=0;int r=0;int s=0;int x=0;
q=3;
p=9;
//C
//F TAB[26]
//R TAB
i=0;
while (i < q) {
- j=0;
while (j < q) {
- x=i*q;
x=x+j;
x=x+p;
x=x+p;
o=255;
TAB[x]=o;
k=0;
while (k < q) {
- l=0;
while (l < q) {
- if (k==l) {
- o=i*q;
o=o+l;
x=k*q;
x=x+p;
x=x+j;
m=TAB[o];
n=TAB[x];
m=m+n;
o=i*q;
o=o+j;
o=o+p;
o=o+p;
r=TAB[o];
if (m < r) {
- TAB[o]=m;
l++;
k++;
j++;
i++;
Potem dame zadevo v Critical ver. 1.0 beta in čakamo kaj bo ...
Kakršna koda bo že prišla ven - postana bo sem.
Man muss immer generalisieren - Carl Jacobi
Thomas ::
Tole je en tak vmesen (?) rezultat, za katerega velja O(n^3).
int TAB[100];int i=0;int j=0;int k=0;int l=0;int m=0;int n=0;int o=0;int p=0;int q=0;int r=0;int x=0;
q=3;
p=9;
while (i < q) {
int TAB[100];int i=0;int j=0;int k=0;int l=0;int m=0;int n=0;int o=0;int p=0;int q=0;int r=0;int x=0;
q=3;
p=9;
while (i < q) {
- j=0;
while (j < q) {
- x=i*q;
x=x+j;
x=x+p;
x=x+p;
TAB[x]=x;
l=0;
while (l < q) {
- o=i*q;
o=o+l;
x=l*q;
x=x+p;
x=x+j;
m=TAB[o];
n=TAB[x];
m=m+n;
o=i*q;
o=o+j;
o=o+p;
o=o+p;
r=TAB[o];
if (m < r) {
- TAB[o]=m;
l++;
j++;
i++;
Man muss immer generalisieren - Carl Jacobi
cRaZY ::
Ampak strassen prispara pri mnozenjih in jih nadoknadi z precej vec sestevanji... pa je zato hitrejs... mislim da iz 8 mnozenj pride na 7, ampak dobi 16 sestevanj.
V tem primeru pa sploh ni nobenega mnozenja...
Naj napisem do konca od tele seminarske... izracunati je treba A^(n-1) teh operacij torej n matrik A zracunat po tej operaciji.
Kako vam gre kej hitrost? jest sm spravu 1000x1000 matriko na 48.5s na P4, na isto po oznakah hitrem athlonu pa tocno 1x pocasneje.. zanimivo :)
lp
PEter.
V tem primeru pa sploh ni nobenega mnozenja...
Naj napisem do konca od tele seminarske... izracunati je treba A^(n-1) teh operacij torej n matrik A zracunat po tej operaciji.
Kako vam gre kej hitrost? jest sm spravu 1000x1000 matriko na 48.5s na P4, na isto po oznakah hitrem athlonu pa tocno 1x pocasneje.. zanimivo :)
lp
PEter.
cRaZY ::
Thomas, pa se tale algoritemcek mal serje, ane?
Nekak prepises tabelo...
ala, v 1. vrstici in 1. stolpcu najdes minimum in ga vpises na koordinato [1,1] (oz 0, ampak pustmo to). Potem pa gres gledat 1. vrstico in 2. stolpec, pri tem pa beres koordinato [1,1], ki si jo prej povozil, mogla pa bi biti originalna...
lp
PEter.
Nekak prepises tabelo...
ala, v 1. vrstici in 1. stolpcu najdes minimum in ga vpises na koordinato [1,1] (oz 0, ampak pustmo to). Potem pa gres gledat 1. vrstico in 2. stolpec, pri tem pa beres koordinato [1,1], ki si jo prej povozil, mogla pa bi biti originalna...
lp
PEter.
ciki57 ::
Meni je zaenkrat uspelo 1000x1000 matriko spraviti na 20 do 30 sekund (odvisno kakšni so elementi matrike) na Duronu 1300.
Treba je še upoštevati da linux laufam na windowsih pod vmwarom in je zato malo počasneje.
Običajen algoritem pa mi stvar naredi v približno 600 sekundah . Ne glede na matriko.
Treba je še upoštevati da linux laufam na windowsih pod vmwarom in je zato malo počasneje.
Običajen algoritem pa mi stvar naredi v približno 600 sekundah . Ne glede na matriko.
Thomas ::
Oba algoritma bi morala delati prav.
S to predpostavko, da je v prvem o=255; treba pač postaviti dovolj visoko, da vsota ne presega. o=99999.
Ali pa še bolje, kar 2 krat maksimalni element obeh matrik.
Critical bo še malček pooptimiziral popoldne enkrat.
S to predpostavko, da je v prvem o=255; treba pač postaviti dovolj visoko, da vsota ne presega. o=99999.
Ali pa še bolje, kar 2 krat maksimalni element obeh matrik.
Critical bo še malček pooptimiziral popoldne enkrat.
Man muss immer generalisieren - Carl Jacobi
Zgodovina sprememb…
- spremenil: Thomas ()
cRaZY ::
Ciki: a 20-30 sekund ti traja ta operacija al N takih operacij pri matriki 1000x1000?
Thomas: am, ti mas samo eno tabelo... in si prepises vrednosti, ki jih mors uporablat... lej:
|1 2|
A =|3 4|
C=A*A
|1 2| |1 2| |2 3|
|3 4| * |3 4| = |4 5|
drugo matriko dobis takole:
C[0,0] = min((1+1),(2+3)) = 2;
C[0,1] = min((1+2),(2+4)) = 3;
C[1,0] = min((3+1),(4+3)) = 4;
C[1,1] = min((3+2),(4+4)) = 5;
Ti pa pises v ISTO matriko, in ti ze na drugem koraku zajebes, ker:
C[0,0] = min((1+1),(2+3)) = 2;
C[0,1] = min((2+2),(2+4)) = 4;
Sicer mozn da ti indexi ne tecejo glih tko, ker si mal drugac naredu zanke, sam prej al slej se prepises... v vsakem primeru moras rezultat pisat v drugo matriko...
lp
PEter.
Thomas: am, ti mas samo eno tabelo... in si prepises vrednosti, ki jih mors uporablat... lej:
|1 2|
A =|3 4|
C=A*A
|1 2| |1 2| |2 3|
|3 4| * |3 4| = |4 5|
drugo matriko dobis takole:
C[0,0] = min((1+1),(2+3)) = 2;
C[0,1] = min((1+2),(2+4)) = 3;
C[1,0] = min((3+1),(4+3)) = 4;
C[1,1] = min((3+2),(4+4)) = 5;
Ti pa pises v ISTO matriko, in ti ze na drugem koraku zajebes, ker:
C[0,0] = min((1+1),(2+3)) = 2;
C[0,1] = min((2+2),(2+4)) = 4;
Sicer mozn da ti indexi ne tecejo glih tko, ker si mal drugac naredu zanke, sam prej al slej se prepises... v vsakem primeru moras rezultat pisat v drugo matriko...
lp
PEter.
Zgodovina sprememb…
- spremenil: cRaZY ()
Thomas ::
Ne. Vse tri matrike so v arrayu TAB.
A na začetku, B na sredi in C na koncu.
V začetku so dimenzije matrike.
A na začetku, B na sredi in C na koncu.
V začetku so dimenzije matrike.
Man muss immer generalisieren - Carl Jacobi
ciki57 ::
Fora je, da ugotavljamo minimalen element, zato ni treba pregledati vse elemente kot pri običanjem matričnem množenju. Če si malce pomagamo s sortiranjem vrstic, lahko z iskanjem najmanjšega nehamo še predem pridemo do konca, samo pravilne pogoje je treba postaviti...
Tistemu izrazu A*A*A*A..*A pa se da zaradi asociativnosti opracije časovno zahtevnost z O(n) zmanjšati na O(logn)
Tistemu izrazu A*A*A*A..*A pa se da zaradi asociativnosti opracije časovno zahtevnost z O(n) zmanjšati na O(logn)
Thomas ::
Smo dal zdejle algoritem mau optimizirat (šele).
Bom ga zjutrej tle sem napisal, če bo sreča z elektriko in ostalim.
Bom ga zjutrej tle sem napisal, če bo sreča z elektriko in ostalim.
Man muss immer generalisieren - Carl Jacobi
Thomas ::
Mogoče je kdo opazil, da še nisem objavil optimiziranega algoritma, kakor sem bil obljubil.
Bo treba še malo počakat. Ker tisto kar je prišlo ven je dokaj čudno in rabi komentar. Ampak dela pa uredu.
Bo treba še malo počakat. Ker tisto kar je prišlo ven je dokaj čudno in rabi komentar. Ampak dela pa uredu.
Man muss immer generalisieren - Carl Jacobi
Vredno ogleda ...
Tema | Ogledi | Zadnje sporočilo | |
---|---|---|---|
Tema | Ogledi | Zadnje sporočilo | |
» | Python - pomoč!Oddelek: Programiranje | 1186 (1022) | lknix |
» | Digitalna evolucija (strani: 1 2 3 4 … 26 27 28 29 )Oddelek: Znanost in tehnologija | 75185 (25354) | pietro |
» | Java ObjektiOddelek: Programiranje | 2221 (1915) | Mavrik |
» | [JavaScript] Sortiranje šumnikovOddelek: Programiranje | 2123 (1857) | MarkookraM |
» | cene permutacij help pleaseOddelek: Programiranje | 2047 (1654) | Sergio |