Počítání míry dokončení úkolů
Vyvíjím v jedné firmě CMS a to obsahuje mimojiné i modul na správu
úkolů. Každý úkol má svůj stav ze kterého lze zjistit, zda je či není
dokončený. Pak také má seznam úkolů, které jsou jeho částí (tj. jsou to
podúkoly).
Cílem je posčítat podúkoly a ukázat u všech úkolů, jak moc jsou hotové.
Tedy pokud má úkol 4 podúkoly a 3 z nich jsou hotové, bude míra
dokončení tohoto úkolu 75%.
Zajímavé tento problém činí to, že prohledávaný graf je obecný,
orientovaný (určitě to nemusí být strom a ani být acyklický,
uživatelé toho naklikají; je to chyba, se kterou si to musí
poradit a vydat rozumné výsledky :) a je uložený v SQL databázi.
Zajímavější to pak je s požadovanou přesností výpočtu. Psané to bude v
PHP+MySQL.
Časová složitost O(N+M) mi přijde taková akorát, ale výpočet může
být rozložen do více částí -- něco při zobrazení, něco při změně úkolu.
Databázi započítávat budu, přepokládám, že jí přenechám většinu výpočtů
a budu si v ní (asi) ukládat i nějaké mezivýsledky (k jednotlivým
uzlům). Přecejen je výrazně rychlejší než PHP a paměťová i časová
složitost O(N) v PHP je hodně.
Cílem je reálná rychlost při provozu a to i za cenu trochu ošklivějšího
algoritmu (ovšem ne příliš ošklivého).
Zpět