Organizace Apache Software Foundation (ASF) vydala verzi 22 integrovaného vývojového prostředí a vývojové platformy napsané v Javě NetBeans (Wikipedie). Přehled novinek na GitHubu. Instalovat lze také ze Snapcraftu a Flathubu.
Společnost AMD na veletrhu Computex 2024 představila (YouTube) mimo jiné nové série procesorů pro desktopy AMD Ryzen 9000 a notebooky AMD Ryzen AI 300.
OpenCV (Open Source Computer Vision, Wikipedie), tj. open source multiplatformní knihovna pro zpracování obrazu a počítačové vidění, byla vydána ve verzi 4.10.0 . Přehled novinek v ChangeLogu. Vypíchnout lze Wayland backend pro Linux.
Národní superpočítačové centrum IT4Innovations s partnery projektu EVEREST vydalo sadu open source vývojových nástrojů EVEREST SDK pro jednodušší nasazení aplikací na heterogenních vysoce výkonných cloudových infrastrukturách, zejména pro prostředí nabízející akceleraci pomocí FPGA.
Společnost Valve aktualizovala přehled o hardwarovém a softwarovém vybavení uživatelů služby Steam. Podíl uživatelů Linuxu aktuálně činí 2,32 %. Nejčastěji používané linuxové distribuce jsou Arch Linux, Ubuntu, Linux Mint a Manjaro Linux. Při výběru jenom Linuxu vede SteamOS Holo s 45,34 %. Procesor AMD používá 75,04 % hráčů na Linuxu.
Blíží se léto, chladiče topí, tranzistory se přehřívají, novinářům pomalu docházejí témata a nastává klasická okurková sezóna. Je tomu tak i mezi bastlíři? Na to se podíváme na Virtuální Bastlírně! Tentokrát se strahováci podívají na zoubek velmi slibně vypadajícímu open-source EDM projektu - ne, nejde o taneční hudbu, ale o elektroobrábění. Ukáží taky, jak vypadá starší cykloradar zevnitř nebo jak se testuje odolnost iPhonů.
… více »Společnosti Ticketmaster byla odcizena databáze s osobními údaji (jméno, adresa, telefonní číslo a část platebních údajů) 560 miliónů zákazníku. Za odcizením stojí skupina ShinyHunters a za nezveřejnění této databáze požaduje 500 tisíc dolarů [BBC].
Byla vydána nová stabilní verze 24.05 linuxové distribuce NixOS (Wikipedie). Její kódové označení je Uakari. Podrobný přehled novinek v poznámkách k vydání. O balíčky se v NixOS stará správce balíčků Nix.
Byla vydána nová verze 1.48.0 sady nástrojů pro správu síťových připojení NetworkManager. Novinkám se v příspěvku na blogu NetworkManageru věnuje Fernando F. Mancera. Mimo jiné se v nastavení místo mac-address-blacklist nově používá mac-address-denylist.
v souvislosti s mym predchozim zapiskem, jsem objevil moc peknou variantu red-black stromu. kdo nekdy zkousel implementovat RB stromy, AVL stromy a dalsi asi vi, ze je to pekny hnus.
jelikoz tento prispevek pisu v dobe, kdy jenom cekam, nez mi uschnou vlasy, abych si mohl jit nakoupit, nebudu se zabyvat analyzou. obzvlast, kdyz lepsi popis za me udelali jini -- paper, slidy. (v tech slidech jsem tusim narazil na nejakou drobnou chybku, ale i tak fakt pekne shrnuti cele problematiky)
presto, ze implementace LLRB je prosta, jak bulharska stripterka, prikladam ukazkovy priklad napsany v cecku pracujici s klici typu int a hodnotami typu char. je to kod na kterem jsem si zkousel, jestli to opravdu funguje tak jak ma. ma to operace insert (vlozeni dvojice), search (nalezeni podle klice) a print (vypis stromove struktury). snad to nekdy nekomu pomuze.
#include <stdlib.h> #include <stdio.h> #define RED (1) #define BLACK (0) typedef struct rb_node { int color; struct rb_node * left; struct rb_node * right; int key; char * value; } rb_node; static inline int is_red(rb_node * n) { if (n == NULL) return 0; return (n->color == RED); } static inline rb_node * rotate_left(rb_node * h) { rb_node * x = h->right; h->right = x->left; x->left = h; x->color = x->left->color; x->left->color = RED; return x; } static inline rb_node * rotate_right(rb_node * h) { rb_node * x = h->left; h->left = x->right; x->right = h; x->color = x->right->color; x->right->color = RED; return x; } static inline void color_flip(rb_node * h) { h->color = !h->color; h->left->color = !h->left->color; h->right->color = !h->right->color; } static inline rb_node * node_new(int key, char * value) { rb_node * res = malloc(sizeof(rb_node)); res->key = key; res->value = value; res->color = RED; return res; } static rb_node * node_insert(rb_node * h, int key, char * value) { if (h == NULL) return node_new(key, value); if (is_red(h->left) && is_red(h->right)) color_flip(h); if (h->key == key) h->value = value; else if (h->key > key) h->left = node_insert(h->left, key, value); else h->right = node_insert(h->right, key, value); if (is_red(h->right) && !is_red(h->left)) h = rotate_left(h); if (is_red(h->left) && is_red(h->left->left)) h = rotate_right(h); return h; } rb_node * rb_insert(rb_node * root, int key, char * value) { root = node_insert(root, key, value); root->color = BLACK; return root; } rb_node * rb_search(rb_node * h, int key) { if ((h == NULL) || (h->key == key)) return h; if (h->key > key) return rb_search(h->left, key); return rb_search(h->right, key); } void rb_print(rb_node * h, int level) { int i; if (h == NULL) return; for (i = 0; i < level; i++) printf(" "); printf("%i:%s\n", h->key, h->value); rb_print(h->left, level + 1); rb_print(h->right, level + 1); } int main() { rb_node * root = NULL; root = rb_insert(root, 1, "foo"); root = rb_insert(root, 5, "bar"); root = rb_insert(root, 10, "baz"); root = rb_insert(root, 3, "qux"); root = rb_insert(root, 7, "quux"); root = rb_insert(root, 8, "corge"); root = rb_insert(root, 2, "grault"); rb_print(root, 0); printf("::%s\n", rb_search(root, 3)->value); return 0; }
Tiskni Sdílej:
Ještě mazánílaskavy ctenar si to uz dodela sam.
dost mne překvapilo, jak jednoduchá ta implementace je...taky jsem na to cumel jak puk. ;-]
typedef struct rb_node { struct rb_node * left; struct rb_node * right; int color; int key; char * value; } rb_node;Je to jen drobná změna, která by měla zmenšit celkovou velikosti struktury, pokud je int 32bitový a ukazatel 64bitový o 8 bytů (pokud je pro vás teda paměťová efektivita důležitá).
Ono, psát kód který má být tuším čistě jen ukázkou datové struktury jako smetí v Céčku se dá taky hodnotit všelijak.
psát kód který má být tuším čistě jen ukázkou datové strukturyten kod jsem psal, abych si vyzkousel jestli to opravdu funguje... dal jsem to sem proto, ze kdosi ve vedlejsi diskuzi mel pripominku, ze by bylo dobre se o to podelit, protoze by se to nekomu mohlo hodit... nic vic, nic min. zadne vetsi ambice jsem s timto konkretnim kusem kodu opravdu nemel
jako smetí v Céčkuted nevim jak si to mam vylozit. tim smetim jste mel na mysli: a) ze to neni zoptimalizovane pro 64bitovou architekturu ... viz vyse nebo b) protoze to je v cecku ,,ktere neni prehledne'' ... schvalne si prepiste ten kod treba do javy, c# nebo jineho ,,moderniho jazyka'' ... uvidime jak moc se bude lisit... btw. i v nejakem meta jazyku by to asi nevypadalo o moc jinak
Tak uvádět jako „moderní jazyk“ další a další s C-like zápisem, žejo.
(Ale tak jako jo, nebylo by to jinde nějak zásadně lepší. Leč na věci se toho tolik nemění.)
Implementace je to hezká, ale mě se to stejně moc nepozdává. Oproti normálním nebalancovaným i balancovaným BST je to pořád dost komplikovaný kód, a výhoda že růst uzlů částečně požerou RED linky a bude se o trošku mín rebalancovat mi to nevaváží. To už můžu rovnou místo lepení uzlů těmi horizontálními RED linky vzít nějaký vhodný násobek cacheline, uzly BST do něj skládat jako do vektoru, a budu mít B-strom s relativně malou velikostí stránky. Tahle struktura bude fakticky speciálním případem RB stromu, takže bude mít všechny jejich výhody, a navíc mnohem menší overhead (ušetří se ty červené pointery, a r/b bit).
Bohužel nemám, jen mě to napadlo, když jsem si všiml že ty 2-3-4 stromy jsou fakticky jen B-stromy s fanoutem 4, kde jsou jednotlivé bloky implementovány dalším "červeným" stromem. Poníženě přiznávám že dotěď jsem o RB stromech nic nevěděl a myslel si že jde o něco úplně jiného. Ale hlavně bych zkusil přímé indexování. Ukousnout 12 bitů, indexovat 1k tabulku, ukousnout dalších 12 bitů, indexovat další 1k tabulku, a zbylých 8 bitů použít jako finální index. Začít s prázdnou kořenovou tabulkou, a L2 a L3 tabulky alokovat podle potřeby. Myslím že tohle je ověřeno jako nejvíce efektivní metoda. Problém je jen když poslední bity mají minimální lokalitu, tak to děsně nabobtná. Ale jestli jde o pointery, tak by to mělo fungovat slušně, ne?