Vlákno názorů k článku Příběhy z vývoje nejrychlejšího virtuálního stroje na světě od Jarda - Jen taková poznámka, ten vzorový program nepočítá prvočísla...
-
Jarda (neregistrovaný)
Jen taková poznámka, ten vzorový program nepočítá prvočísla Eratosthenovým sítem, ale běžným algoritmem na prvočísla. Eratosthenovo síto funguje ve stručnosti tak, že si vezmu seznam prvních N čísel. Pak vezmu první prvočíslo (tj. 2) a v seznamu škrtnu všechny jeho násobky. Pak dělám postupně totéž pro další prvočísla. Nakonec mi zůstanou jen prvočísla. Mimochodem tento algoritmus, pokud se správně napíše, tak bude v normálním C mnohem rychlejší, než v čemkoliv jiném.
-
Je to tak. Složitost mé verze je určitě větší než té verze s polem. Víceméně se podobá funkcionálnímu řešení a tudíž to není to Eratosthenovo síto. Na druhou stranu, algoritmus je ve všech jazycích stejný. Proto by porovnání měla být férová.
S poslední větou si dovolím nesouhlasit. Nevidím důvod, proč by to tak mělo být. Ale uznávám, že by se to muselo zkusit.
-
Karel (neregistrovaný)
Ad poslední věta: ten algoritmus tráví drtivou většinu času v miniaturní smyčce. C se přeloží jen na několik velmi málo instrukcí assembleru, takže režie na "škrtnutí" jednoho čísla bude víceméně jen v přičtení, zápisu do paměti a skoku. C nemusí být nutně "mnohem rychlejší", ale rozhodně bude na hranici, kterou daný HW zvládne. Dokud je algoritmus založen na přičtení, zápisu (=škrtnutí) a opakování, tak sebelepší algoritmus strojové optimalizace nemůže dopadnout lépe.
Optimalizace nestrojová samozřejmě lépe dopadnout může a dopadne, kupříkladu při vyškrtávání čísla X > 2 stačí vyškrtat jen čísla (2*k+1)*X (čili nepřičítáme X, ale 2*X). Důvod? Protože sudé násobky X už vyškrtala dvojka. Obecně se pro každé X dá určit počáteční koeficient, od kterého má smysl začít škrtat. Kupříkladu u čísla 13 nemá smysl škrtat 26, 52, 78 atd. (už škrtla dvojka), ani 39 nebo 117 (škrtla trojka), ani 65 (škrtla pětka) atd. Stačí škrtat od čísla 13*13 a přičítat 2*13. Tohle ale žádné VM nedokáže odhalit.
