Zpráva Justičního výboru Sněmovny reprezentantů upozorňuje na cenzurní kampaň Evropské komise, mířenou proti svobodě projevu na sociálních sítích. V dokumentu se uvádí, že se Evropská komise během posledních šesti let účastnila více než 100 uzavřených jednání, během nichž po platformách požadovala úpravy pravidel moderování obsahu, přičemž toto úsilí Komise zahrnovalo i cenzuru politických názorů a pravdivých informací. Výbor zdůrazňuje, že tento přístup Bruselu ohrožuje ústavou zaručená práva Američanů na svobodu projevu.
Linus Torvalds vydal jádro Linux 6.19. Podrobný výčet změn je ke zhlédnutí na stránce Kernel Newbies, stručné výběry v LWN (část první, druhá).
Do prodeje jde tichá bezdrátová herní myš Logitech PRO X2 SUPERSTRIKE s analogovými spínači s haptickou odezvou (HITS, Haptic Inductive Trigger System). Cena je 4 459 Kč.
Microsoft na GitHubu zveřejnil zdrojový kód projektu LiteBox, jedná se o 'knihovní operační systém' (library OS) zaměřený na bezpečnost, využívající systémovou architekturu LVBS k ochraně jádra před útoky z uživatelského prostoru. LiteBox je napsán v Rustu a uvolněný pod licencí MIT. Projekt je teprve v rané fázi vývoje.
BreezyBox je open-source shell a virtuální terminál pro populární jednočip ESP32. Nabízí základní unixové příkazy, sledování aktuálního pracovního adresáře (CWD), jednoduchý instalátor a spouštěč aplikací v podobě ELF binárních souborů, zabudovaný HTTP server nebo třeba ovládání WiFi - ukázka použití coby 'malého osobního počítače'. Ačkoliv je BreezyBox inspirovaný BusyBoxem, oproti němu má tento projekt několik externích závislostí, zejména na ESP-IDF SDK. BreezyBox je dostupný pod licencí MIT.
Byl představen cross-assembler xa.sh, napsaný čistě v Bourne shell skriptu. Tento nástroj umožňuje zpracovávat assemblerový kód pro Intel 8080, přičemž je možné snadno přidat podporu i pro další architektury, například 6502 a 6809. Skript využívá pouze různé běžné unixové příkazy jako jsou awk, sed nebo printf. Skript si lze stáhnout z GitHubového repozitáře projektu.
Byla představena nová verze modelu Claude Opus 4.6 od společnosti Anthropic. Jako demonstraci možností Anthropic využil 16 agentů Claude Opus 4.6 k vytvoření kompilátoru jazyka C, napsaného v programovacím jazyce Rust. Claude pracoval téměř autonomně, projekt trval zhruba dva týdny a náklady činily přibližně 20 000 dolarů. Výsledkem je fungující kompilátor o 100 000 řádcích kódu, jehož zdrojový kód je volně dostupný na GitHubu pod licencí Creative Commons.
Kultovní britský seriál The IT Crowd (Ajťáci) oslavil dvacáté výročí svého prvního vysílání. Sitcom o dvou sociálně nemotorných pracovnících a jejich nadřízené zaujal diváky svým humorem a ikonickými hláškami. Seriál, který debutoval v roce 2006, si i po dvou dekádách udržuje silnou fanouškovskou základnu a pravidelně se objevuje v seznamech nejlepších komedií své doby. Nedávné zatčení autora seriálu Grahama Linehana za hatecrime však vyvolává otázku, jestli by tento sitcom v současné Velké Británii vůbec vznikl.
Společnost JetBrains oznámila, že počínaje verzí 2026.1 budou IDE založená na IntelliJ ve výchozím nastavení používat Wayland.
Společnost SpaceX amerického miliardáře Elona Muska podala žádost o vypuštění jednoho milionu satelitů na oběžnou dráhu kolem Země, odkud by pomohly zajistit provoz umělé inteligence (AI) a zároveň šetřily pozemské zdroje. Zatím se ale neví, kdy by se tak mělo stát. V žádosti Federální komisi pro spoje (FCC) se píše, že orbitální datová centra jsou nejúspornějším a energeticky nejúčinnějším způsobem, jak uspokojit rostoucí poptávku po
… více »Pojmem strom se zpravidla označuje neorientovaný graf, jehož každé dva vrcholy jsou spojeny právě jednou cestou (pokud nerozumíte, zkuste se podívat třeba do wiki - graf, strom).
Strom může reprezentovat vybranou hierarchickou (stromovou) strukturu a ta je předmětem toho článku. Kde že jste mohli strom mimo park zahlédnout? Zajisté jste se s nimi setkali minimálně v diskusních fórech ABCLinuxu.cz, nebo při nakupování v internetovém obchodě, na jehož kategoriích výrobků si budeme práci se stromovou strukturou prezentovat. Důvodem je několik "zajímavých" akcí, jež se v internetovém obchodě provádějí. Uložištěm našeho stromu bude RDBMS komunikující jazykem SQL (konkrétně MySQL a v jednom případě i PostgreSQL).
V perexu jsem naznačil, že si ukážeme celkem tři příklady reprezentace stromu v SQL. Než si z nich vůbec začneme vybírat, měli bychom si ujasnit to, co od stromu budeme očekávat. Aplikace typu internetový obchod může provádět následující akce:
Operací s hierarchickou strukturou bude pravděpodobně více a mnohé mohou být efektivněji provedeny na aplikační úrovni (např. načtením celé struktury a jejím zpracováním namísto několika SQL dotazů). Ponechme je ale stranou a zkusme se podívat, co nám nabízí samotné SQL. Vzhůru do lesů!
Prvním způsobem uložení hierarchické struktury v SQL tabulce budou tzv. sebereferenční tabulky, definující strom seznamem následníků. Sebereferenční tabulky využívají vazby rodič-syn/dcera v hierarchické struktuře přítomné. Pro jednoduchost budeme předpokládat, že každý uzel má nanejvýš jednoho rodiče.
Uvažujme následující hierarchii kategorií:
SQL tabulka by mohla být vytvořena příkazem:
CREATE TABLE categories( id INT NOT NULL PRIMARY KEY, name VARCHAR(32), parent INT NOT NULL);
a její obsah by vypadal takto:
+----+---------------------+--------+ | id | name | parent | +----+---------------------+--------+ | 1 | Operační systémy | 0 | | 2 | Unix | 1 | | 3 | Linux | 1 | | 4 | Windows | 1 | | 5 | Red Hat | 3 | | 6 | Mandriva | 3 | +----+---------------------+--------+
Jak vidíte, každý uzel má unikátní identifikátor (číslo ID) a také jsme mu přiřadili rodiče. Všimněte si, že kategorie "Operační systémy" má ve sloupci parent nulu, i když žádná taková kategorie v tabulce není. Její syny budeme označovat jako kořenové kategorie a pro ni samotnou nebudeme požadovat rodiče.
Podívejme se teď na operace, které nás při práci se stromovou strukturou budou otravovat.
CRUD operace jsou vcelku triviální. Vkládání zajistí prostý INSERT. Při odebírání bychom měli dbát na to, abychom dle potřeby rekurzivně smazali i uzly-syny, což je v košatém stromě docela náročné. Přesun uzlu (a celého jeho podstromu!) v rámci stromu, tj. změnu jeho rodiče, realizujeme jednoduchým UPDATE.
Zobrazení podstromu provedeme podobně jako smazání - rekurzivně vybereme všechny potomky právě zpracovávaného uzlu. Podotkněme, že výhoda načtení celého stromu a jeho zpracováním aplikací sice ušetří práci databázi, ale nelze ji dost dobře použít při získávání všech výrobků patřících do kategorií podstromu, kterých může být velmi mnoho.
Rozbalení stromu dle vybrané kategorie je variací na téma zobrazení podstromu s tím, že do hloubky jdeme jen po cestě od kořene k rozbalovanému uzlu. Nalezení této cesty je při této reprezentaci znovu náročné.
Předností sebereferenčních tabulky je jejich jednoduchost - při práci s ní si bohatě vystačíte se znalostí rekurze. Cenou ovšem bude neúměrné zatížení databázového serveru zvláště v případě, že se stromem budete pracovat často, což se u internetového obchodu děje obvykle s každou zobrazenou stránkou, či když strom bude hezky košatý (uzly mají mnoho potomků) a vysoký (mnoho generací potomků). Odlehčit si můžete jistou úrovní cachování stránek, nicméně časem se nejspíš poohlédnete po výkonnějším řešení.
A narazíte možná na genealogické stromy. Genealogický strom také využívá vazbu rodič-syn mezi uzly, ale navíc pro každý uzel definuje i tzv. genealogický identifikátor. Tento identifikátor je unikátní pro každý uzel a dají se z něj vyčíst informace o jeho předcích (rodičích, prarodičích, prapra...) i potomcích. Identifikátor potomka totiž získáme tak, že za identifikátor předka připojíme identifikátor potomka.
Zvolíme-li za identifikátor písmeno abecedy, pak bude naše rozšířená tabulka obsahovat tyto záznamy:
+----+---------------------+--------+------+ | id | name | parent | path | +----+---------------------+--------+------+ | 1 | Operační systémy | 0 | A | | 2 | Unix | 1 | AA | | 3 | Linux | 1 | AB | | 4 | Windows | 1 | AC | | 5 | Red Hat | 3 | ABA | | 6 | Mandriva | 3 | ABB | +----+---------------------+--------+------+
CRUD operace tentokrát váže několik nepříjemných podmínek. Jednou z nich je omezení počtu potomků dle volby uložení identifikátoru (v případě písmen abecedy smít uzel mít "jen" 26 přímých potomků). Vložení nového uzlu do stromu provedeme tak, že zjistíme genealogický identifikátor rodiče a za identifikátor uzlu zvolíme nejmenší možné písmeno abecedy, které je na dané úrovni volné (úrovní rozumíme množinu přímých potomků rodiče). Zaveďme proto požadavek, aby na sebe identifikátory sourozenců lexikálně navazovaly.
Odstraňení uzlu je velmi snadné. Stačí smazat všechny uzly, jejichž genealogický identifikátor začíná identifikátorem odstraňovaného uzlu. Pokud bychom v naší hierarchii chtěli z nabídky odstranit podstrom s kořenovou kategorií "Linux", provedli bychom SQL příkaz:
DELETE FROM categories WHERE genealogical LIKE 'AB%';
Tím nám ovšem může vzniknout mezera na úrovni mazaného uzlu (Linux), což si nepřejeme a musíme proto po smazaní uzlu aktualizovat identifikátory postižených uzlů.
Přesun uzlu provedeme příslušnou změnou umístění (změna rodiče) a následnou aktualizací identifikátorů.
Poznamenejme, že návaznost identifikátorů se nakonec zdá být spíše na škodu, jelikož nám práci docela komplikuje, nicméně se bez procedury na odstranění hluchých míst ve stromu nejspíš neobejdeme.
Zobrazení kompletního podstromu je poněkud svízelné. Sice nám postačí
SELECT s klauzulí ORDER BY genealogical, aplikace ovšem často
požaduje,
aby byl výstup abecedně setříděn. Tuto komplikaci lze vyřešit už během CRUD
operací, totiž vkládáním nových uzlů na správné místo. Cenou je bohužel
režie spojená s tříděním a následnou aktualizací identifikátorů.
Chcete-li si ušetřit nepříjemnosti s nedostatkem písmen a přepočítáváním po mazání, můžete použít jiný identifikátor. V praxi se často používá např. speciální oddělovač následovaný číselnou sekvencí. Identifikátor uzlu Red Hat by byl "/1/3/5&qout;.
Konečně nalezení cesty k uzlu zařídí:
SELECT * FROM categories WHERE 'ABB' LIKE genealogical||'%' nebo SELECT * FROM categories WHERE 'ABB' LIKE concat(genealogical, '%')
Posledním a dle mého názoru nejvýkonnějším řešením je tzv. nested set reprezentace stromu. (Pozn.: Tento název používá Joe Celko a z různých článku se zdá, že není sám. Ačkoli podstatu uložení informace o uzlech charakterizuje čitelně i pro základních grafových algoritmů neznalé, lepší název by mohl být DFS strom.) Podívejme se nejprve na tabulku:
+----+---------------------+--------+------+-------+ | id | name | parent | left | right | +----+---------------------+--------+------+-------+ | 1 | Operační systémy | 0 | 1 | 12 | | 2 | Unix | 1 | 2 | 3 | | 3 | Linux | 1 | 4 | 9 | | 4 | Windows | 1 | 10 | 11 | | 5 | Red Hat | 3 | 5 | 6 | | 6 | Mandriva | 3 | 7 | 8 | +----+---------------------+--------+------+-------+
Vychází ze sebereferenční tabulky, kterou rozšiřuje atributy left a right. Jejich hodnoty jsou získány průchodem stromu DFS (depth first search) algoritmem. Pseudokód algoritmu:
AbcLinuxu.cz
ITBiz.cz
HDmag.cz
AbcPráce.cz
DFS(graf)
foreach uzly_grafu as uzel do
uzel->barva = bila
done
cas = 0
foreach uzly_grafu as uzel do
if uzel->barva = bila
DFS-PROJDI(uzel)
done
end
DFS-PROJDI(uzel)
uzel->barva = seda
cas = cas + 1
uzel->nalezen = cas
foreach sousede[uzel] as soused do
if soused->barva = bila
DFS-PROJDI(soused)
done
uzel->barva = cerna
uzel->opusten = cas
Algoritmus začíná voláním funkce DFS, které je předán zkoumaný graf. Ta nastaví barvu všech uzlů na bílou (uzel dosud nebyl navštíven), seřídí čas a následně prochází uzly grafu s tím, že pokud je uzel bílý, zavolá funkci DFS-PROJDI. DFS-PROJDI přebarví uzel na šedou (byl navštíven, ale dosud se zpracovává), zvedne čas o jedničku a použije jej jako čas navštívení uzlu a poté rekurzivně prochází dosud nenavštívené sousedy uzlu předaného jako parametr. Jakmile jsou všichni sousedé zpracování, přebarví uzel na černou (zpracování dokončeno), nastaví čas opuštění uzlu a vrací se.
Čas navštívení a opuštění uzlu se použijí jako hodnoty atributů left resp. right v SQL tabulce. Lepší představu o výsledku můžete získat z obrázku.
Všimněte si, že interval <left;right> libovolného uzlu je podintervalem intervalu vlastního rodiče (odtud nested set = vnořené množiny). Tato vlastnost plyne z toho, jak DFS prochází strom a ukladá časy a právě ona nám ulehčí práci s hierarchickou strukturou v SQL.
Podívejme se na operace, které chceme nad strukturou provádět. Všechny podkategorie zvolené kategorie získame jednoduchým SELECTem:
SELECT * FROM categories WHERE left >=x AND right <=y
Oproti rekurzi sebereferenčních tabulek podmíněnou mnoha dotazy či spíše přenosem většího množství dat jsme ve výhodě, ovšem genealogický identifikátor umožňuje totéž, ač s nutností použití pomalejšího operátoru LIKE. Získat výstup setříděný podle názvu uzlů je tentokrát o něco jednodušší. Po každé CRUD operaci totiž musíme aplikovat DFS algoritmus na celý strom znovu. Aby DFS generoval časy s ohledem na abecední pořadí uzlů, stačí naštěstí jen vhodně připravit pořadí uzlů, ve kterém jsou algoritmem zpracovávány (nezapomeňte abecedně setřídit i pole sousede[uzel]).
Cestu k uzlu nalezneme také velmi jednoduše. Stačí si uvědomit, že každý předek uzlu byl navštíven dříve a opuštěn později než uvažovaný uzel.
SELECT * FROM categories WHERE left <= x AND right >=y
DFS strom se zdá být velmi vhodný pro statické, či málo upravované struktury. Uplatnění si však zajisté najde i v případě potřeby vyhledávání ve velmi rozsáhlých hierarchických strukturách.
Nástroje: Tisk bez diskuse
Tiskni
Sdílej:
deb http://ftp.cz.debian.org/debian jessie main contrib non-free
11.1.2006 09:25
Věroš | skóre: 24
| blog: Co není v hlavě
| 49.29 s.š., 16.54. v.d.
A to jsem si na něj ráno taky vzpomněl.
.
11.1.2006 10:07
def Renumber (node, counter):
node.left = counter; counter++
for i in node.get_child_list ():
counter = Renumber (i, counter)
node.right = counter; counter++
return counter
Renumber (root, 1)
Na začiatok sa chcem poďakovať za článok. Zhodou okolností práve píšem bakalársku prácu na rovnakú tému, preto by som sa chcel spýtať, či by mi niekto nevedel poradiť vhodnú literatúru. Vyšlo niečo k stromovým dátam aj v češtine alebo slovenčine?, za odpoveď vopred ďakujem.....