Forum » Programiranje » Časovna zahtevnost Dijkstrovega algoritma
Časovna zahtevnost Dijkstrovega algoritma
neoto ::
Zanima me, v kolkem času ponavadi ta procedura opravi s 500.000 točkami, urejenimi v neusmerjeno mrežo brez dodatnih pogojev za izločanje?
Je velika razlika, če se uporabi še prioritetna vrsta?
Je velika razlika, če se uporabi še prioritetna vrsta?
Gundolf ::
Spiši program in poženi pa boš videl. Drugače je pa preveč odvisno od sistema na katerem ga poganjaš, kako dobro znaš spisati algoritem in mislim da tudi od grafa, ki ga preizkuješ. Drugače se pa zdajle sploh ne spomnim točno kako izgleda Dijkstra 
neoto ::
Sej ravno to je. Program imam, algoritem se izvaja precej dolgo, zato me zanima malo primerjava z drugimi, da vidim, koliko je še možnosti za izboljšave...
Gundolf ::
Pol miljona točk je veliko. Možna optimizacija je z upoštevanjem strukture grafa. Saj praviš da imaš mrežo (verjetno 2D).
Primoz ::
bi bil pripravljen delit to modrost še z ostalimi?
There can be no real freedom without the freedom to fail.
neoto ::
Ja no, fora je v tem, da sem proceduro najprej temeljil na enem izmed primerov, ki sem jih našel na internetu. Pri tem načinu sem pri iskanju točke z najmanjšo oddaljenostjo uporabljal dvojno for zanko, ki se je pri 500.000 točkah izvajala obupno počasi. Zdaj sem pa to celotno proceduro prilagodil tako, da uporablja prioritetno vrsto in sem s tem odpikal iskanje po vseh točkah.
In da povzamem, glede na to, da se v VB-ju for zanke izvajajo izjemno počasi, sem lahko z odpravitvijo teh zank celotno zadevo zelo opazno pohitril...
In da povzamem, glede na to, da se v VB-ju for zanke izvajajo izjemno počasi, sem lahko z odpravitvijo teh zank celotno zadevo zelo opazno pohitril...
OwcA ::
Hočeš reči, da se stvar izvaja za en velikostni red manj časa?
Otroška radovednost - gonilo napredka.
Zgodovina sprememb…
- spremenilo: OwcA ()
neoto ::
Prej dva ali pa tri. Prej sem pustil računalnik pol ure, pa še ni dokončal vseh točk, zdaj pa čez vse točke pride v 2-3 minutah (program je napisan v VB-ju, ki je precej počasen!)
Sergio ::
OwcA: da, za en velikostni red :)
neoto: to je en velikostni red. Iz n^2 si prisel na nlogn
neoto: to je en velikostni red. Iz n^2 si prisel na nlogn
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
neoto ::
Bi rekel da za najmanj 20-40%, če bi to napisal v javi ali pa do 50% če bi pisal v c++.
Če bi imel cilj zadevo naredit še hitrejšo, vem kaj moram narediti...
Če bi imel cilj zadevo naredit še hitrejšo, vem kaj moram narediti...
neoto ::
Se strinjam da bi se dalo vse skupaj pohitrit (sploh če izklopim izrisovanje stanja, pa računanje hitrosti,...).
Thomas, glede one alternative: je to sploh open source algoritem?? Namreč jaz dvomim da je, pa malo čudna se mi zdi njihova stran. Če že ponujanjo nekaj tako hitrejšega, si bi pa le lahko malo privoščili za imidž...
Thomas, glede one alternative: je to sploh open source algoritem?? Namreč jaz dvomim da je, pa malo čudna se mi zdi njihova stran. Če že ponujanjo nekaj tako hitrejšega, si bi pa le lahko malo privoščili za imidž...
Zgodovina sprememb…
- spremenil: neoto ()
darkolord ::
Glede tistga, da se da v VBju pohitrit sm mislu tudi bolj na splošno... namreč obstaja ene par ljudi, ki obsesivno optimizirajo VB kodo in so prisli do kar lepih rezultatov 
OwcA ::
darko: ti ljudje se lahko na glavo postavijo, pa bo stvar, pri isti časovni zahtevnosti, še vedno prav tragično propadla, če zvečamo vhodne podatke za velikosten razred. Žal.
Otroška radovednost - gonilo napredka.
Thomas ::
C++, basic, assembler ... vse to je ista figa. Dobiš samo nek konstantni faktor izboljšanja z uporabo enega ali drugega ali tretjega progranskega jezika oziroma kompajlerja.
Pri algoritmih pa skušamo dobiti nekaj več, kot je samo linearno izboljšanje. Včasih gre, drugič ne.
Pri algoritmih pa skušamo dobiti nekaj več, kot je samo linearno izboljšanje. Včasih gre, drugič ne.
Man muss immer generalisieren - Carl Jacobi
CCfly ::
Dva tedna optimiziraš kodo, namesto da bi razmišljal, kako zmanjšati število točk v drevesu.
edit: se oproščam vozlišč.
edit: se oproščam vozlišč.
"My goodness, we forgot generics!" -- Danny Kalev
Zgodovina sprememb…
- spremenilo: CCfly ()
64202 ::
> Pri algoritmih pa skušamo dobiti nekaj več, kot je samo linearno izboljšanje. Včasih gre, drugič ne.
Se ne bi branil, ce mi kdo za x-krat pohitri g++ :)
Se ne bi branil, ce mi kdo za x-krat pohitri g++ :)
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | HDD - neizbežne napake pri branju (URE)Oddelek: Strojna oprema | 3966 (3321) | MrStein |
| » | IBM odkril nov način uporabe ogljikovih nanocevk v tranzistorjihOddelek: Novice / Znanost in tehnologija | 5661 (3120) | zavajon |
| » | [Algoritem] Kako do najkrajše poti na med točkamiOddelek: Programiranje | 3037 (2625) | Spura |
| » | [VB.NET] Izpisovanje v TextBox in prekinitveOddelek: Programiranje | 1183 (876) | darkolord |
| » | Najhitrejši programski jezik? (strani: 1 2 )Oddelek: Programiranje | 7422 (5242) | Senitel |