Borneq <b...@a...hidden.pl> napisał(a):

> W dniu 2012-01-30 02:25, M.M. pisze:
> > Ostatnio wzialem pod lupe pewien programik do generowania lasow drzew
> > regresyjnych. Program jest napisany bardzo intuicyjnie, np. kazdy
> > rekord z pliku jest alokowany przez new i sa listy rekordow (a nie tablice
> > liniowe). Program uzywa (chyba) dobrego algorytmu ale ma kiepska
> > implementacje. Nie ma zoptymalizowanej pamieci cache i nie jest
> > zrownoleglony ani nie ma jednej globalnej struktury danych przyjaznej
> > dla wszystkich procedur, tylko robi konwersje.
>
> Czy alokowanie przez new rzeczywiście tak nieefektywne? W C# i Javie
> chyba nie można się bez tego obyć, tylko że tam new jest szybsze.
> Listy rekordów chyba są dość szybkie

Problem polega na czym innym. Sama alokacja przy pomocy new nie musi
byc problemem, wszystko zalezy od tego jak czesto alokujemy w stosunku
do innych operacji.

Chodzi o to, ze mam liste rekordow, zwykla struktura:
struct NodeList {
void *dane;
NodeList *next;
};
Wczytuje dane z pliku i za kazdym razem mam dwa wywolania new, jedno
dla utworzenia wezla, a drugie dla utworzenia danych. Potem lista
jest przegladana. Wyglada na to ze new podaje w miare mozliwosci
sekwencyjne adresy i pierwszy przeglad trwa krotko. Potem jedna lista
jest rozbijana na dwie listy. Do kazdej trafiaja przypadkowe elementy.
Takich podzialow robie wiecej, w koncu wszystkie listy sa skladane z
powrotem w jedna i z powrotem sa dzielone. Po okolo dwoch-trzech takich
przebiegach algorytmu uzyskuje praktycznie losowy dostep do pamieci i
to jest glownym problemem. Po upakowaniu tego w sekwencyjne adresy i
zrownoleglenie (na listach ciezko zrownoleglac) przyspieszenie jest
ogromne, przewiduje ze okolo 200 razy.


Pozdrawiam.


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/