strojove porovnani dvou algoritmu rubrika: Programování: Jiné

2 voidplace1
položil/-a 5.7.2015

Rekneme, ze mam dva Javascript scripty, ktere dosahuji stejneho vystupu ruznou implementaci.
Rekneme, ze treba resi vypocet Fibonacciho posloupnosti.
Jakym zpusobem by se dala automatizovane ohodnotit narocnost tech algoritmu? Zajimala by me pametova narocnost, casova, CPU usage, trida slozitosti algoritmu (https://cs.wikipedia.org/wiki/Asymptotick%C3%A1_slo%C5%BEitost).
Zajimaji me jakekoliv napady na reseni kterekoliv zminene metriky, pripadne navrhy jinych metrik, jak ty algoritmy kvalitativne porovnat.

Ty metriky nemusi byt 100% spolehlive. Jde v podstate o ohodnocovaci funkci pro selekci lepsiho reseni, pri generovani tech reseni.

Zatim me napadly jen nejake hodne lame veci typu vzit nejaky javascript syntax tokenizer a za kazdy prikaz hodit increment poctu kroku algoritmu. Dal neco jako spustit to v nejakem debug enginu a vyuzit API k nemu (to by bylo ale asi desne pomale).
Co se tyka mereni vyuziti pameti, casu a CPU, zatim uvazuji, ze to pobezi na nejakem beznem OS, takze nemuzu vyloucit konzumaci syst. prostredku nesouvisejicimi procesy. Jak se resi nejaka izolace mereni v tom?

Jedna se o zcela hypotetickou, dilcii ulohu. Zatim :).
Dik.

odkaz Vyřešeno
9 Taco
odpověděl/-a 5.7.2015

No, javascript je na to docela blbej jazyk, ale postupoval bych takto:

  1. Vytvořit si sandbox
  2. Připravit si testovací data
  3. Vygenerovat test
  4. Spustit a sledovat zajímavé hodnoty: vytížení procesoru, čas, paměť,...
  5. Vygenerovat koláčový graf

Troufl bych si říct, že nejsložitější je spíše získat dostatečně přesnou signaturu. Aby si do toho nemusel ládovat příliš mnoho dat. Na tohle jsou staticky typovaný jazyky lepší. Taky se tomu dá pomoc, že si zkusíš vlézt do implementace, a koukneš se, jaké funkce to volá, a jakého typu jsou ony. A od toho to zpětně odvodíš.

Teda, vlastně ani nevím, jak k těm funkcím chceš přistupovat. Pokud máš funkci pro výpočet Fibonacciho posloupnosti, tak tam je to daný, a celý můj přechozí odstavec můžeš vypustit.

Komentáře

  • voidplace1 : Diky za postrehy! Nakonec pro zakladni concept-proof mi tahle cesta asi taky dava nejvetsi smysl. Teda nez se snazit ohodnotit alg. jeho analyzou (treba pocet kroku apod.), tak merit jen spotrebu zdroju (pamet, cpu, cas) pro ruzne vstupy. Efektivnost algoritmu bude mit nejvetsi vahu jen pro jednu tridu problemu, takze nad tim asi ani nebudu palit cas. Jenom - na javascriptu vlastne ani netrvam. Dulezite je pro me spustit a ohodnotit co nejvetsi mnozstvi variant algoritmu v case (rekneme, ze variant je nekonecno), s tim, ze ty algoritmy budou relativne jednoduche scripty, ktere nepobezi dlouho. Dulezite je teda pro me to co nejrychleji jednorazove spustit. Rikal jsem si, ze interpretovane jazyky mi v tomohle vyjdou asi podstatne lip (spustit jednorazove JS s V8 enginem vs neco nejdriv treba vecnost kompilovat v jave/C#/C a pak teprve spustit). Co tak sleduju znas jazyku urcite vic nez ja, zda se ti ten predpoklad spravny? Signatura by problem byt nemela. Bude v podstate vzdy stejna, byt ty objekty reprezentujici vstupy se pro nejake typy problemu budou lisit. Omlouvam se za vagni konceptualni popis. Jednak jde zatim hlavne o myslenkovy experiment a ten samotny ucel zatim nechci uplne prozradit (byt je neskodny). — 5.7.2015
  • Taco : Bude to dělat stroj, ne? Tak jestli to bude kompilovat, no tak ať si to užije. Připravíš konfiguraci, spustíš přes víkend, a v pondělí si vyzvedneš výsledky. — 5.7.2015
  • Taco : Co se týče volby jazyka, to máš těžký, protože, alespoň jak na to pohlížím, ten samý algoritmus v javascriptu bude mět jiné výsledky než v C. Možná by se to dalo nějak generalizovat, určitě tam bude nějaká korelace, ale nad tím jsem nikdy neuvažoval. — 5.7.2015
  • rs : Pockej to chces rict ze treba QuickSort bude mit jinou tridu slozitosti pokud ho napises v JavaScriptu nebo C++ ? To je prece nesmysl algoritmu je definovana posloupnost ukonu a je +- jedno v cem to napises. Jasne jeden jazyk muze byt rychlejsi nez druhy ale to nema vliv na casovou slozitost jako takovou. Plus samozrejme nektere prekladace muzou optimalizovat kod lepe jine hure ale zase obecne v tom nebude rozdil. — 5.7.2015
  • Taco : @salacr: Tak jednak QuickSort je již konkrétní implementace, a signatura je u QuickSortu a třeba BubbleSortu stejná. A druhak jsem měl na mysli právě ty optimalizace. Třeba když střelím od oka, implementace v Javě se může pro malá a pro velká čísla chovat výrazně jinak, než implementace v C. Asi. Pohlížím na to z pohledu zvnějšku, kdy QuickSort je čistě název pro blackbox. — 5.7.2015
  • Honza Břešťan : Rozdil muze treba delat, jestli je QS implementace in-place a nebo vytvari nova pole (to algoritmus nespecifikuje, daji se udelat obe varianty, runtime navic muze mit svoje vlastni slovo - napr. persistent data structures). Pak budou alokace a dealokace hodne ovlivnovat prostorovou slozitost, ale i pozorovany cas. Obecne to je halting problem, takze je jasne, ze jakakoliv aproximace proste bude mit svoje mouchy... — 5.7.2015
  • Havri : No, nebyl bych si jistý, že na jazyku nezáleží. Céčko mi nabízí konstantní časovou složitost při přístupu k prvkům v poli. Pokud bychom měli nějaký hypotetický jazyk, který by tuto vlastnost neměl a přístup k prvkům v seznamu by dělal v lineárním čase, nemuseli bychom ani některé jiné algoritmy naprogramovat se stejnou časovou složitostí. Nicméně běžné jazyky typu JavaScript/PHP atp. mají AFAIK seznamy jako hash tabulky a ty mají konstantní složitost při přístupu k prvkům. — 5.7.2015
  • rs : Na co jsem narazel je tvrzeni: "ten samý algoritmus v javascriptu bude mět jiné výsledky než v C." tak samozrejme ze v javascriptu bude pomalejsi ale pokud to bude opravdu ten sami algoritmus. Tak by mel mit i stejne vysledky ve smyslu v obou jazycich bude jeho casova narocnost linearni. — 5.7.2015

Pro zobrazení všech 4 odpovědí se prosím přihlaste:

Rychlé přihlášení přes sociální sítě:

Nebo se přihlaste jménem a heslem:

Zadejte prosím svou e-mailovou adresu.
Zadejte své heslo.

Aktuální otázky v rubrice Programování: Jiné

Otázky uživatele voidplace1