wielokrotne wywoływanie quicksort - duże zużycie pamięci

To a propos mojego wcześniejszego tematu szybkie wczytywanie dużych plików.

Mam klasę generyczną Zbior, do której przesyłam obiekty składające się z danych pobranych z pliku. Klasa Zbior zawiera również funkcję quicksort, którą wywołuje z inna funkcja (klasyfikuj) z main'a. Teraz problem wygląda tak, nawet dla głupiej dwukrotnej walidacji krzyżowej (podzieleniu pliku z danymi na 2 części i sprawdzaniu dwukrotnie czy na podstawie jednej połówki dobrze poklasyfikuje drugą) zużycie pamięci dochodzi prawie do 200mb. Dla 5-krotnej przekracza 2GB :) Jak rozumiem przy każdym wywołaniu quicksorta dane są wrzucane na stos, ale potem nie są usuwanie z niego, nawet jak funkcja quicksort się wykona i przez to po wywołaniu funkcji po raz drugi dokładane są kolejne dane na stos? Czy da się zrobić tak żeby po tym jak funkcja quicksort skończy sortowanie, to żeby pamięć została zwalniana? Czy do tego muszę ją wywoływać poza klasą? Nie do końca rozumiem kwestie związane z zarządzaniem pamięcią.

Sprawdź wycieki jakimś valgrindem. Jak funkcja wróciła do miejsca w którym ją wywołałeś to stos także jest tak samo zajęty (wraca do dokładnie tego samego miejsca na stosie). Błąd masz na pewno gdzie indziej, quicksort nie powinien alokować niczego na stercie.

Sprawdź konstruktory kopiujące, destruktory itp. Ogólnie staraj się obiekty przekazywać przez referencję lub wskaźniki (najlepiej const jak nie zmieniasz obiektów).

Tak wygląda właściwy kod u mnie

 void quicksort(Wektor< Para<X,C> > &w, int x, int y)
	{
		Para<X,C> v,temp;
		int i = x;
		int j = y;
		v = w[(x+y)/2];
		do
		{
			while(w[i].element().interval(xx) < v.element().interval(xx))
				i++;
			while(v.element().interval(xx) < w[j].element().interval(xx))
				j--;
			if(i <= j)
			{
				temp = w[i];
				w[i] = w[j];
				w[j]= temp;
				i++;
				j--;
			}
		}
		while(i <= j);
		if(x < j)
			quicksort(w, x, j);			
		if(i < y)
			quicksort(w, i, y);
	}

funkcja interval liczy odległość od danego elementu z tablicy do obiektu xx

nawet jak przed wywołaniem funkcji quicksort utworzę obiekt klasy wektor z parametrem double i do kolejnych elementów przypiszę odległości:

 while(!zrobione())
		{
			doubleW[i] = biezacy().element().interval(xx);
			nastepny();
			i++;
		}

i potem wywołam zmodyfikowany quicksort:

 void quicksortDouble(Wektor<double> &w, int x, int y)
	{
		double v,temp;
		int i = x;
		int j = y;
		v = w[(x+y)/2];
		do
		{
			while(w[i] < v)
				i++;
			while(v < w[j])
				j--;
			if(i <= j)
			{
				temp = w[i];
				w[i] = w[j];
				w[j]= temp;
				i++;
				j--;
			}
		}
		while(i <= j);
		if(x < j)
			quicksortDouble(w, x, j);			
		if(i < y)
			quicksortDouble(w, i, y);			
	}

To i tak strasznie dużo pamięci zużywa.

Sam już nie wiem... starałem się Dr Memory coś zdziałaś, ale wywalał jakies błędy od siebie a nie od mojej aplikacji :/

Klasa Para

 template<class X, class C> class Para
{
public:
    X& element()
	{ return el;};
    C& kategoria(){return kat;};
    bool operator ==(Para &p){return (el==p.el && kat==p.kat);};
    bool operator<( Para &p ){return (el<p.el);};
	Para& operator=(Para &p)
	{
		this->el=p.element();
		this->kat=p.kategoria();
		return *this;
	}
	
	bool operator!=(Para &p)
	{
		return !(*this == p);
	}
    Para(){};
    Para(X &x,C &c){el=x;kat=c;};

private:
	X el;
    C kat;
};

Klasa Wektor

 template <class T> class Wektor
{ public:
    unsigned int& size(){return rozm;};
    Wektor(){};
    Wektor(const unsigned int &n)
	{
		try
		{
			rozm=n;
			A=new T[n];
		}
		catch(const bad_alloc& e)
		{
			cerr<<e.what()<<endl;
		}
	};
	~Wektor()
	{
		delete []A;
	}
    T& operator [ ](const unsigned int &i){if(0<=i && i<=rozm) return A[i];};

  private:
    unsigned int rozm;
    T* A;
};

Nadal nie widzę nic podejrzanego, poza wspomnianym interval(). Ale ponieważ się uczysz, kilka uwag co do kodu:

[1] Const correctness -- każda metoda nie zmieniająca stanu obiektu (jak np. operatory <, ==, != czy size()) powinny być zadeklarowane jako const:

bool operator==(const Para& p) const { return el == p.el && kat == p.kat; }
                ^^^^^          ^^^^^

Podobnie dla getterów powinny istnieć dwie wersje metody -- jedna nie-const zwracająca referencję do obiektu, i jedna const zwracająca stałą referencję lub kopię:

C& kategoria() { return kat; } // wersja nie-const, pozwala na zmiane obiektu kat
const C& kategoria() const { return kat; } // wersja const, moze byc wywolana na obiektach const

[2] Listy inicjalizacyjne -- dużo wygodniejsze, bardziej idiomatyczne oraz bezpieczniejsze do inicjalizacji pól klasy w konstruktorze:

Para(const X& x, const C& c) : el(x), kat(c) { }

[3] Tu jest błąd, kompilator zapewne rzuca ostrzeżenie:

T& operator[](const unsigned int &i)
{
    if (0<= i && i <= rozm)
        return A[i];
    // crash
}

Jeśli indeks będzie poza zakresem, metoda nic nie zwróci (bo nie może). W tym wypadku powinna rzucić wyjątek, w przeciwnym wypadku mamy undefined behaviour.

[4] Jak już wspomniał adf88 -- to jest odkrywanie koła na nowo. Ponadto brakuje kilku ważnych rzeczy w tej implementacji: domyślny konstruktor Wektora nie inicjalizuje pól, w szczególności -- nie ustawia rozmiaru na 0, wspomniany brak wyjątku w operatorze [], brak konstruktorów kopiujących. Iteratory też byłyby przydatne. Nie bez kozery implementacja std::vector z STL to ponad 2500 linii kodu.

Trochę wymiękam, myślałem, że interval dużo zużywa pamięci, bo jest funkcją wywoływaną z klasy, ale nie. Jak teraz jest funkcją, luźno lewitującą w kodzie, to nic to nie daje. Zamieszczam skrócony kod, bo część kodu, dla obecnie testowanego kodu, nawet nie wykonuje się:

double intervalKonkretnyTyp(const KonkretnyTyp &Ktyp1, const KonkretnyTyp &Ktyp2)
{
	double suma = 0;
	
		for(int i = 0; i < Ktyp1.size; i++)
		{
			if(Ktyp1.A[i].CzyJestLiczba())
			{
				suma += Interval::intervalLiczba(Ktyp1.A[i].GetLiczba(),Ktyp2.A[i].GetLiczba());				
			}
		}

		return sqrt(suma);
} 

I zamieszczam klasę Interval, z której jest wywoływana statyczna funkcja/metoda (nie wiem czy nazewnictwo z C# przenosi się do c++ w ramach funkcji wywoływanych z klas)

class Interval
{
public:
	static double intervalLiczba(const double &x1, const double &x2) {return pow(x1 - x2,2);}
}; 

czyli teraz sprawdzenie < w quicksort wygląda np. tak:

 while(intervalKonkretnyTyp(w[i].element(),xx) < intervalKonkretnyTyp(v.element(),xx))

Trochę wymiękam czemu zużycie pamięci rośnie tak szybko.

dziwne. Problem zniknął. Nie sam oczywiście, przejrzałem cały kod, gdzie zapomniałem, to dałem przesyłanie wartości do zmiennych przez const &, a właśnie. gdzieś przeczytałem, że nie opłaca się przesyłać typów prostych przez referencje, bo rezerwuje się 8 bitów na nią, a typ może mieć 4. To prawda? są sytuacje, kiedy jest to wysoce nieoptymalne?

dałem też przed paroma funkcjami jednolinijkowymi

inline

, chociaż nie wiem czy kompilator sam tego nie robi w ramach optymalizacji?

póki co jest nieźle, bo program mieli już ponad 30 min. dla pliku zawierającego 30 tys. linii danych i zajmuje "jedyne" 223mb, z tym, że wolno sortuje te wszystkie dane, bo w sumie przy każdym sortowaniu liczy odległość między obiektami. sortowanie quicksort. zobaczymy jak to dalej pójdzie. w sumie dalej będę próbował wyeliminować zużycie pamięci.
a i jeszcze jedna sprawa, czy jest różnica w szybkości między taką funkcją

 unsigned int &card(){return size;} 

a taką?

unsigned int &card()
{
return size;
} 

jakby z AMD codeanalyzator wynikało tak,ale mogę mylić się. chodzi oczywiście o zawarcie całego kodu w jednej linijce.

ups...

jest problem z klasą wektor, która może spowodować AV, chodzi o to, że w momencie dowolnego kopiowania tej klasy, zostanie skopiowany również wskaźnik, co spowoduje, że gdy np. tymczasowy obiekt zniknie, to zniknie razem z danymi na które ten wskaźnik wskazywał, co spowoduje, że oryginalny obiekt który tego wskaźnika będzie używał, będzie miał adres na już zwolnioną pamięć.

Rozwiązanie:
zdefiniować konstruktor kopiujący oraz operator przypisania. jeśli Ci się nie chce to możesz je zdefinować puste i wrzucić w sekcję private.

Poza tym nie opłaca się robić typów w prostych w ten sposób:
const int&
bardziej opłaca się je skopiować (const int). chyba, że chcesz, żeby w razie zmiany wartości w jakiejś metodzie wartość nadal była aktualna, ale strzelam że nie chcesz.

costamcos napisał(a)

póki co jest nieźle, bo program mieli już ponad 30 min. dla pliku zawierającego 30 tys. linii danych i zajmuje "jedyne" 223mb, z tym, że wolno sortuje te wszystkie dane, bo w sumie przy każdym sortowaniu liczy odległość między obiektami. sortowanie quicksort. zobaczymy jak to dalej pójdzie. w sumie dalej będę próbował wyeliminować zużycie pamięci.

223000 / 30 = 7500

aż tak długie linie tam masz?

Nie wiem co jest, ale licząc nawet 200 na linię wyjdzie z 40 razy za dużo.
Jakaś masakra a nie algorytm...

 unsigned int &card(){return size;} 

A tu po co ta referencja?
Referencja jest równoważna ze wskaźnikami, więc używasz gdy chcesz to zmieniać (zawartość), albo w przypadku struktur, żeby przyspieszyć.

Z tamtą funkcją możesz zrobić np. tak:
card() = 7;
i to będzie równoważne z: size = 7;

chociaż nie wiem czy kompilator sam tego nie robi w ramach optymalizacji?
zależy jaki kompilator, ale większość dzisiejszych słowo inline po prostu olewa, a inline'uje automatycznie jeśli włączysz optymalizację, niezależnie czy inline użyłeś czy nie.

@Autor wątku:
Tutaj inline nic nie pomoże.
Masz jakiś gruby problem z wydajnością, inline aż tak Ci nie pomoże.
Powinieneś liczyć element "v.element().interval(xx)" tylko raz (chociaż nie wynika to z kodu bo nie wiadomo co to "xx").

Podaj cały kod, albo to szukanie igły w stogu siana.

na razie nie jest źle. Zainstalowałem Ubuntu na maszynie wirtualnej a potem wspomnianego już valgrinda i miałem przecieki pamięci, teraz też mam, ale mniej i już tyle RAMu nie pożera, i patrzę dalej co jest nie tak.
Algorytm dalej długo wykonuje się dla 25000 obiektów, ale to chyba nic dziwnego. Przy 5-krotnej walidacji krzyżowej 25000 plików dzielone jest na 5 części i teraz każda część z osobna dopasowywana jest względem reszty, tzn. 20 tys. obiektów sortowanych jest względem 1 obiektu, potem drugiego, trzeciego... pięciotysięcznego i tak od początku dla kolejnych grupek po 5 tysięcy obiektów, czyli w sumie program musi wykonać sortowanie jednego obiektu względem 20 tysięcy obiektów aż 25 tysięcy razy!!!

teraz wracam do uporania się z dalszymi wyciekami.