Knihovna pro stromy v C

[Jan Kasprzak]

Dalibor Straka wrote:
: > 	Uz nemam, ale neco jako
: > 
: > 	for (i=0; i < (1<<24); i++) {
: > 		if (skore[i] > neco ...) {
: > 			printf("%d,%d...\n", i, skore[i],...);
: > 		}
: > 	}
: > 
: > 	Dal jsem to pro jistotu do samostatne funkce, a ta i presto
: > ze v testovacim behu mela je nekolik malo desitek volani, tak sumarni cas
: > mela daleko nejvetsi z celeho programu.

: Aha, ja myslel, ze pomale je ukladani do pole.

	To samozrejme ne.

: Tady evidentne zdrzuje
: hlavne printf() :-).

	Nikoliv, to by se ukazalo v profileru (pri linkovani s profilovaci
libc). Navic printf() tam bude tak jako tak. Pomale je skutecne sekvencni
prochazeni 1<<24 radku.

: Porad tvrdohlave tvrdim, ze
: 
: 	buf = calloc(2^24 * sizeof (int));
: 	zdroj = nejaky_blok_integeru //cist read() po jednom je moc volani 
: 	while (zdroj_size--)
: 		(int *) (buf + *zdroj++)++;

	Toto je ovsem zapis do pole (shromazdovani dat), ne vypis vysledku.
Zapis mam samozrejme takhle nejak a je to rychle. Je ale otazka, jestli
jinou vhodnou strukturou nejde zapis+vypis nejak zrychlit (nejspis tedy
za cenu castecneho zpomaleni zapisu vyrazne zrychlit vypis).

	Jeste k jinym ideam z tohoto vlakna:
zkusil jsem to prepsat na jednosmerne linkovany seznam
a je to cca 5x pomalejsi. Problem je nejspis v tom, ze velikost usporadanych
podposloupnosti na vstupu je porad radove stejna, zatimco velikost dosud
objevenych ruznych klicu na vstupu roste, takze prochazeni seznamu je cim dal
mene uspesne.

-Y.

-- 
| Jan "Yenya" Kasprzak  <kas at {fi.muni.cz - work | yenya.net - private}> |
| GPG: ID 1024/D3498839      Fingerprint 0D99A7FB206605D7 8B35FCDE05B18A5E |
| http://www.fi.muni.cz/~kas/    Journal: http://www.fi.muni.cz/~kas/blog/ |
**         Those who fail to understand communication protocols,          **
**         are doomed to repeat them over port 80.    -- from /.          **