abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
včera 17:55 | Komunita

Několik vývojářů aplikací pro GNOME napsalo otevřený dopis Please don’t theme our apps komunitě kolem GNOME se žádostí, aby jednotlivé linuxové distribuce neměnily vzhled jejich aplikací.

Ladislav Hagara | Komentářů: 11
včera 16:44 | Komunita

O víkendu proběhla v Norimberku openSUSE Conference 2019, tj. letošní konference vývojářů a uživatelů linuxové distribuce openSUSE. Na programu byla řada zajímavých přednášek a workshopů. Videozáznamy přednášek jsou k dispozici na media.ccc.de a na YouTube.

Ladislav Hagara | Komentářů: 0
včera 15:11 | IT novinky

Ubuntu doposud instalaci proprietárních ovladačů GPU pouze nabízelo na vyžádání, ovladače se musely stáhnout z Internetu. To se zřejmě pro GPU Nvidia změní s vydáním 19.10, jak je patrné ze záznamu v Launchpadu, tedy Ubuntu zahrne ovladače Nvidia 390 a 418 přímo do instalačního obrazu systému, jak to již činí správci derivátu Pop!_OS od firmy System76 dodávající počítače právě s tímto systémem. Velikost obrazu tak naroste o cca 115 MB. Open-source ovladač Nouveau zůstane výchozí.

Fluttershy, yay! | Komentářů: 0
25.5. 20:55 | Zajímavý projekt

Článek na LinuxGizmos.com představuje v NASA vyvinutého autonomního robota ve tvaru krychle pojmenovaného Astrobee neboli Hvězdná včela. Uvnitř včely běží Ubuntu/ROS a Android (GitHub). Na Mezinárodní vesmírné stanici bzučí tři tyto včely. Jejich jména jsou Honey, Queen a Bumble.

Ladislav Hagara | Komentářů: 0
24.5. 20:11 | Zajímavý projekt

Na Humble Bundle lze zdarma a bez DRM získat počítačovou hru Jalopy (YouTube). Hra je určena pro Windows, lze ji ale hrát také v Linuxu (ProtonDB, WineHQ). Speciální akce končí v sobotu v 19:00.

Ladislav Hagara | Komentářů: 0
24.5. 00:55 | Nová verze

ZFS on Linux, tj. implementace OpenZFS (Wikipedie) na Linuxu, byl vydán ve verzi 0.8.0. Přehled novinek v diskusním listu zfs-announce nebo na GitHubu. Nejnovější ZFS on Linux je kompatibilní s Linuxem 2.6.32 až 5.1.*.

Ladislav Hagara | Komentářů: 11
24.5. 00:33 | Nová verze

Byla vydána verze 1.35.0 programovacího jazyka Rust (Wikipedie). Podrobnosti v poznámkách k vydání. Vyzkoušet Rust lze například na stránce Rust by Example.

Ladislav Hagara | Komentářů: 0
23.5. 14:22 | Zajímavý projekt

GitHub v příspěvku na svém blogu představil GitHub Sponsors. Jedná se o další z možností, jak finančně podpořit vývojáře open source softwaru. Podrobnosti v často kladených dotazech (FAQ).

Ladislav Hagara | Komentářů: 9
23.5. 13:44 | Zajímavý software

Společnost Feral Interactive zabývající se vydáváním počítačových her pro operační systémy macOS a Linux vydala počítačovou hru Total War: Three Kingdoms (Wikipedie) pro Linux. Koupit ji lze za 59,99 €. Tentokrát byla verze pro Linux vydána ve stejný den jako verze pro Microsoft Windows.

Ladislav Hagara | Komentářů: 0
23.5. 10:00 | Nová verze

Po téměř 11 měsících vývoje od vydání verze 5.28 byla vydána nová stabilní verze 5.30 programovacího jazyka Perl. Do vývoje se zapojilo 58 vývojářů. Změněno bylo přibližně 620 tisíc řádků v 1 300 souborech. Přehled novinek a změn v podrobném seznamu.

Ladislav Hagara | Komentářů: 2
GPU kterého výrobce aktuálně preferujete pro provoz Linuxu?
 (49%)
 (26%)
 (23%)
 (2%)
Celkem 376 hlasů
 Komentářů: 29, poslední 24.5. 14:49
Rozcestník

Left-Leaning Red-Black tree

23.2.2009 20:25 | Přečteno: 1540× | Distribuce | Výběrový blog

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;
}

       

Hodnocení: 86 %

        špatnédobré        

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

Komentáře

Vložit další komentář

23.2.2009 20:51 Ladicek | skóre: 28 | blog: variace | Havlíčkův brod
Rozbalit Rozbalit vše Re: Left-Leaning Red-Black tree
Ještě mazání :-)

Ne, když jsem dneska viděl prvně ten paper (iniciativně jsem si ho vyhledal po zmínce v té předchozí diskusi), dost mne překvapilo, jak jednoduchá ta implementace je. I like this!
Ještě na tom nejsem tak špatně, abych četl Viewegha.
23.2.2009 21:15 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
Rozbalit Rozbalit vše Re: Left-Leaning Red-Black tree
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. ;-]
Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
AltOS avatar 24.2.2009 00:20 AltOS | Jizak
Rozbalit Rozbalit vše Re: Left-Leaning Red-Black tree
Absolutne k veci (TM):

...je prosta, jak bulharska stripterka...

Plati to jeste dnes?
24.2.2009 01:43 Deleted [8409] | skóre: 14 | blog: darkblog
Rozbalit Rozbalit vše Re: Left-Leaning Red-Black tree
Nebylo by lepší reorganizovat ten uzel takto?
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á).
24.2.2009 02:04 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
Rozbalit Rozbalit vše Re: Left-Leaning Red-Black tree
v tomto pripade to pomuze... v realnem kodu to mam stejne delane uplne jinak...

jinak resit takove veci v ukazkovem prikladu pro deset polozek imho patri do kategorie ,,premature optimization'' a mozna i ,,immature'' ;-]
Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
thingie avatar 24.2.2009 02:16 thingie | skóre: 8
Rozbalit Rozbalit vše Re: Left-Leaning Red-Black tree

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.

Růžové lži.
24.2.2009 03:05 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
Rozbalit Rozbalit vše Re: Left-Leaning Red-Black tree
psát kód který má být tuším čistě jen ukázkou datové struktury
ten 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éčku
ted 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

Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
thingie avatar 24.2.2009 11:53 thingie | skóre: 8
Rozbalit Rozbalit vše Re: Left-Leaning Red-Black tree

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í.)

Růžové lži.
2.3.2009 13:39 zde | skóre: 9 | blog: Linuch | Brno
Rozbalit Rozbalit vše Re: Left-Leaning Red-Black tree

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).

Táto, ty de byl? V práci, já debil.
2.3.2009 16:37 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
Rozbalit Rozbalit vše Re: Left-Leaning Red-Black tree
mas to nekde naimplementovane? rad bych to srovnal v realu...
Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
2.3.2009 18:02 zde | skóre: 9 | blog: Linuch | Brno
Rozbalit Rozbalit vše Re: Left-Leaning Red-Black tree

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?

Táto, ty de byl? V práci, já debil.

Založit nové vláknoNahoru

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.