| Autor | Zpráva | ||
|---|---|---|---|
| Petr Ká Profil |
#1 · Zasláno: 21. 7. 2014, 22:58:52 · Upravil/a: Petr Ká
Ahoj, už nějakou dobu přemýšlím nad takovou celkem zajímavou banalitou, která by se dala vyjádřit poměrně dobře na velkých strukturách, nicméně pokusím se popsat co nejjednodušeji příklad:
- Mám strukturu položek (založené na ID a PARENT_ID) - Každá položka může mít neomezeně podpoložek - potřebuji z tohoto vygenerovat strukturu tak, že každá položka může mít MAX 3 podpoložky a ty ostatní doplnit do dalšího podlevelu (pouze pokud tam bude "místo" => přednost mají přímé podpoložky - PARENT_ID) Pro příklad (neřešme, co na těch obrázkách je, ale jak jsou data strukturována): Mám toto (každá položka může mít neomezeně podpoložek): 
A potřebuji toto (každá položka může mít MAX 3 podpoložky, pokud má víc, doplní se do "children" větve zas do limitu 3, pokud jsou už v "children" větvi 3 přímé podpoložky, fronta jde do další úrovně níže): 
Volání by mělo být nejlépe rekurzivně Ještě dodám, že mi je jedno z jakého array by se to generovalo. Buď z "plochého" nebo zanořeného :) Díky! |
||
| Virtus Profil |
Zdravím,
Petr Ká: „Mám strukturu položek (založené na ID a PARENT_ID)“ podle prvního obrázku a této citované věty to vypadá, že aktuálně tedy máte Hierarchicko síťový model (logicky organizovanou bázi dat), a podle druhého obrázku z této struktury chcete udělat ,,něco" naprosto neorganizovaného, osobně mi to nedává moc smysl a rád bych se tedy zeptal na co konkrétně toto potřebujete? Ideální by bylo přiložit dva podobné obrázky s konkrétními daty, na které to chcete/potřebujete aplikovat. Ps: Pokud někdo jiný pochopil co potřebujete a napíše sem očekávanou odpověď považujte moje požadavky/přípomínky za bezpředmětné. |
||
| mimochodec Profil |
Petr Ká:
Já nebudu pátrat, k čemu by to bylo dobré. Chápu, jak má vypadat výstup. Ale nikde nepopisuješ, podle jakého klíče se mají položky načítat na vstupu. Připadá mi, že tě vazba rodič-potomek vůbec nezajímá a chceš ji opustit. Řešení vidím takové, že rekurzivně projdeš všechny vstupní položky, postupně je všechny nasypeš do jednorozměrného pole a to pak v cyklu přeložíš do nového pole ID, parent_ID, přičemž toho rodiče si pohlídáš nějakým pomocným polem s FIFO logikou. // edit: teď vidím "přednost mají přímé podpoložky", pardon. Pokud se toto má zohlednit, trochu se to komplikuje. Jak moc, teď hned nevím, je moc hodin. Napíšu zítra. |
||
| Petr Ká Profil |
#4 · Zasláno: 22. 7. 2014, 09:11:03 · Upravil/a: Petr Ká
mimochodec:
Úplně přesně jsi mě pochopil, je potřebs FIFO logika a přednost mají přímé položky, pokud jich je méně než 3 doplní se ze zásobníku... Virtus: Psal jsem neřešme co na tech obrázkách je, ale jak je strukturovaný :) |
||
| mimochodec Profil |
#5 · Zasláno: 22. 7. 2014, 13:08:17
Petr Ká:
„přednost mají přímé položky“ Pak se ale ty dva principy tlučou. Když v tom stromu na vstupu bude mít ten nejvyšší uzel pět potomků a každý z nich dalších pět, velmi rychle o tu vazbu potomek-rodič přijdeš a už od nějaké páté nebo šesté položky to odbavuješ prostě sériově. |
||
| Petr Ká Profil |
#6 · Zasláno: 22. 7. 2014, 13:11:22
mimochodec
Ano, to je přesně cíl, takhle to potřebuju, proste aby se "přesahovací" položky doplnovali pouze tam, kam se vejdou, ale právě tou logikou FIFO (prvně jde ta, která je tam nejdéle v "cache") |
||
|
Časová prodleva: 3 dny
|
|||
| Petr Ká Profil |
#7 · Zasláno: 25. 7. 2014, 22:23:13
Ani nic že?
|
||
| 1Pupik1989 Profil |
#8 · Zasláno: 26. 7. 2014, 08:30:45
Já pořád nějak nepochopil, co se stane se dvěma potomky, co z listu zbydou. Ty se vloží jako potomek toho prvního, čili o úroveň níž?
Nebo první se prostě prohlásí za root node a další 3 za ním jsou potomci? Další tři budou potomci toho prvního ze třech a tak dále? |
||
| juriad Profil |
#9 · Zasláno: 26. 7. 2014, 08:42:57
Zkoušel jsem to implementovat a také mi vůbec není jasné, co se má s přebývajícími položkami stát. Jediné, co je jasné, je, že mají být přesunuty někam do podstromu.
Ale, co když v podstromu již není místo? Viz přiklad jen s jednou hlavní položkou a pěti podřízenými. Má se to snažit o nějaké vyvažovaní? Nebo prostě přebývající položky předávat rekurzivně prvnímu potomkovi? Tedy levá větev bude šíleně hluboká. Nebuď tak líný a ukaž jak budou vypadat ty stromy na obrázku Navigation tree. Možná by pomohlo vysvětlit, k čemu je to dobré. Pokud chceš vytvořit strom, který obsahuje v každém vrcholu maximálně tři potomky a zároveň je vyvážený, použij 2-3-strom, který má přesně takové vlastnosti. |
||
| 1Pupik1989 Profil |
#10 · Zasláno: 26. 7. 2014, 13:00:51
Právě to přesně nechápu. Nebo to má být stylem postupného plnění? Jako zvolení root node a pak rovnoměrně naplňuji, dokud zásobník nebude prázdný? Takže kořen bude mít 3 sub potomky, pak se zase vyplní úroveň 2 a tak dále, dokud nebude hotovo?
Má ten strom definované nějaké pevné vazby? |
||
| Petr Ká Profil |
#11 · Zasláno: 26. 7. 2014, 13:03:42
Ano, má se to vyplnovat do nejakeho limit (max 3 children node, max 5 children node...). Prednost mají přímé. Tzn. Pokud nejaky root bude mít pouze 2 prime, tak se treti (pri limitu 3) doplni z "cache". Doplni se nejstarsi zaznam a smaze z "cache" (array_shift???).
|
||
|
Časová prodleva: 9 let
|
|||
0