NOVINKA - Online rekvalifikační kurz Python programátor. Oblíbená a studenty ověřená rekvalifikace - nyní i online.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Diskuze – Lekce 3 - Jak najít nejkratší cestu z bodu A do bodu B?

Zpět

Upozorňujeme, že diskuze pod našimi online kurzy jsou nemoderované a primárně slouží k získávání zpětné vazby pro budoucí vylepšení kurzů. Pro studenty našich rekvalifikačních kurzů nabízíme možnost přímého kontaktu s lektory a studijním referentem pro osobní konzultace a podporu v rámci jejich studia. Toto je exkluzivní služba, která zajišťuje kvalitní a cílenou pomoc v případě jakýchkoli dotazů nebo projektů.

Komentáře
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá 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.

Editováno 25.3.2013 15:32
 
Odpovědět
25.3.2013 15:29
Avatar
Kit
Tvůrce
Avatar
Odpovídá 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?

Odpovědět
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
Odpovídá 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á.

Odpovědět
25.3.2013 15:51
https://www.facebook.com/peasantsandcastles/
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovídá 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ý...

Odpovědět
25.3.2013 15:58
https://www.facebook.com/peasantsandcastles/
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá 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.

 
Odpovědět
25.3.2013 16:00
Avatar
Kit
Tvůrce
Avatar
Odpovídá 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.

Odpovědět
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
Odpovídá 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.

Odpovědět
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
Odpovídá 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

Editováno 25.3.2013 16:31
Odpovědět
25.3.2013 16:30
https://www.facebook.com/peasantsandcastles/
Avatar
Kit
Tvůrce
Avatar
Odpovídá 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.

Odpovědět
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 ;).

 
Odpovědět
26.3.2013 11:47
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 20.