Source lesen und verstehen lernen

[knivil]

bisschen einseitige buchtips. findeste nicht?

Ich bin weder Amazon noch google, auch nicht seine Mutti. Also muss es reichen, nur den Weg zur Toilette zu weisen, anstatt ihm auch noch den Hintern (Arsch wird leider zensiert) abzuwischen.

[volkard]

knivil schrieb:

bisschen einseitige buchtips. findeste nicht?

Ich bin weder Amazon noch google

Trotzdem wirkt es ein bißchen seltsam, daß Du bei drei Büchern ecp gleich zweimal nennst.

Ansonsten ist die Buchauswahl für diesen Zweck ideal. Effektiv C++ programmieren und Modern C++ design. Wozu noch mehr?

[knivil]

Ok, das eine sollte More Effective C++ ... sein.

[ZSchneidi]

knivil : hey wie bist du denn drauf ? ^^

musst ja wirklich schlechte laune haben manchmal oder ?
Ich hatte dich ja auch nicht gebeten mir den ... abzuwischen.
Die Buchtips scheinen ja ganz brauchbar, kommt dann bei Zeiten mal.

Und dass ich es nicht kapieren will, würde ich nicht behaupten, dann würde ich mir keinen Kopf machen. Das mit der Gitarre war auch nur n beispiel, wenn du von sowas schonmal gehört hast Hör auf +fricky, der hats verstanden.

Und mit ner Vorlesung für höhere Mathematik würde ich vielleicht wirlich meine Schwierigkeiten haben, aber Code ist Code und ich hab noch keinen gesehen, den ich nicht lesen konnte, an sich kann man das meiste gut nachvollziehen, warum also nicht mal nen Blick drauf werfen.

Wenn du mir mal konkret sagen könntest warum das nen schlechter Ansatz sein sollte, würde ich das vielleicht noch nachvollziehen können, du sagst aber immer nur das is der falsche weg und bringt alles nichts. Das kann ich jetz auf anhieb so nicht bestätigen, mir brachte das schon ein wenig mehr einsicht.

[volkard]

Ausgerechnet unser Haustroll hat's verstanden. Da würde ich jetzt ganz vorsichtig sein, ob er Dich nicht nur veralbern wollte.

[knivil]

Viel Spass beim Raten: Was macht die Funktion scan? Um es etwas schwieriger zu machen, habe ich mal die Kommentare entfernt. Die grobe Idee als auch deren Umsetzung kann in wenigen Zeilen hingeschrieben werden. Das Lesen und Verstehen dieser Zeilen dauert etwa 5 min (etwas Erfahrung vorausgesetzt). Ich erhebe keinen Anspruch darauf, dass diese Loesung besonders elegant ist. Ich selbst finde sie dennoch schoen. Trivialitaeten habe ich mal weggelassen, falls dir noch etwas fehlt, dann sag Bescheid.

PS: Diese Zeilen sind fuer dich persoenlich zum Testen, wie gut das mit dem Verstehen von Sourcecode klappt. Du brauchst mir nichts zu beweisen. Auch will ich niemanden hier etwas beweisen, nur dass es recht schwierig ist, dem Sourcecode zu Grunde liegende Konzepte zu verstehen.

class Point
{
	public:
		double m_x,m_y;
		Point();
		Point(double x, double y);
		Point(const Point& p);

		Point operator-(const Point& p) const;
		const Point& operator=(const Point& p);
		bool operator==(const Point& p) const;

		bool leftOf(const Point& p1, const Point& p2) const;

		bool collinear(const Point& p1, const Point& p2) const;
};

bool Point::leftOf(const Point& p1, const Point& p2) const
{
	Point r(*this - p1);
	Point q(p2 - p1);
	return (q.m_x*r.m_y - q.m_y*r.m_x) > 0;
}

bool Point::collinear(const Point& p1, const Point& p2) const
{
	Point r(*this - p1);
	Point q(p2 - p1);
	return (q.m_x*r.m_y - q.m_y*r.m_x) == 0;
}

class ScanPred
{
	private:
		Point a;
	public:
		ScanPred(const Point& p);
		bool operator()(const Point& p1, const Point& p2) const;
};

class SortPred
{
	public:
		bool operator()(const Point& p1, const Point& p2) const;
};

ScanPred::ScanPred(const Point& p)
{
	a = p;
}

bool ScanPred::operator()(const Point& p1, const Point& p2) const
{
	return p1.leftOf(a,p2);
}

bool SortPred::operator()(const Point& p1, const Point& p2) const
{
	if( p1.y() < p2.y())
		return true;

	if ((p1.y() == p2.y()) && (p1.x() < p2.x()))
		return true;

	return false;
}

void scan(std::deque<Point>& set)
{

	std::sort(set.begin(), set.end(),SortPred());

	std::deque<Point>::iterator new_end = std::unique(set.begin(),set.end());
	set.erase(new_end,set.end());

	if (set.size() < 3) return;

	Point min = set.front();
	Point max = set.back();
	set.pop_front();

	std::sort(set.begin(),set.end(),ScanPred(min));

	set.push_back(min);
	set.push_front(min);

	std::stack<Point> conv_stack;
	conv_stack.push(set.back());
	set.pop_back();
	conv_stack.push(set.back());
	set.pop_back();

	while(set.size() > 1)
	{
		Point tmpM	= conv_stack.top();
		conv_stack.pop();
		if (tmpM.leftOf(conv_stack.top(),set.back()))
		{
			// mache nichts :-)
		}
		else
		{
			conv_stack.push(tmpM);
			conv_stack.push(set.back());
			set.pop_back();
		}
	}

	while (conv_stack.size() > 1)
	{
		Point tmpM = conv_stack.top();
		conv_stack.pop();

		if (tmpM.collinear(set.front(),conv_stack.top()))
		{
			// mache nichts :-)
		}
		else
		{
			set.push_front(tmpM);
		}
	}

	if (set.size() == 1)
	{
		set.push_front(max);
	}
}

Hör auf +fricky

Da wuerde ich meine Seele der Verdammnis preisgeben.

[+fricky]

knivil schrieb:

Viel Spass beim Raten: Was macht die Funktion scan?

kommentare raushauen ist unfair, aber grob geraten: punkte aussortieren die nicht auf einer geraden liegen.

[knivil]

Naja, man mag streiten, ob Kommentare Teil des Quelltextes sind. Mit Kommentaren braeuchte man sich den Quelltext nicht mehr ansehen, um zu verstehen. Ich bin da immer recht grosszuegig. Auch hat die Funktion scan einen treffenderen Namen im Original. Ansonsten falsch geraten.

[Profi-Progger]

ZSchneidi schrieb:

Und mit ner Vorlesung für höhere Mathematik würde ich vielleicht wirlich meine Schwierigkeiten haben, aber Code ist Code und ich hab noch keinen gesehen, den ich nicht lesen konnte, an sich kann man das meiste gut nachvollziehen, warum also nicht mal nen Blick drauf werfen.

Knivil hat ja schon ein schönes Beispiel gezeigt. Deine Technik funktioniert nur bei Trivialprogrammen, bei Software die auch etwas tut hat man selbst mit ordentlicher Kommentierung noch ordentlich Hirnschmalz zu investieren.

[ZSchneidi]

knivil : nette Idee, werd mich mal daran versuchen, momentan is nur schlecht, da ich noch auf Arbeit sitze ^^

Werd bei gelegenheit mal versuchen das zu analysieren.

Ui so eindeutige Meinungen zu +fricky, sollte ich da was wissen ?

[volkard]

Wenn der Erfinder des Algos zu Halloween Geburtstag hat, dann weiß ich, was die Funktion scan macht. Eigentlich kam ich durchs Lesen von leftOf drauf und weil ich sowas auch mal gebaut habe (aber naiv) und gar nicht so durchs Lesen des Hauptcodes.

[ZSchneidi]

Ok, ich konnts nicht lassen und habs mir doch mal angesehen.

Und muss sagen is ziemlich simple ... ^^
Ne spaß beiseite, ich konnte damit jetzt nicht wirklich viel anfangen.

Hab mir die Referenz zur Hand genommen, aber selbst die konnt mir jetzt nicht wirklich weiter helfen. Es ist noch nichtmal unbedingt das semantische, sondern geht schon beim Syntaktischen los.

void scan(std::deque<Point>& set)
{

    std::sort(set.begin(), set.end(),SortPred());

    std::deque<Point>::iterator new_end = std::unique(set.begin(),set.end());

Hier beispielsweise : "deque<Point>" hab ich auch noch nicht gesehen sowas.
Mir fehlt auch noch der Ansatz was set an dieser stelle ist. Kann kann ich alles noch nicht so ganz nachvollziehen.

Was würdest du selbst sagen, welchen grad an Schwierigkeit die Source aufweist ?
Wenn du mir jetz sagst, das is Kinderkram und sollte keine Probleme machen, sollte ich mir ernsthaft gedanken machen

[+fricky]

ZSchneidi schrieb:

Ui so eindeutige Meinungen zu +fricky, sollte ich da was wissen ?

wegen dem werden die c++ flamethreads immer so lang.

[Profi-Progger]

ZSchneidi schrieb:

Ok, ich konnts nicht lassen und habs mir doch mal angesehen.

Und muss sagen is ziemlich simple ... ^^
Ne spaß beiseite, ich konnte damit jetzt nicht wirklich viel anfangen.

Hab mir die Referenz zur Hand genommen, aber selbst die konnt mir jetzt nicht wirklich weiter helfen. Es ist noch nichtmal unbedingt das semantische, sondern geht schon beim Syntaktischen los.

void scan(std::deque<Point>& set)
{

    std::sort(set.begin(), set.end(),SortPred());

    std::deque<Point>::iterator new_end = std::unique(set.begin(),set.end());

Hier beispielsweise : "deque<Point>" hab ich auch noch nicht gesehen sowas.
Mir fehlt auch noch der Ansatz was set an dieser stelle ist. Kann kann ich alles noch nicht so ganz nachvollziehen.

Was würdest du selbst sagen, welchen grad an Schwierigkeit die Source aufweist ?
Wenn du mir jetz sagst, das is Kinderkram und sollte keine Probleme machen, sollte ich mir ernsthaft gedanken machen

Syntaktisch ist der Code sehr leicht zu verstehen, vorausgesetzt man beherrscht C++
Die Semantik ist natürlich etwas ganz anderes, und ich habe zwar eine starke Vermutung was der Code macht, aber habe es noch nicht verifiziert (kann man ja einfach mit ein paar Zahlenbeispielen überprüfen, ob man recht hatte).
Wer allerdings noch nie solche Algorithmen studiert hat wird wohl eher keine Chance haben darauf zu kommen.

[knivil]

@ZSchneidi: In der Signatur steht, dass eine Menge (deswegen der Name set (eng.)) von Punkten (2D) als In/Out-Parametern der Funktion uebergeben wird. Der verwendete Container ist halt std::deque. In der ersten Zeile der Funktion werden die Punkte gemaess dem Praedikat (erst nach X, dann nach Y Koordinate, siehe SortPred::operator()( ...) ) sortiert. Danach werden alle doppelten Punkte mittels unique und Vergleichsoperator (Point::operator==( ... ) ) entfernt. Danach ist die Vorverarbeitung abgeschlossen.

Zum Schwierigkeitsgrad: ist schon fortgeschritten. Aber in Anwendungssoftware wirst du hauptsaechlich fortgeschrittenen Code oder schwieriger finden.

PS: Ich kann dir ja mal etwas Zeit geben und loese es dann naechste Woche oder so auf.

Wer allerdings noch nie solche Algorithmen studiert hat wird wohl eher keine Chance haben darauf zu kommen.

Gimp wurde mal als Beispiel genannt. Deswegen dachte ich, ein algorithmisches Beispiel ist nicht schlecht (und es war mein einziges weniger umfangreiches).

[+fricky]

knivil schrieb:

Gimp wurde mal als Beispiel genannt. Deswegen dachte ich, ein algorithmisches Beispiel ist nicht schlecht (und es war mein einziges weniger umfangreiches)

wenn du den gimp-code nimmst, sind verzeichnisnamen und namen der source-files, funktionen, structuren, variablen, etc. schon mal wichtige hinweise. wenn du dann noch mit 'nem reverse-enigneering tool rübergehst und siehst, welche funktionen welche aufrufen, wie was benutzt wird usw, dann haste schon viele informationen. bei deinem code sieht man z.b. nicht, in welchem zusammenhang er verwendet wird. das macht es etwas schwieriger. ausserdem ist gimp leichter zu lesen, weil in C geschrieben. *grins*

[knivil]

welchem zusammenhang er verwendet wird.

straight forward wird scan verwendet. Die Punkte werden in der main eingelesen und ausgegeben.

[hustbaer]

Ehrlich gesagt, wen interessiert schon was der Code tut?
Wozu sollte ich mich durch etwas nicht dokumentiertes durchkämpfen wollen, vor allem wenn das Original a) bessere Namen und b) Kommentare enthält???

Davon abgesehen hat das nichts mit Software-Design oder sonstwas zu tun, das ist schlicht und ergreifend ein Algorithmus.
Wieso ich den verstehen wollen würde, wenn ich bloss das Design einer grösseren Anwendung verstehen möchte, entzieht sich mir grad vollkommen.

[knivil]

Davon abgesehen hat das nichts mit Software-Design oder sonstwas zu tun, das ist schlicht und ergreifend ein Algorithmus. Wieso ich den verstehen wollen würde, wenn ich bloss das Design einer grösseren Anwendung verstehen möchte, entzieht sich mir grad vollkommen.

Sag das nicht mir, sondern ZSchneidi. Denn genau darum geht es. Auch verweise ich auf den Threadtitel. Der Source ist nicht fuer dich oder sonst wen gedacht, sondern einzig und allen fuer ZSchneidi. Er war der Meinung mittels Sourcecode (Implementation) zu lernen, wie es die "Grossen" so machen. Das hier dient als Beispiel, wie man schwerlich von Sourcecode auf Implementationsideen schliessen kann. Auch sind Kommentare in realen Projekten recht rar, die Funktion scan haette ich auch nicht benennen brauchen, sondern alles gleich in die main hauen koennen.

[volkard]

Aber ich habs rausgefunden.
*hüpf*
*meld*
Jetzt lobe mich doch mal.
*hüpf*
*meld*