3. Array nach Häufigkeit sortieren

Array nach Häufigkeit sortieren

  • R

    Hallo Zusammen,

    ich habe ein Array mit folgendem exemplarischen Inhalt:

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

    Es besteht aus einem Zahlenmuster von 3 Zahlen gefolgt von einer Häufigkeitszahl die
    angibt wie oft das Muster vorgekommen ist. Also "110 1011 10001" ist das Muster be-
    stehend aus drei Zahlen und "23" ist die Zahl die angibt wie oft das Muster vorge-
    kommen ist. Jede Zahl hat aber seinen eigenen Index in dem Array. Die Reihenfolge
    ist aber immer gleich. Also 3 Zahlen (Zahlenmuster) gefolgt von einer Zahl die die Häufig-
    keit der vorangegangenen Zahlen (Zahlenmuster) angibt.

    So, nun möchte ich die Zahlenmuster in dem Array nach den Häufigkeitszahlen sortieren
    ohne das die Zahlenmuster selbst verändert werden. Die Häufigkeitszahlen sollen dabei
    entfernt werden. Also der Output von dem obigen Beispiel wäre dann:

    1011 1010 111 10011 100 11 1011 1001 1001 110 1011 10001

    Vielleicht weiss jemand eine Lösung für das Problem oder kann mir irgendwie weiter-
    helfen? Wäre echt super, danke!

    gruss, rommi

    0
  • R

    Hallo Zusammen,

    die Häufigkeitszahlen können in dem neu sortieren Array auch drin bleiben. Wichtig ist aber dass die Muster nach Häufigkeit sortiert werden und die Muster selbst nicht verändert werden!

    Gruss, rommi

    0
  • V

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

    Gut Schuß
    VuuRWerK 😉

    0
  • K

    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).

    0
  • R

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

    0
  • K

    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.

    0
  • R

    Hallo Knivil,

    ein gutes Beispiel würde mehr sagen als tausend Worte 😞

    Gruss, rommi

    0
  • ?

    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
}
    0
  • Administrator

    @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

    0
  • N

    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... 😉

    0
  • R

    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.

    0
  • Administrator

    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.

    0
  • K

    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.

    0
  • V

    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]

    0
  • N

    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?
    0
  • K

    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?

    0
  • V

    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]

    0
  • K

    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".

    0
  • N

    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

    0
  • R

    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 😃

    0
  • V

    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 😉

    0
Anmelden zum Antworten