int division Memleak?

[Wodar Hospur]

Folgendes, bei meiner Realisierung des Backtracking Algos fürs Springerproblem ist mir eine interessante Besonderheit aufgefallen.

#include <vector>


// needed for output

#include <iostream>

#include <sstream>

#include <string>


// CONSTS for field

#define MAX_X 5

#define MAX_Y 5


// Startposition

#define START_X 0

#define START_Y 0


// saving the winner

std::vector<std::vector<unsigned int> > result;


// jumpingpattern

int xarray[] = {1,2,1,2,-1,-2,-1,-2};

int yarray[] = {2,1,-2,-1,2,1,-2,-1};



bool visited(std::vector<unsigned int> &vec, unsigned x, unsigned y) {

	int vec_x = 0;

	int vec_y = 0;

	for(std::vector<unsigned int>::iterator it = vec.begin(); it != vec.end(); it++) {

		vec_y = (*it % 10);

		vec_x = (*it - vec_y)/10;

		if(vec_x == x && vec_y == y) {

			return true;

		}

	}

	return false;

}


void goNext(std::vector<unsigned int> &vec) {

	// reached end

	if(vec.size() == (MAX_X * MAX_Y)) {

		// closed vs. open jump

		result.push_back(vec);

		return;

	}


	unsigned int start = vec.back();


	int y = (start % 10);

	int new_y = 0;


	int x = (start - y)/10;

	int new_x = 0;


	for(int i=0; i<8; i++) {

		new_x = x + xarray[i];

		new_y = y + yarray[i];


		if(new_x >= 0 && new_x < MAX_X && new_y >= 0 && new_y < MAX_Y) {	

			if(!visited(vec, new_x, new_y)) {

				std::vector<unsigned int> new_vec = std::vector<unsigned int>(vec.begin(), vec.end());

				new_vec.push_back(new_x*10 + new_y);

				goNext(new_vec);

			}

		}

	}

}


unsigned int findPos(std::vector<unsigned int> &vec, unsigned int val) {

	int pos = 0;

	for(std::vector<unsigned int>::iterator it = vec.begin(); it != vec.end(); it++,pos++) {

		if(*it == val) {

			return pos;

		}

	}

	pos++;

	return pos;

}


void print(std::vector<unsigned int> &vec) {

	std::stringstream* str = new std::stringstream;

	for(int i=0; i < MAX_X; i++) {

		*str << "   ";

		*str << i;

	}

	std::cout << str->str() << std::endl;

	delete str;


	int pos;

	for(int i=0; i < MAX_Y; i++) {

		str = new std::stringstream;

		*str << i;

		for(int j=0; j < MAX_Y; j++) {

			*str << "  ";

			pos = findPos(vec,j*10+i);

			*str << pos;

			if(pos < 9) {

				*str << " ";

			}


		}

		std::cout << str->str() << std::endl;

		delete str;


	}	

}


int main (int argc, char * const argv[]) {	

	std::vector<unsigned int> start;

	start.push_back(START_X*10 + START_Y);

	goNext(start);

	std::cout << "gesamte Ergebnisse: " << result.size() << std::endl;


	print(result.back());

	return 0;

}

kompiliert dabei super und liefert auch das richtige Ergebnis. Jetzt wollte ich das Ding etwas tunen, dafür war jetzt eine Überlegung z.b. den Modulo Operator durch eine einfache int divison zu ersetzen:

....

vec_y = (*it % 10);

....

int y = (start % 10);

....

zu

....

vec_y = (*it / 10);

....

int y = (start / 10);

....

ändern. Das führt aber auf Mac OS X 10.6 mit aktuellem x code von einem Speicherbedarf von 400 KB zu einem Speicherbedarf > 1 GB. Selbst wenn da irgendwelche impliziten Typumwandlungen laufen sollten, der Speicher sollte ja auch wieder freigegeben werden?

Btw. kurze Frage gibst ne elegantere Lösung in einem std::vector zu prüfen ob ein bestimmtes Element enthalten ist als stur Durchzulaufen?

[Klotzkopp]

Jetzt wollte ich das Ding etwas tunen, dafür war jetzt eine Überlegung z.b. den Modulo Operator durch eine einfache int divison zu ersetzen:

Ist dir klar, dass dabei etwas ganz anderes herauskommt? Damit machst du deine Koordinatenberechnung kaputt. Du hängst immer wieder 42 an den Vector an, bis der Speicher volläuft.

Ich nehme an, der Ansatz, zwei Werte in einen unsigned int zu packen, war ein Versuch, den Speicherbedarf zu verringern, aber dabei ist einiges schiefgelaufen.

Wie groß kann denn dein Vector werden? Maximal MAX_X * MAX_Y Einträge. Ich weiß nicht, wie groß die Schachbretter werden sollten, aber das ist ziemlich überschaubar.

Und wenn du so etwas machst, solltest du nicht den Faktor 10 benutzen, um die Werte zu trennen. Damit kannst du die Werte zwar schön ansehen, aber der Computer könnte mit einer Zweierpotenz viel schneller rechnen.

Btw. kurze Frage gibst ne elegantere Lösung in einem std::vector zu prüfen ob ein bestimmtes Element enthalten ist als stur Durchzulaufen?

Nein. Aber die ganze Zerlegerei in zwei Einzelwerte könntest du dir komplett sparen, indem du gleich nach den zusammengesetzten Werten suchst. Bei findPos machst du es doch auch so, warum nicht bei visited?

[Wodar Hospur]

Ist dir klar, dass dabei etwas ganz anderes herauskommt? Damit machst du deine Koordinatenberechnung kaputt. Du hängst immer wieder 42 an den Vector an, bis der Speicher volläuft.

Genau das verstehe ich ja nicht, wenn ich eine Ganzahl durch eine Ganzzahl teile sollte das Ergebnis ja wieder eine Ganzzahl sein und der Gleitkommaanteil wird einfach abgeschnitten.

Ich nehme an, der Ansatz, zwei Werte in einen unsigned int zu packen, war ein Versuch, den Speicherbedarf zu verringern, aber dabei ist einiges schiefgelaufen.

Joah ziemlich genau, liegt daran das der Algo vorher bei Java je nach Formulierung (mit paar Bugs) ungefähr 400 MB Speicher brauchte.

Wie groß kann denn dein Vector werden? Maximal MAX_X * MAX_Y Einträge. Ich weiß nicht, wie groß die Schachbretter werden sollten, aber das ist ziemlich überschaubar.

Naja dann hab ich aber ja noch die ganzen Lösungsvektoren und die wachsen ja wohl exp.

Und wenn du so etwas machst, solltest du nicht den Faktor 10 benutzen, um die Werte zu trennen. Damit kannst du die Werte zwar schön ansehen, aber der Computer könnte mit einer Zweierpotenz viel schneller rechnen.

Gute Idee, am besten shiffte ich also um 4 Bits.

Nein. Aber die ganze Zerlegerei in zwei Einzelwerte könntest du dir komplett sparen, indem du gleich nach den zusammengesetzten Werten suchst. Bei findPos machst du es doch auch so, warum nicht bei visited?

Danke, klar.

[Guybrush Threepwood]

Genau das verstehe ich ja nicht, wenn ich eine Ganzahl durch eine Ganzzahl teile sollte das Ergebnis ja wieder eine Ganzzahl sein und der Gleitkommaanteil wird einfach abgeschnitten.

Kennst du den Unterschied zwischen / und %?

[Klotzkopp]

Genau das verstehe ich ja nicht, wenn ich eine Ganzahl durch eine Ganzzahl teile sollte das Ergebnis ja wieder eine Ganzzahl sein und der Gleitkommaanteil wird einfach abgeschnitten.

% ist nicht der Operator für Ganzzahldivision. Der Modulooperator liefert den Rest einer Division.

42 / 10 = 4

42 % 10 = 2

Du kannst nicht einfach den einen durch den anderen austauschen.

[Wodar Hospur]

Autsch... AUTSCH.. tut das weh... was hab ich mir dabei gedacht.. peinlich.. ich habs einfach falsch rum aufgezogen, vielen lieben Dank.

Natürlich ist 42 % 10 = 2 und 42 / 10 = 4, aber beides kann für die Aufgabe genommen werden das eine so:

y = 42 & 10 //y=2

x = (42 - y)/10 //x=4

oder aber:

x = 42/10 //x=4

y = 42 - (10*x) //y=2

Wobei es sich auch verbinden lassen würde. Habe allerdings jetzt das Ganze auf einen 4er Shift umgestellt. Schon verbringen ich nur noch die Hälfte der Zeit in der Methode und davon die meiste im Iterator. Das heißt jetzt schau ich mal ob sich der Iterator nicht durch eine zusätzliche Stuktur mit einer konstanten Zugriffszeit (bool array) ergänzen lässt.