Array nach Häufigkeit sortieren

knivil

rommi schrieb:

Hallo Knivil,

ein gutes Beispiel würde mehr sagen als tausend Worte

Gruss, rommi

Da ist ein Link und damals habe ich es geschafft, alles auf 3 Seiten zusammenzufassen, was man ueber Sortieren in C++ wissen sollte. Da sind auch 3 Beispiele enthalten. Ich versuche es zu vermeiden, copy-paste-Loesungen anzubieten, da hat man ja nicht mal 'ne Chance nachzudenken.

VuuRWerK

Da ich ja das Beispiel mit der priority_queue gebracht habe fühlte ich mich kurz dazu genötigt ein Beispiel zu implementieren :>

Aber Vorsicht, sehr quick and dirty!!!

#include <iostream>
#include <fstream>
#include <string>
#include <queue>
#include <algorithm>

typedef struct {
	std::string* bits;
	int amount;
} file_content;

struct compare {
	int operator()(const file_content& c1, const file_content& c2) {
		return c1.amount < c2.amount;
	}
};

void read_file() {
	std::ifstream in("test.txt");
	std::string line;
	std::priority_queue<file_content,
		std::vector<file_content>,
		compare> q;
	int c = 0;
	file_content content;
	content.bits = new std::string[3];
	while (getline(in, line)) {
		if (c < 3) {
			content.bits[c++] = line;
		} else if (c == 3) {
			content.amount = atoi(line.c_str());
			q.push(content);
			content.bits = new std::string[3];
			content.amount = 0;
			c = 0;
		}
	}
	delete[] content.bits; // for all the squealers ...
	in.close();
	std::cout << "*** sorted by amount ***" << std::endl;
	while(!q.empty()) {
		file_content c = q.top();
		std::cout << "bits(amount: " << c.amount << "): ";
		for (unsigned int j = 0; j < 3; ++j)
			std::cout << c.bits[j] << " | ";

		std::cout << std::endl;
		q.pop();
	}
}

int main(int argc, char* argv[]) {
	read_file();
	return 0;
}

Das per Hand sortieren wie es ebenfalls vorgeschlagen wurde ist natürlich auch möglich aber mit der priority_queue ist es halt immer sortiert vorliegend.

Gut Schuß
VuuRWerK

[edit]Speicher freigegeben. (Da dies wirklich nicht schön ist, auch nicht bei einem quick-and-dirty Beispiel ...)[/edit]

Nexus

Von dem Code meines Vorposters rate ich ab.

content.bits = new std::string[3];

Bereits bei dieser Zeile stellen sich mir vier Fragen:

Wieso braucht es einen Zeiger?
Warum ein Array von 3 std::string s?
Wo wird der angeforderte Speicher freigegeben?
Weshalb nimmt man nicht gleich einen Konstruktor, um die Initialisierung sicherzustellen?

knivil

Dravere hat eindeutig den besten Code (wir sollen 'ne Abstimmung machen). Die beiden anderen finde ich grausam, halt quick and dirty. Da es aber oeffentlich und fuer alle ansehbar ist, sollte man sich schon etwas Muehe geben. Da brauche ich mich nicht zu wundern, warum mein Arbeitsplatz sicher ist.

Ich frage mich nur: Warum make_heap, sort_heap, wenn es ein einfaches sort auch tut?

VuuRWerK

Ich hoffe Du hast folgendes gelesen:

Aber Vorsicht, sehr quick and dirty!!!

Eigentlich wollte ich noch dazuschreiben das ich es so nie machen würde aber das fand ich überflüssig weil es selbstverständlich ist, es ging mir nur darum ein kurzes Beispiel zu liefern wie man es mit priority_queue machen kann, fertig. Zudem wollte ich nicht mehr als 3 minuten investieren.

Aber ich muss mich eigentlich nicht rechtfertigen ...

Gut Schuß
VuuRWerK

[edit]Mein Arbeitsplatz ist ebenfalls sicher weil ich obiges nicht abliefern würde, aber wie schon gesagt ...[/edit]

knivil

Nein, du musst dich nicht rechtfertigen. Ich habe gelesen, dass es quick and dirty ist. Es ist eher ein allgemeines Phaenomen. Leider wird sowas dann erstmal von Anfaengern gern ungefragt uebernommen. Bei zwei Seiten gibt es manchmal auf beiden Seiten "Schuld".

Nexus

VuuRWerK schrieb:

Ich hoffe Du hast folgendes gelesen:

Aber Vorsicht, sehr quick and dirty!!!

Eigentlich wollte ich noch dazuschreiben das ich es so nie machen würde aber das fand ich überflüssig weil es selbstverständlich ist, es ging mir nur darum ein kurzes Beispiel zu liefern wie man es mit priority_queue machen kann, fertig. Zudem wollte ich nicht mehr als 3 minuten investieren.

Ja, das habe ich in der Tat gelesen. Vielleicht wäre es sinnvoller gewesen, kein Codebeispiel zu liefern. Das ist jetzt nicht böse gemeint, aber als Anfänger nimmt man sich viel zu schnell ein Beispiel an deinem Code. Zumal die Einstellung "Hauptsache, es geht, Code ist ja egal" unter Anfängern sehr verbreitet ist.

Aber abgesehen davon: Selbst in den drei Minuten wäre es nicht nur möglich gewesen, sondern auch einfacher und kürzer gegangen, ein String-Objekt anstelle eines Zeigers zu nehmen.

VuuRWerK schrieb:

Aber ich muss mich eigentlich nicht rechtfertigen ...

Nicht? Warum tust du es dann? :p

rommi

Phewww, das ist ja ne Menge Holz

Ich schau mir jetzt mal eins nach dem anderen in Ruhe an, schliesslich sollte man erstmal langsam anfangen! Jetzt hab ich gedacht "Deutsche Sprache schwere Sprache" aber seitdem ich C-- gesehen habe...

@Daravere:
Kann jedem mal passieren dass einem soein Ding rausflutschschschscht.
Gaaaanz ehrlich ich hab mir deinen Code garnicht angeschaut. Ich weiss praktisch garnix davon... Trotdem lieb von dir!

Auf jeden Fall nochmal Danke, und wenns nach mir gehen würde bekommt Ihr
für den Rest des Tages frei

VuuRWerK

Nexus schrieb:

VuuRWerK schrieb:

Ich hoffe Du hast folgendes gelesen:

Aber Vorsicht, sehr quick and dirty!!!

Eigentlich wollte ich noch dazuschreiben das ich es so nie machen würde aber das fand ich überflüssig weil es selbstverständlich ist, es ging mir nur darum ein kurzes Beispiel zu liefern wie man es mit priority_queue machen kann, fertig. Zudem wollte ich nicht mehr als 3 minuten investieren.

Ja, das habe ich in der Tat gelesen. Vielleicht wäre es sinnvoller gewesen, kein Codebeispiel zu liefern. Das ist jetzt nicht böse gemeint, aber als Anfänger nimmt man sich viel zu schnell ein Beispiel an deinem Code. Zumal die Einstellung "Hauptsache, es geht, Code ist ja egal" unter Anfängern sehr verbreitet ist.

Aber abgesehen davon: Selbst in den drei Minuten wäre es nicht nur möglich gewesen, sondern auch einfacher und kürzer gegangen, ein String-Objekt anstelle eines Zeigers zu nehmen.

Stimm ich Dir auch voll und ganz zu, aber ich war nicht davon ausgegangen das er völliger Anfänger ist.
Hab es oben aber mal editiert damit wenigstens der Speicher frei gegeben wird wie es sich natürlich auch gehört!

Nexus schrieb:

VuuRWerK schrieb:

Aber ich muss mich eigentlich nicht rechtfertigen ...

Nicht? Warum tust du es dann? :p

Da ich weiß das ich es besser kann und mich ein wenig angekratzt gefühlt habe

Gut Schuß
VuuRWerK

Dravere

knivil schrieb:

Ich frage mich nur: Warum make_heap, sort_heap, wenn es ein einfaches sort auch tut?

Weil bei std::sort nicht definiert ist, was für ein Sortieralgorithmus verwendet wird. Es wäre korrekt, wenn ein Bubblesort im Hintergrund verwendet wird. Ich glaube allerdings, dass meistens ein Quicksort verwendet wird. Der kann aber im Worstcase Szenario auf O(n^2) gehen, ist aber eher unwahrscheinlich. Ein Heapsort dagegen hat eine sichere Laufzeit von O(n*log(n)). Der Heapsort ist eines der schnellsten instabilen Sortierverfahen. Informationen dazu:
http://de.wikipedia.org/wiki/Sortieralgorithmen

rommi schrieb:

@Daravere:
Kann jedem mal passieren dass einem soein Ding rausflutschschschscht.
Gaaaanz ehrlich ich hab mir deinen Code garnicht angeschaut. Ich weiss praktisch garnix davon... Trotdem lieb von dir!

Grad garnix? Hmmm, ok.
Dann vielleicht doch ein paar Hilfestellungen, mal schauen:
1. Statt getline könntest du gleich die Zahlen über den operator >> einlesen. Leerzeichen werden automatisch ignoriert.
2. Was ich gemacht habe, ist eine Struktur zu erstellen, welche eine eigene Überladung für den operator >> auf einen std::istream (Basisklasse von std::ifstream ) hat. Die Struktur speichert immer 3 Zahlen und die Häufigkeit.
3. Ich lese nun immer solche Strukturen als ganzes ein und speichere sie in einem std::vector ab.
4. Die Struktur hat einen operator < , welcher die Häufigkeit vergleicht. Dadurch ist es mir möglich herauszufinden, welche Häufigkeit mit welchen Zahlen zuerst kommen soll.
5. Die Sortierung lagere ich allerdings an Standardfunktionen aus. std::make_heap bereitet die Sortierung vor und std::sort_heap führt die Sortierung schlussendlich durch.
6. Schlussendlich habe ich für die Struktur noch den operator << überladen auf einen std::ostream (Basisklasse von std::ofstream ). Bei der Ausgabe, werden nur die Zahlen ausgegeben und jeweils durch ein Linefeed (neue Zeile) getrennt. Ich gebe also einfach alle Strukturen in meinem std::vector an den Stream.

Das ganze habe ich "vereinfacht" mit Funktionen und Strukturen aus der Standardbibliothek, wie std::copy , std::ostream_iterator oder std::istream_iterator .

Aber vielleicht bringt dich dies nun auf die Idee, welche ich genutzt habe.

Grüssli

knivil

std::sort nicht definiert ist, was für ein Sortieralgorithmus verwendet wird

Keine Ahnung was der Standard sagt, aber auf der Seite von SGI steht O( n log n ) als worst case. Ja, der Sortieralgorithmus ist nicht angegeben.

volkard

Dravere schrieb:

Der Heapsort ist eines der schnellsten instabilen Sortierverfahen.

lies auch http://de.wikipedia.org/wiki/Introsort

Dravere

knivil schrieb:

Keine Ahnung was der Standard sagt, aber auf der Seite von SGI steht O( n log n ) als worst case. Ja, der Sortieralgorithmus ist nicht angegeben.

Der Standard sagt, dass es ca. O(n * log(n)) sein muss. Aber eben nur ca., vorgeschrieben ist es nicht.

@volkard,
Ja, ist mir bekannt. Heapsort bleibt aber einer der schnellsten. Ich sagte ja nicht der schnellste. Introsort wird übrigens auch auf Wikipedia im Artikel von Quicksort erwähnt.
Danke trotzdem für den Link.

Grüssli