Efektívne čítanie príkazov - C

Nazdar,

v rámci spoznávania a učenia sa jazyka C by som chcel urobiť obdobu Windowsáckeho 'cmd.exe'. Cez tento program by som mohol testovať rôzne svoje podprogramy, ktoré by som externe naprogramoval a tu vložil čisto vo forme funkcií, ktoré by užívateľ volal príkazom v CLI, teda napríklad zadaním "root 345 8" by vypočítalo a vypísalo ôsmu odmocninu čísla 345.

Program bude fungovať v nasledujúcich krokoch:
1. Cez funkciu 'fgets()' vloží do reťazca vstup užívateľa
2. Vstup následne spracuje, vymaže z neho nepotrebné znaky a rozdelí ho na niekoľko ďalších reťazcov - prikaz[]; arg1[]; arg2[];...
3. Teraz program cez 'switch case' zistí, či príkaz naozaj existuje. Ak áno, povolá danú funkciu, ak nie, vypíše chybovú hlášku a vráti program na začiatok.

Toto všetko by malo fungovať, resp. neočakávam žiadne väčšie ťažkosti, avšak problém vidím v bode 3. Každý jeden príkaz si totižto vyžaduje vlastný 'case', čo by pri väčšom počte funkcií mohlo byť nepriehľadné, ťažko editovateľné a neskôr aj pomalé a neefektívne.

Keď som si robil menší prehľad o programovacích jazykoch, zaujala ma funkcia Pythona 'exec'. Tá dokázala vykonať reťazec kódu uloženého v premennej. Niečo také by sa presne hodilo do môjho programu, avšak pokiaľ som dobre hľadal, tak v C, ani v C++ nič takéto nie je. Preto sa obraciam na skúsenejších programátorov - ako zefektívniť 3. bod tohto programu? Ide to vôbec?

Za vaše odpovede dopredu vďaka.

Čo presne sa ti tu zdá pomalé a neefektívne?

Samozrejme, podobná funkcia ako exec je v kompilovaných jazykoch nezmysel. Takže nie, nedá sa to. A ak by to aj niekto implementoval, tak až to by bolo neefektívne (real-time interpeter C-čka? no fuj)

S tou efektívnosťou mi ide o to, že program bude musieť prechádzať každým casom, kým nenarazí na zhodu alebo kým nedôjde na default. Čiže ak bude hľadať pokyny pre príkaz, ktorého case je úplne na konci, tak bude musieť kontrolovať všetky nad ním. Ak ich tam bude 200, tak 200 porovnaní.

Ako nehovorím, C je rýchly jazyk, čo dnešné CPU len znásobujú, ale aj tak, tlačiť systémovú záťaž dole nie je na škodu .

Ak dobre chápem čo chceš, tak v Cčku ich zopár je : http://en.wikipedia.org/wiki/Exec_(computing)#C_language_prototypes
Hodím ti aj príklad, čo sme mali na operačných systémoch :



Dodávam že príkaz je pre Unix jadro ...

No keď už ťa trápia takéto veci, tak dobre: Môžeš napríklad v príkazoch vyhľadávať rýchlejšie, než lineárne. Nepoužiješ podmienky, ale normálne vyhľadávanie a pri zoradených príkazoch môžeš vyhľadávať logaritmicky.
Tam môžeš namietnuť neefektivitu porovnávania stringov, tak teda ďalej.
Porovnávanie stringov sa dá vyriešiť všeliakými stromovými štruktúrami. Pár z použivaných pre takéto účely je napr. tzv. prefixový strom (trie), radix trie (tieto dva sú používané napríklad napr. v jadre unixu), B-stromy (veľmi používané napr. v súborových systémoch a databázach) a veľa ďalších.
Tam sa ale treba rozhodnúť, čo je dôležitejšie - či časová, alebo pamäťová zložitosť štruktúry. Pri tých tvojich chabých sto príkazoch by bola takáto štruktúra dosť overkill. Bola by síce asymptoticky rýchla, ale zbytočne veľká a zložitá a tie podmienky by nakoniec vyšli možno aj rýchlejšie (pri tých milisekundách je to naozaj ťažko poznať)

Ďalej máš možnosť prejsť to klasickým rekurzívnym zostupom. To by ale viedlo na ťažkú diskusiu, pretože som vymenoval veľmi silné dátové štruktúry, ktoré by sa na to určite nejako dali napasovať a boli asi aj rýchlejšie. Toto veľmi závisí na tom, ako veľmi zložité by si to chcel mať.

Zachádzam ale do totálneho extrému, pretože na takto jednoduchú vec, akú robíš, by som určite nič nevymýšľal a podmienkoval to.

Takže záver: Keď robíš jednoduchú vec, urob ju jednoducho. v tvojom prípade by som sa skôr zamýšľal nad optimalizáciou jednotlivých programov, než na ich spôsob výberu.

PS: To, čo sem hodil XOLOO je niečo úplne iné.

Chápem teda, nerobiť z jednoduchej veci zložitú . Takže ostanem u pôvodnej myšlienky. Ešte ma snáď napadlo, že by som niektoré príkazy s vyššou prioritou napísal do prvých casoch, aby sa vyhodnotili ako prvé, ale to už bude iba drobná vychytávka. Každopádne, vďaka za tvoj čas a za rozšírenie obzorov .

Preco nerozdelis tych svojich 200 prikazov na rozne podmnoziny ktore by si volal dalsim argumentom a takto zmensil dany vyber, teda ak spravne chapem tomu co sa snazis spravit. Takto si svojich 200 roznych prikazov rozdelis na 10 podmnozin a teda ak mas dany prikaz posledny tak nemusi zbehnut navyse cez tych 199 porovnavani nad nim, ale zbehne len poslednu mnozinu zlozenu z 20 porovnavani, ci blba myslienka?

Ak sa teda zamyslíme nad tými 200 príkazmi, čo dal autor ako príklad pre "veľa podmienok", tak by bolo optimálne (podľa mňa) skôr nejaké hashovanie. Trebalo by vymyslieť hashovaciu funkciu, ktorá urobí z reťazca číslo a ideálne ešte všetky výsledky znormalizované (tzn. výjdu všetky čísla od 0 do 199 a vždy jednoznačne) Tak by stačilo zavolať raz rýchlu hashovaciu funkciu a adresovať sa priamo do pola (konštatná zložitosť aj jedna aj druhá) A v poli by mohli byť ukazatele na funkcie, alebo niečo podobné.
Ak by sa nepodarilo vymyslieť hashovaciu funkciu, ktorá dá pekné čísla, tak by som to zase riešil binárnym vyhľadávaním. Tak zavolám raz funkciu a v logaritmickom čase nájdem v (zoradenom) poli odpovedajúci príkaz.
Ďalšia možnosť je hashovanie reťazením, čo vedie v podstate na podobné riešenie, ako od JanoF.

Pri hlbšom zamyslení by sa dalo nájsť veľa ďalších a určite aj lepších riešení.

Ešte ma napadlo, že by som mohol reagovať na túto vetu. To, čo som tu písal doteraz, je optimalizácia algoritmu ako takého (optimalizácia časovej/pamäťovej zložitosti)
Potom ešte existuje optimalizácia zameraná na hardware - tj. optimalizácia využitia skrytých pamätí(cache), optimalizácia kódu ako takého (transformácia cyklov, znižovanie počtu skokov atď), paralelizácia a tak ďalej.
Tieto optimalizácie sa ale robia pre náročné výpočty. Na takéto účely sú viac-menej zbytočné.
Ale napadlo ma, že ti ich spomeniem, keď si taký zvedavý
Pravdou je, že nech je C akokoľvek rýchly, akýkoľvek program, ktorý teraz napíšeš, často nevyužije CPU ani na 5%. Optimalizáciou kódu (práve takou, akú popisujem teraz) vieš efektivitu extrémne zvýšiť. Na ukážku si môžeš porovnať nejaký zložitejší výpočet napísať, skompilovať, spustiť a potom to isté skompilovať so zapnutými optimalizáciami (v GCC je to prepínač -O3 pre najvyšší stupeň)

viem, že je to OT, ale je vôbec technicky možné resp. môže existovať problém na ktorý existuje implementácia algoritmu, ktorá je v nejakom jazyku (C) súčasne najmenej pamäťovo aj časovo aj počtom krokov a ešte aj kód má najmenej riadkov? samozrejme pre každý vstup?
intuícia mi vraví, že asi taký problém (úloha) nemôže existovať, ale nie som informatik

jarrro, ak by si bol informatik, vedel by si, že na jazyku vôbec nezáleží. Ani trochu. Jazyk ti len umožňuje spúšťať kód na danom procesore a neupísať sa k smrti vyťukávaním núl a jedničiek. Celá implementácia je len o tom, ako program správne namapovať na činnosť procesora.


Čo sa algoritmov týka, v informatike existuje dosť rozsiahla teória zložitosti a tá rieši presne tieto veci. Táto teória často pracuje so zjednodušeným modelom počítača, tzv. turingovým strojom (aj z toho vidno, že na implementácií naozaj nezáleží)
Môžeš si o tom niečo prečítať napr. tu http://www.algoritmy.net/article/5774/Tridy-slozitosti
Je to už ale také celkom magické čítanie Na tvoju otázku sa preto ťažko hľadá odpoveď. Zjednodušene by sa dalo povedať, že áno - existujú optimálne algoritmy, ktoré riešia nejaký problém. Často ale aj teoreticky horší algoritmus môže riešiť daný problém lepšie, než ten optimálny - tj. všeliaké heuristiky, hľadanie probližných výsledkov, randomizované algoritmy atď. Ak do úvahy zoberieme aj paralelné výpočty, odpoveď sa ešte viac skomplikuje.

Btw. tvoja otázka z laického hľadiska vyznie divne. Existuje problém, na ktorý existuje optimálna implementácia? No áno, napríklad pričítanie jedničky k nejakému číslu. To dokážem urobiť na jedinú inštrukciu v snáď každom procesore. Podobne každá operácia, ktorá má vlastnú inštrukciu (typicky sčítanie, odčítanie, logické operácie a podobné veci, ktoré sa na úrovni fyzického hardware realizujú vždy rovnako)

aha hanbím sa aritmetika prirodzených čísel ma nenapadla

Uz sme velmi OT (neskor asi presuniem do Ostatnych), ale neda mi to - chapat jednu instrukciu ako atomicku operaciu, ktora stoji konstantny cas a pamat, je dost zavadzajuce. Je to samozrejme prakticke, ale inde ako na akademickej pode to moc nevyuzijes a realne nema zmysel pracovat s takymto vypocetnym modelom. 2+3 nestoji rovnako ako 2^300+3^200 -> treba premyslat nad logaritmickou cenou, nie jednotkovou.

On sa pýtal na "optimálnu implementáciu". O tom, že záleží prípad od prípadu som napísal viac než dosť -> v tvojom príklade je to tiež prípad od prípadu.
A ak si všimneš, naschvál som nedal ako prvý príklad sčítanie dvoch čísel, ale inkrementáciu o jedničku, ktorá naozaj vždy stojí rovnako Uviedol som to ako príklad a naozaj optimálnejšiu implementáciu než jednu inštrukciu (na procesore) nenájdeš. Len toľko som tým chcel povedať.

To, čo píšeš ty, je samozrejme pravda.