Zarábaj až 6 000 € mesačne! Akreditované rekvalifikačné kurzy od 0 €. Viac informácií.

Diskusia – Ako nájsť najkratšiu cestu z bodu A do bodu B?

Späť

Upozorňujeme, že diskusie pod našimi online kurzami sú nemoderované a primárne slúžia na získavanie spätnej väzby pre budúce vylepšenie kurzov. Pre študentov našich rekvalifikačných kurzov ponúkame možnosť priameho kontaktu s lektormi a študijným referentom pre osobné konzultácie a podporu v rámci ich štúdia. Toto je exkluzívna služba, ktorá zaisťuje kvalitnú a cielenú pomoc v prípade akýchkoľvek otázok alebo projektov.

Komentáre
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovedá na Kit
Lukáš Hruda:25.3.2013 15:29

Řekl bych, že u kolekce hodně záleží na tom, co na ní má být rychlé. Pokud nepotřebuji měnit velikost nebo pouze občas či výjimečně, je nejlepší pole. Pokud potřebuji často měnit velikost, pak záleží, jestli potřebuji měnit velikost kompletně nebo pouze přidávat/odebírat jednotlivé prvky. Pak záleží na tom, jestli je potřebuji přidávat/odebírat pouze na konci nebo i veprostřed nebo na začátku. Pak záleží, jestli chci aby bylo rychlé spíše měnění velikosti nebo přístup k prvkům. Pak také záleží jestli mi záleží na spotřebě paměti. Prostě všechno záleží :D ...pro každou situaci je potřeba jiná optimalizace.

Tím ale netvrdím, že programátor udělá optimalizaci vždy lépe než kolekce.

Editované 25.3.2013 15:32
 
Odpovedať
25.3.2013 15:29
Avatar
Kit
Tvůrce
Avatar
Odpovedá na Lukáš Hruda
Kit:25.3.2013 15:46

Po kolekcích je požadována hlavně robustnost a spolehlivost. Rychlost bývá až na dalších pozicích. Přesto bývají některé kolekce lépe vytuněné, než bych byl schopen nebo ochoten naprogramovat.

Když jsem potřeboval vynásobit 2 matice 5000×5000 prvků, knihovní funkce byla řádově rychlejší, než můj triviální program. Funkci sinus nebo logaritmus se také neobtěžuji programovat a raději použiji funkci z knihovny.

Některé kolekce mají přímo vestavěno binární vyhledávání, o kterém tady byla řeč. Proč je tedy nevyužít?

Odpovedať
25.3.2013 15:46
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovedá na Kit
Luboš Běhounek Satik:25.3.2013 15:51

Pokud je tvůj kód pomalejší, než kód nějaké kolekce, pak to není tím, že by byla kolekce tak rychlá, ale tím, že tvůj kód je tak pomalý.

Napsat kód na míru algoritmu tak, aby byl rychlejší, než standardní kolekce moc práce většinou nedá.

Odpovedať
25.3.2013 15:51
https://www.facebook.com/peasantsandcastles/
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovedá na Kit
Luboš Běhounek Satik:25.3.2013 15:58

Právě kvůli robustnosti nemůžou být kolekce rychlejší, než vlastní kód.

Knihovní funkce mohou být rychlejší třeba proto, že využívají HW podpory - ty matice třeba MMX, sin nebo log jsou přímo asm instukce, takže je nesmysl je psát sám, hw to udělá vždy rychleji, než sw.

I když má kolekce binární vyhledávání, pořád je to jenom kolekce - má velkou režii kvůli obecnosti a robustnosti - např. můj vlastní C# string sortovač byl cca řádově rychlejší, než ten vestavěný...

Odpovedať
25.3.2013 15:58
https://www.facebook.com/peasantsandcastles/
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovedá na Luboš Běhounek Satik
Lukáš Hruda:25.3.2013 16:00

Záleží taky na jazyce, třeba v C++ je vektor skoro stejně rychlý jako pole, přitom umí i přidávat a odebírat prvky. Ovšem pouze na konec, změna velikosti v jiné části vektoru už je mnohem pomalejší. Tím se dostávám zpět k tomu, že záleží na situaci a na tom, co programátor zrovna potřebuje.

 
Odpovedať
25.3.2013 16:00
Avatar
Kit
Tvůrce
Avatar
Odpovedá na Luboš Běhounek Satik
Kit:25.3.2013 16:00

Jaký používáš algoritmus na násobení matic? Podotýkám, že matice mají rozměr 5000×5000. Mně by se s tím tedy programovat nechtělo.

Odpovedať
25.3.2013 16:00
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Kit
Tvůrce
Avatar
Odpovedá na Luboš Běhounek Satik
Kit:25.3.2013 16:04

Funkce sinus ani logaritmus nejsou v HW, píší se většinou ve Fortranu. V embedded zařízeních, kde záleží na rychlosti, se obvykle dělají tabulkami.

Odpovedať
25.3.2013 16:04
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovedá na Kit
Luboš Běhounek Satik:25.3.2013 16:30

Netuším, takhle velké matice jsem zatím násobit nepotřeboval.

Když sinus ani logaritmus nejsou implementovány v hw, tak k čemu je podle tebe třeba asm instrukce fsin ? To by mě vážně zajímalo :D

Editované 25.3.2013 16:31
Odpovedať
25.3.2013 16:30
https://www.facebook.com/peasantsandcastles/
Avatar
Kit
Tvůrce
Avatar
Odpovedá na Luboš Běhounek Satik
Kit:25.3.2013 16:49

No dobrá, instrukce fsin se objevila poprvé v procesorech 387, přehlédl jsem to. Ve 386 ještě nebyla.

Klasickým algoritmem pro násobení matic by to trvalo dost dlouho, proto se to počítá rychlejšími algoritmy, které jsou ale podstatně delší a komplikovanější. Někdo je však přede mnou napsal a jsou fakt kvalitní.

Velké matice se násobí poměrně často zejména v různých simulacích fyzikálních dějů a při prezentaci grafiky. Některé grafické karty to mají vestavěno.

Odpovedať
25.3.2013 16:49
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Mircosoft
Tvůrce
Avatar
Mircosoft:26.3.2013 11:47

Díky za podnětnou diskusi o kolekcích, maticích a hardwaru, ale už jsme poněkud off-topic.

Účelem článku bylo vysvětlit algoritmus hledání cesty na obecné úrovni, aby si ho každý mohl implementovat a optimalizovat po svém, ne poskytnout hotový, přímo použitelný kód. Jestli chcete napsat něco lepšího, směle do toho ;).

 
Odpovedať
+1
26.3.2013 11:47
Robíme čo je v našich silách, aby bola tunajšia diskusia čo najkvalitnejšia. Preto do nej tiež môžu prispievať len registrovaní členovia. Pre zapojenie sa do diskusie sa zaloguj. Ak ešte nemáš účet, zaregistruj sa, je to zadarmo.

Zobrazené 10 správy z 20.