Knihovna pro stromy v C

Dalibor Straka dast na panelnet.cz
Úterý Září 11 18:51:25 CEST 2007


Ahoj,

On Tue, Sep 11, 2007 at 05:59:33PM +0200, Jan Kasprzak wrote:
> : 
> : On Tue, Sep 11, 2007 at 01:58:43PM +0200, Jan Kasprzak wrote:
> : > No a ted je otazka, jak toto v C naprogramovat. Pro 24 bitu v zasade
> : > staci mit pole delky 2^24, na zacatku naplnit nulami, pak pricitat
> : > jednicky podle vstupu a na konci jednim pruchodem vypsat ty nenulove.
> : > Bohuzel i tohle mi v profileru vylezlo nahoru jako nejvic narocne,
> : >
> : Mohl bys mi poslat kod? Todle se mi zda jako neuveritelne.
> 	
> 	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. Tady evidentne zdrzuje
hlavne printf() :-). 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++)++;

Velikost zdroje muzes zoptimalizovat tak, aby se jeste vse veslo do 
cache. I kdyz pri cteni dat z okolicka si cache sama pricucne ;-).

-- Dalibor Straka



Další informace o konferenci Linux