Strukturovaná diskuse pod články – teorie

Mnoho začínajících weblogů či webzinů se trápí s problémem, jak udělat strom diskusí pod články co nejefektivněji. Pokusím se problém vysvětlit v následujících článcích, přičemž v tomto si provedeme nejprve malou teoretickou analýzu.

Představme si následující problém – máme stránku s diskusí a chtěli bychom veškeré příspěvky přehledně zobrazit. Pro několik málo příspěvků je stačí naskládat za sebe tak, jak přišly, ovšem pro větší počet začíná být tento způsob nepřehledný a nikdo neví, kdo na co vlastně odpovídá. Někdy je výhodnější z příspěvků vytvořit jakýsi „strom“.

Stromové zobrazení diskuse sebou ale přináší spoustu problémů. Obvykle totiž známe u každého příspěvku pouze jeho číslo (index) a číslo toho, který mu předcházel. Přitom pro výstup bychom potřebovali dvě pole – v jednom budou uloženy čísla příspěvků tak, jak za sebou půjdou ve stromu, a ve druhém bude informace, o kolik je každý příspěvek ve stromu odsazen. Z těchto údajů se následně provede vykreslení stromu.

Pro jistotu si zopakujme, z čeho vycházíme – máme jedno pole, ve kterém jsou uložena čísla předcházejících příspěvků (dále předchůdců). To znamená, že je-li na čtvrtém místě uložena trojka, je předchůdce čtvrtého příspěvku příspěvek číslo tři. Dále si dovolím předpokládat znalost celkového počtu příspěvků (count($pole)). Než se pokusíme uvařit z těchto ingrediencí vhodný algoritmus, rozeberme si tento problém poněkud zevrubněji. Pokud vás nezajímá, jak tento algoritmus funguje, pak následující řádky v klidu přeskočte.

Co platí ve výsledném poli? Vezměme si dva příspěvky A a B, které reagují těsně po sobě na stejný příspěvek číslo C (dále následníci C). Pokud by A neměl žádné následníky, ležely by tyto dva prvky ve výsledném poli vedle sebe. Snadno si totiž uvědomíme, že pokud by tomu tak nebylo, museli bychom mezi ně vtěsnat nějaké příspěvky. Ty by tam ovšem byly jen kdyby byly následníky A a to je spor. Jiný případ ovšem nastane, když A nějaké následníky má. Pak totiž C budu moci do výsledného pole vložit až když vypíšu všechny následníky A a zároveň jejich následníky a tak dále…

Tím jsme si ale definovali problém, který vlastně chceme řešit. Řekněme, že máme nějaký příspěvek P. Chceme vypsat čísla všech příspěvků, kterým tento článek nějak předcházel. Mějme například takovýto strom příspěvků:

1
 – 3
 – 5
    – 8
       – 10
    – 9
 – 7
2
 – 4
 – 6

Potom pro 5 chceme vypsat 8, 10, 9, pro 1 vypíšeme 3, 5, 8, 10, 9, 7 a další. Asi jste si všimli, že čísla příspěvků vypisuji v tom pořadí, v jakém bychom je chtěli nakonec získat. To ale z postupu, který jsem uvedl výše, přímo neplyne. Ovšem využijeme-li rekurze, získáme přibližně tento postup:

1. vezmi prvního následníka aktuálního prvku
2. vypiš všechny následníky toho prvního
3. udělej totéž pro dalšího následníka

Tento rekurentní postup už vrátí posloupnost setříděnou přesně tak, jak jsme chtěli. Bohužel nemáme dostatek informací k tomu, abychom tento algoritmus mohli implementovat přímo. K tomu potřebujeme znát následníky každého příspěvku.

Pokud předpokládáte počty příspěvků v řádech desítek, je nejlepší vytvořit matici (dvourozměrné pole), kde na i-tém řádku budou všichni následníci i-tého článku. Jen pro jistotu náznak implementace – vytvoříme dvourozměrné pole a navíc pomocné pole, které si bude pro každý příspěvek pamatovat, kolik jeho následníků už jsme zpracovali. Potom budeme procházet vstupní pole. Vezmeme hodnotu i-tého, o níž víme, že představuje číslo předchůdce, takže schéma zápisu v PHP bude vypadat asi takto:

$matice[$zdroj[$i]][$pom[$zdroj[$i]++]]=$i

Proměnná $pom je pomocné pole s počty následníků (abychom věděli, na jaké místo v matici ukládat) a zdroj vstupní pole. Nebudu se k tomuto postupu rozepisovat více, protože další bude fungovat i pro tisíce příspěvků a není o moc složitější než tento.

Všimněte si, že v poli matice, která má kvadraticky mnoho míst (tedy pokud máme 100 příspěvků, má toto pole 10 000 členů, pro 1 000 příspěvků už to bude 1 000 000 členů) jich použijeme jen lineárně mnoho (tedy pro 100 prvků využijeme jen 100, pro 1 000 jich použijeme 1 000). (Příliš jsem nezdůvodnil, proč jich skutečně tolik použiji, takže – v každém kroku zaplním jedno místo, těch kroků při zaplňování matice udělám N, kde N je počet prvků na vstupu – jinými slovy lineární závislost…)

Ten nepoměr je zjevný. Řešením může být například pole následníků. Pole následníků je relativně často užívaná datová struktura, která řeší problém s nevyužitým místem. Jak už název napovídá, jde o zvláštní pole. Poněkud nekorektní, ale velmi názorný obrázek si uděláte, pokud si představíte, že do pole budete postupně zapisovat jednotlivé řádky matice, tak jak jsme si ji výše popsali, ovšem vynecháte „volná“ místa. V poli tak budou jakési „úseky následníků“, přičemž každý úsek bude mít společného předchůdce.

Protože je tento slovní popis možná trochu chaotický, připojím matici, vycházející z úvodního stromu:

 1  2 -1 -1 -1 -1 -1 -1 -1 -1 //řádek pro „nultý“ příspěvek
 3  5  7 -1 -1 -1 -1 -1 -1 -1
 4  6 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
 8  9 -1 -1 -1 -1 -1 -1 -1 -1
 …

Hodnota -1 značí prázdné místo – nulu jsem nemohl použít, protože ta značí nultý kořen, který je předchůdcem těch prvků které předchůdce nemají (v našem příkladu příspěvky 1 a 2). Z matice po řádcích přečteme pole následníků. Tedy 1 2 3 5 7 4 6 8 9...

Rád bych upozornil na úsporu prostoru. V takovém poli bychom ale nebyli schopni dohledat, čí následník daný prvek vlastně je. Potřebujeme tedy pomocná pole. V jednom budeme mít uloženo, kolik má který prvek následníků, a ve druhém si zapamatujeme, kde začínají jednotlivé úseky. (Hlouběji si tvorbu těchto polí popíšeme až při praktické implementaci.)

Pokud máme vytvořeno pole následníků spolu s pomocnými poli, naprogramujeme si rekurentní funkci, která bude dělat to, co jsme naznačili výše, tedy bude po jednom brát následníky aktuálního článku, každého si zapamatuje a spustí pro něj tuto rekurentní funkci. Jakmile se z ní vynoří, udělá totéž pro druhý příspěvek a tak bude pokračovat dále. Prosté, jednoduché a navíc nefunkční!

Ti z vás, kteří četli pečlivěji, si určitě povšimli, že jsem jaksi přehlédl jeden důležitý fakt – bylo by žádoucí, aby příspěvek, který byl vložen do diskuse dříve, byl nad příspěvkem, který byl vložen později. To nám ale výše uvedený postup nezaručí. Kdyby měl třeba příspěvek 4 následníky 6 a 7, pak tento algoritmus může vypsat 4 6 7 stejně dobře jako 4 7 6.

Mohlo by vás napadnout nejprve si pro každý prvek jeho následníky setřídit, nebo vždy nalézt ještě neuložený s nejmenším číslem. (Zde by bylo vhodné, aby číslo příspěvku korespondovalo s pořadím zaslání, jinými slovy musí platit, že je-li index(A)<index(B), potom A byl přidán před B – to nebude problém zaručit…)

Jednoduchost tohoto řešení je vyvážena jeho neefektivitou a tak provedeme lehký úkrok – pokusíme se šikovně vystavět pole následníků. Šikovně znamená, že indexy následníků v jednotlivých úsecích pole následníků budou setříděné, tedy pokud budeme v naší rekurentní funkci postupovat popořadě, budeme mít zaručeno, že aktuální následník má nejmenší index ze všech dosud nezpracovaných následníků daného prvku. I když jeto ze slovního popisu těžko vidět, je vytvoření takového pole velice jednoduché (vzhledem k povaze vstupních dat).

Tím ale nekončíme. Víme sice, v jakém pořadí budeme jednotlivé příspěvky vypisovat, ale zatím vůbec nemáme ponětí o odsazení, abychom získali opravdu přehledný strom. Možné je řešení za pomoci jediného pole a for cyklu. Využívá jedné velmi jednoduché myšlenky: Pokud byl můj předchůdce odsazen o P mezer, budu já (jeho následník) odsazen o P+1 mezer. Stejně tak ostatní následníci tohoto předchůdce budou odsazeni o P+1.

Stačí tedy nultý komentář (chápejme ho třeba jako příspěvek, na který se reaguje) odsadit o „nula“, tedy uložit si do pole na nultý index nulu. Pak jen postupujeme po jednotlivých políčcích. Řekněme, že jsme na k-tém políčku. Potom tomuto k-tému políčku přiřadíme hodnotu předchůdce k-tého prvku + 1.

Možná ale není úplně jasné, že už tento předchůdce bude spočítaný. Jestliže je ale A předchůdce B, potom index(A)<index(B) (viz výše). To krom jiného znamená, že jsem-li u k-tého prvku, musel jsem už spočítat všechny prvky 0 až k-1. A protože předchůdce aktuálního prvku musel mít index menší než k, musí se někde mezi nimi nacházet a musí tedy být spočítán…

Implementace výše uvedeného je triviální a pokud mezi vámi panují nějaké nejasnosti, budou jistě rozehnány po přečtení kódu – jak jsem říkal, celý tento postup budeme schopni přepsat dvěma řádky zdrojových kódů!

A ještě poznámka na závěr. Možná by vás zajímala časová náročnost našeho řešení. Výklad principů analýzy časové, potažmo paměťové náročnosti algoritmů hrubě překračuje účel tohoto článku. (Pokud máte s podobnými analýzami zkušenost, pak vězte, že jde o k*N+N+N ~ O(N).) K běžnému použití stačí vědět, že pro řádově desítky tisíc příspěvků nepoběží déle než několik sekund, spíše však méně než sekundu. Vzhledem k tomu, že počty příspěvků málokdy „přelezou“ stovku, rozhodně nemusíte mít strach, že by se na tento výpočet čekalo.

Starší komentáře ke článku

Pokud máte zájem o starší komentáře k tomuto článku, naleznete je zde.