Array nach Häufigkeit sortieren

[VuuRWerK]

Ich denke mal da sollte Dir std::priority_queue<T> helfen.

Gut Schuß
VuuRWerK

[knivil]

Erstens: Sortieren und weglassen, sind 2 Dinge, die auch getrennt behandelt werden sollten.

Zweitens: Zahlenmuster und Haeufigkeit gehoeren zusammen, also kann mann sie ja auch mal als explizit zusammengehoerig darstellen. Beispielsweise so:

struct
{
    int muster[3];
    int count;
};

Wenn du Sortieralgorithmen der std benutzen moechtest ist vielleicht ein Zuweisungsoperator und copy-Constructor noetig. Dann schreibst du dir eine Kleiner-Gleich-Operation, die deine Relation spezifiziert. Ich habs mal hier zusammengefasst: Sortieren in C++ für Fortgeschrittene.

Wie du jezt die Haeufigkeit weglaesst, kannst du dir allein ueberlegen (zumal sie ja auch nicht schadet).

[rommi]

Hallo Zusammen,
dass mit der priority_queue schaut interessant aus. Das werd ich mir mal genauer anschauen. Danke erstmal! Gruss rommi

[knivil]

rommi schrieb:

Hallo Zusammen,
dass mit der priority_queue schaut interessant aus. Das werd ich mir mal genauer anschauen. Danke erstmal! Gruss rommi

Jaja, warum einfach, wenn es auch kompliziert geht. Es ist doch nur sortieren.

[rommi]

Hallo Knivil,

ein gutes Beispiel würde mehr sagen als tausend Worte

Gruss, rommi

[sortierer]

viel spaß

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template<typename T>
class zahlenkette
{
public:
    zahlenkette(const T *werte, int n)
    {
        int i;
        m_nZahlen = n-1;
        m_zahlen = new T[m_nZahlen];

        for (i = 0; i < m_nZahlen; ++i)
            m_zahlen[i] = werte[i];
        m_haeufigkeit = werte[i];
    }

    zahlenkette(const zahlenkette &z)
    {
        m_nZahlen = z.m_nZahlen;
        m_zahlen = new T[m_nZahlen];

        for (int i = 0; i < m_nZahlen; ++i)
            m_zahlen[i] = z.m_zahlen[i];
        m_haeufigkeit = z.m_haeufigkeit;
    }

    zahlenkette &operator=(const zahlenkette &z)
    {
        m_nZahlen = z.m_nZahlen;
        delete [] m_zahlen;
        m_zahlen = new T[m_nZahlen];

        for (int i = 0; i < m_nZahlen; ++i)
            m_zahlen[i] = z.m_zahlen[i];
        m_haeufigkeit = z.m_haeufigkeit;

        return *this;
    }

    ~zahlenkette()
    {
        delete [] m_zahlen;
    }

    T getHaeufigkeit() const { return m_haeufigkeit; }
    T getZahl(size_t i) const { return m_zahlen[i]; }

private:
    int m_nZahlen;
    T *m_zahlen;
    T m_haeufigkeit;
};

template<typename T>
bool zahlenkettenvergleich(const zahlenkette<T> &a, const zahlenkette<T> &b)
{
    return a.getHaeufigkeit() < b.getHaeufigkeit();
}

int main()
{
    int test[] = {110, 1011, 10001, 23,
                1011, 1010, 111, 5,
                1011, 1001, 1001, 14,
                10011, 100, 11, 9};
    const int KETTENLAENGE_MIT_HAEUFIGKEIT = 4;
    const int ANZ_WERTE = sizeof(test)/sizeof(int);
    typedef zahlenkette<int> int_kette;

    vector<int_kette> ketten;
    for (int i = 0; i < ANZ_WERTE; i+= KETTENLAENGE_MIT_HAEUFIGKEIT)
        ketten.push_back(int_kette(test + i, KETTENLAENGE_MIT_HAEUFIGKEIT));

    sort(ketten.begin(), ketten.end(), zahlenkettenvergleich<int>);

    for (size_t i = 0; i < ketten.size(); ++i)
        for (int j = 0; j < (KETTENLAENGE_MIT_HAEUFIGKEIT-1); ++j)
            cout << ketten[i].getZahl(j) << " "; //die sortierten zahlenketten evtl. in neues array kopieren
}

[Dravere]

@rommi,
Wie sieht dieses exemplarische Array denn im Programmcode aus?
Ich würde nämlich gleich wie knivil vorgehen und das ganze in eine Struktur oder Klasse packen. Also immer 3 Zahlenfolgen und ihre Häufigkeit in eine Datenstruktur. Zudem einen operator < für diese Datenstrukturen erstellen, welcher die Häufigkeit vergleicht. Diese Datenstrukturen in einem std::vector speichern und danach das folgende anwenden:
http://www.cplusplus.com/reference/algorithm/sort_heap.html
(Beispiel steht unten)

Grüssli

[Nexus]

Dravere schrieb:

Zudem einen operator < für diese Datenstrukturen erstellen, welcher die Häufigkeit vergleicht.

Mit Operatoren bin ich persönlich immer vorsichtig. Gerade bei Fällen, wo die Semantik nicht ganz eindeutig ist, finde ich einen Funktor oder eine Funktion geeigneter. Ein treffender Bezeichner sagt auch meistens mehr als das schlichte < aus...

[rommi]

Ja, nu eigentlich sind es viele Dateien in einem Verzeichnis die alle im Aufbau
gleich sind. Also erst 3 Werte dann die Häufigkeitszahl dann wieder 3 Werte usw.
Den Inhalt jeder Datei lade ich Zeile für Zeile in ein Array (siehe unten steheden
Code) und wenn alle Zeilen in das Array geladen sind würde ich gerne das Array
sortieren und das sortierte Array wieder in die Datei zurückschreiben (überschreiben).
Hier ein Beispiel für den Aufbau bzw. Inhalt so einer Datei:

================== test.txt:

110
1011
10001
23
1011
1010
111
5
1011
1001
1001
14
10011
100
11
9

usw..

================ Hier ein Ausschnitt aus meinem Code

for each (string tmp in vdateiname)		// Jede Datei durchlaufen
{
	//===== Inhalt der Kurzdatei in Array speichern
	ifstream datei(tmp.c_str());	

	while(getline(datei, zeile))		// Zeile für Zeile durchgehen
	{
		stringstream strzulolo(zeile);	// Typumwandulung string to long long 	
		strzulolo >> zahl;		
		vdatinhalt.push_back(zahl);	// Zeile in Array speichern
	}		
}

....
....

Vielleicht noch 2 Hinweise. Die Typ-Umwandlung (siehe Code) hat für den späteren
Code noch eine Bedeutung und ist aber für meine Frage nicht relevant! Ausserdem
können diese Zahlen z.B. 1011 auch ganz anders aussehen z.B. 4267123434534
Also das sind keine Binärzahlen ich habe dass nur gemacht um diese Zahle besser
von den Häufigkeitszahlen zu abstarahieren (sorry!)

Eigentlich hat mich jemand gefragt ob man sowas mit C++ machen kann. Ich hab
gesagt ich versuchs aber leider mach ich auch erst seit ein paar Wochen mit
C++ rum und in meinem C++Buch steht zu diesem Thema nicht soviel drin was
mich jetzt wirklich weiterbringt. Jetzt bin ich halt am überleg überleg überleg ...
Evtl. könnte ich es über eine zweite Liste und dann über ne zwei verschachtelte
for-Schleifen machen aber ob dass das wahre ist?!

Auf jeden Fall erstmal megamässigen Dank an alle für eure Hilfe.

[Dravere]

Umm...

#include <vector>
#include <fstream>
#include <iterator>
#include <algorithm>

struct NumbersWithFrequency
{
	long numbers[3];
	long frequency;
};

std::istream& operator >>(
	std::istream& input,
	NumbersWithFrequency& obj)
{
	input >> obj.numbers[0];
	input >> obj.numbers[1];
	input >> obj.numbers[2];

	input >> obj.frequency;

	return input;
}

std::ostream& operator <<(
	std::ostream& output,
	NumbersWithFrequency const& obj)
{
	output << obj.numbers[0] << '\n';
	output << obj.numbers[1] << '\n';
	output << obj.numbers[2];

	return output;
}

bool operator <(
	NumbersWithFrequency const& lhs,
	NumbersWithFrequency const& rhs)
{
	return lhs.frequency < rhs.frequency;
}

// Sorry Nexus, bin zu faul einen Funktor zu machen :)

int main()
{
	std::ifstream inFile("./inout.txt");
	std::vector<NumbersWithFrequency> data;

	std::copy(
		std::istream_iterator<NumbersWithFrequency>(inFile),
		std::istream_iterator<NumbersWithFrequency>(),
		std::back_inserter(data));

	std::make_heap(data.begin(), data.end());
	std::sort_heap(data.begin(), data.end());

	inFile.close();

	std::ofstream outFile("./inout.txt");

	std::copy(
		data.begin(),
		data.end(),
		std::ostream_iterator<NumbersWithFrequency>(outFile, "\n"));

	return 0;
}

Mist ... jetzt wollte ich eigentlich nur kurze Hilfestellungen geben, damit du selber drauf kommst, aber der Code ist mir nur so aus den Finger geflutscht. Und ich kann mich nicht beherrschen und ihn jetzt einfach löschen ...

Ehm, Fragen?
Vielleicht noch eine C++ Referenz:
http://www.cplusplus.com/reference/

Kommentieren tue ich den Code jetzt nicht. Bin ich wiederrum zu faul.

*am liebsten den Code löschen möchte*

Grüssli

PS: Du kannst den Code Copy&Pasten, aber er ist nicht so optimal. Sollte schliesslich ursprünglich nur ein Hinweis werden. Und ich hoffe du tust es auch nicht, sondern fragst nach, damit du den Code auch verstehst.

[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