Modalwert aus Vector finden (Stroustrup)



  • Hallo
    Ich arbeite mich langsam aber stetig durch Stroustrup's Buch durch und möchte mal die Erfahrenen fragen ob der folgende Code in Ordnung ist oder totaler Mist. Er funktioniert anscheinend soweit.
    Die Aufgabe lautet:

    ...Die Zahl die am häufigsten in einer Reihe auftaucht wird Modalwert genannt. Erstelle ein Programm, das den Modalwert von einer Reihe positiver ganzer Zahlen findet.

    // Modalwert aus Reihe ganzer positiver Zahlen
    #include<iostream>
    #include<string>
    #include<vector>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    int main()
    {
        vector<int> val(8);
        val[0]=5;
        val[1]=0;
        val[2]=2;
        val[3]=2;
        val[4]=4;
        val[5]=33;
        val[6]=4;
        val[7]=4;
        sort(val.begin(),val.end());
        int counter=0;
        int counter2=0;
        int x=0;
        for (int i=0; i<val.size(); ++i)
        {
            for (int j=0; j<val.size(); ++j)
            {
                if (val[i] == val[j])
                    counter=counter+1;
            }
            if (counter>=counter2)
            {
                counter2=counter;
                x=i;
            }
            counter=0;
        }
        cout<<"MODALWERT="<<val[x]<<endl;
    }
    


  • Also auf dem ersten Blick würde ich deine beiden Schleifen als ranged based for bauen.

    //c++11
    for ( const auto & i : val)
    {
        for (const auto & j : val)
        {
        }
    }
    
    //oder
    
    for (vector<int>::const_iterator it = vec.cbegin(); it != vec.cend(); ++it)
    {
    }
    

    Wenn du den Inhalt des Vektors nicht verändern willst solltest du mit const iteratoren arbeiten.

    Ansonsten kannst du auch statt counter+1, ++counter schreiben.



  • Nein, totaler Mist ist das nicht, aber kommt ein bisschen umständlich daher.

    Z.B. hast du die Folge erst sortiert, benutzt dann aber trotzdem einen naiven Algorithmus mit quadratischer Laufzeit, der die Sortiertheit gar nicht ausnutzt.



  • counter2 zählt nix. Würde counter2 z.B. 'currentMax' heissen, hätte ich sofort gewusst, was du machst, so musste ich genau drauf gucken.

    Schön in C++11:

    vector<int> val {1, 434, 22};
    


  • Ruvi schrieb:

    Also auf dem ersten Blick würde ich deine beiden Schleifen als ranged based for bauen.

    Wenn du den Inhalt des Vektors nicht verändern willst solltest du mit const iteratoren arbeiten.

    Ansonsten kannst du auch statt counter+1, ++counter schreiben.

    Ich habe nur die Dinge verwendet die bis zu diesem Kapitel in dem Buch verwendet wurden, von daher kannte ich "ranged based for" und "const iterator" noch nicht. Aber ich schau auch gerne mal über den Tellerrand :). Das ++counter hätte ich natürlich schon wissen müssen.

    MC Elch schrieb:

    benutzt dann aber trotzdem einen naiven Algorithmus mit quadratischer Laufzeit, der die Sortiertheit gar nicht ausnutzt.

    Ja, danke das du mich darauf hingewiesen hast. Das kam von den zig Versuchen das Ding hinzubekommen. Ich hatte gelesen das man es halt durch sortieren hinbekommen kann, das hab ich ewig probiert und bin dann später da gelandet wo der Code jetzt steht. Ich hab immer noch keine Vorstellung wie das Funktionieren soll. Der Sinn war doch die Nummern zu sortieren um dann in einer Schleife herauszufinden welcher Wert am meisten hintereinander erscheint. Aber wie Ordne ich dann gleichzeitig den höchsten Wert der Position im Vector zu?
    Ich denke ich muss einfach noch viel mehr Aufgaben dieser Art üben damit sich mir diese Logik besser erschließt 💡

    @Jockelx
    danke für den Hinweis

    Ich habe jetzt alles soweit gestrichen/geändert und den naiven Algorithmus mit quadratischer Laufzeit weiter verwendet da ich noch kein Plan habe wie ich das sortieren des Vectors nutzen soll. Und was bingt das Sortieren gegenüber dem "naiven Algorithmus mit quadratischer Laufzeit" für Vorteile außer das es nicht "naiv" ist? 😃

    int main()
    {
        vector<int> val{5,0,2,2,4,33,4,4};
        int counter=0;
        int currentMax=0;
        int x=0;
        for (int i=0; i<val.size(); ++i)
        {
            for (int j=0; j<val.size(); ++j)
            {
                if (val[i] == val[j])
                    counter=++counter;
            }
            if (counter>=currentMax)
            {
                currentMax=counter;
                x=i;
            }
            counter=0;
        }
        cout<<"MODALWERT="<<val[x]<<endl;
    }
    


  • pauledd schrieb:

    da ich noch kein Plan habe wie ich das sortieren des Vectors nutzen soll. Und was bingt das Sortieren gegenüber dem "naiven Algorithmus mit quadratischer Laufzeit" für Vorteile außer das es nicht "naiv" ist? 😃

    Für dein kleines Beispiel ist das im Endeffekt wurscht, aber stell dir vor, du bekommst als Input nicht 10 sondern 1000 oder noch mehr Zahlen. Dann wird deine innere Schleife nicht 100 sondern 1.000.000+ mal durchlaufen, das skaliert halt einfach nicht gut.

    Wenn du den Vektor eh schon sortierst, hast du ja identische Zahlen als "Runs" zusammengruppiert, dann reicht es einmal durchzulaufen, mitzuzählen, wie lang der aktuelle Run ist und welchen Zahlenwert er hat, und das vergleichst du mit dem längsten bisher gefundenem Run und updatest den bei Bedarf. Das geht in linearer Zeit und ist gegenüber dem Sortieren quasi kostenlos und insgesamt viel besser als die quadratische Lösung.



  • Meine Loesung mit einer Schleife wuerde irgendwie so aussehen.
    Ich hoffe ich hab nichts uebersehen.

    #include <vector>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
    	vector<int> val{ 5, 0, 2, 2, 4, 33, 4, 4 };
    
    	int counter = 0;
    	int currentMax = 0;
    
    	vector<int>::const_iterator modal_value;
    	vector<int>::const_iterator last_number = std::cbegin(val);
    
    	std::sort(std::begin(val), std::end(val));
    
    	for (auto cit = std::cbegin(val); cit != std::cend(val); ++cit)
    	{
    		if (*cit == *last_number)
    		{
    			++counter;
    		}
    		else
    		{
    			if (counter >= currentMax)
    			{
    				currentMax = counter;
    				modal_value = last_number;
    				counter = 0;
    			}
    			last_number = cit;
    		}
    	}
    
    	cout << "MODALWERT=" << *modal_value << endl;
    
    	system("PAUSE");
    	return 0;
    }
    


  • MC Elch schrieb:

    Wenn du den Vektor eh schon sortierst, hast du ja identische Zahlen als "Runs" zusammengruppiert, dann reicht es einmal durchzulaufen, mitzuzählen, wie lang der aktuelle Run ist und welchen Zahlenwert er hat, und das vergleichst du mit dem längsten bisher gefundenem Run und updatest den bei Bedarf. Das geht in linearer Zeit und ist gegenüber dem Sortieren quasi kostenlos und insgesamt viel besser als die quadratische Lösung.

    Sortieren ist langsam. Den Median erhält man mit std::nth_element .



  • enf elem schrieb:

    Sortieren ist langsam. Den Median erhält man mit std::nth_element .

    Vom Median ist ja auch nicht die Rede.



  • Ich hab jetzt noch was mit sortieren zu bieten:

    int main()
    {
        vector<int> val {4,0,4,2,2,4,5,33};
        sort(val.begin(),val.end());
        int m=0;
        for (int i=0; i<val.size(); ++i)
        {
            if (val[i]==val[i+1])
                m=val[i];
        }
        cout<<"Modalwert="<<m;
    }
    

    Ist das Ok soweit?



  • Du brauchst die #includes und das using namespace std; nicht abzuschneiden. Das macht copy und paste nur umständlicher für alle, die Deinen Code kompiliern möchten.

    Es gibt neben operator[]() noch den Zugriff auf Vektorelemente mit at() . at() kontrolliert ob der Index auf den zugegriffen wird gültig ist.
    Da gibt es dann eine Überraschung, wenn Du Z. 8 und 9 ersetzt:

    if (val.at(i)==val.at(i+1))
                m=val.at(i);
    


  • Ist das Ok soweit?

    Nein, du liest jenseits der Vectorgrenzen:

    for (int i=0; i<val.size(); ++i)
    {
        if(val[i]==val[i+1])
                   // ^^^^^ da
            m=val[i];
    }
    

    Davon abgesehen ist deine Implementierung auch falsch. Versuch mal diesen vector:

    {0, 2, 4, 0, 0, 0, 0, 0, 2, 4}
    

    Dein Algorithmus sucht die letzte Zahl, die mindestens zweimal vorkommt.

    Vorgehensweise: Sortieren, zählen bis eine neue Zahl kommt. Dann neu zählen. Wenn die neue Zahl öfter vorkommt, als die alte: neue Zahl merken, neue Anzahl merken, weitermachen.



  • nächster Versuch:

    // Modalwert aus Reihe ganzer positiver Zahlen
    #include<iostream>
    #include<string>
    #include<vector>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    int main()
    {
        vector<int> val {0, 2, 4, 0, 0, 0, 0, 0, 2, 4};
        sort(val.begin(),val.end());
        int counter_old=0;
        int counter_new=0;
        int cur_max=0;
        for (int i=0; i<val.size(); ++i)
        {
            if (i>0 && val[i]==val[i-1])        // Wenn 2. Wert im Vektor gleich dem 1.
            {
                counter_old=++counter_old;      // alten Zähler erhöhen
                if (counter_old>counter_new)    // wenn alter Zähler größer Vektorwert in cur_max speichern
                {
                    cur_max=val[i];
                    counter_new=counter_old;
                }
            }
            else
                counter_old=0;                  // Wenn Vektor Paar ungleich alten Zähler zurücksetzen
        }
        cout<<"M="<<cur_max<<endl;
    }
    


  • pauledd schrieb:

    nächster Versuch:

    if (i>0 && val[i]==val[i-1])        // Wenn 2. Wert im Vektor gleich dem
    

    Selbst, wenn du es hier mit i>0 abfängst es ist immer eine schlechte Idee im Vector vor oder zurückzugucken.

    Guck Dir mal die Lösung an die ich geschrieben habe und tausch die iteratoren einfach mit richtigen ints aus oder merk dir die last_number einfach.
    Du kannst es natürlich auch mit einem bool lösen aber +1 , -1 im Vector ist selbst mit abfangen eine schlechte Lösung. (Nach meiner Meinung)

    Wenn du es mit iteratoren machst musst du nicht kopieren ansonsten kopier, das int einfach das kostet nichts.



  • Ok ich schau mir nochmal dein Code an. Aber ich denke ich habe die Aufgabe im Rahmen der bisher behandelten Mittel des Buches gelöst da ich den Begriff "Iterator" bzw. "const_iterator" noch nicht gelesen habe (kommt irgendwo ab Seite 700 :D, bin auf Seite 155).

    Ein paar Fragen zu deinem Code:

    warum schreibst du eigentlich immer das

    std::
    

    davor?

    was macht das auto in ?

    for (auto cit...
    

    was macht das * hier?

    if (*cit == *last_number)
    


  • pauledd schrieb:

    std::
    

    davor?

    Das ist einfach Gewohnheit, da ich schon oben using namespace std; geschrieben habe ist es eigentlich nicht nötig.
    Wenn du deinen Source -Code in Header(hpp) und CPP files trennst, wirst du die using deklarationen, wenn überhaupt nur im cpp File haben.

    pauledd schrieb:

    was macht das auto in ?
    C++:

    for (auto cit...
    

    auto ist einfach etwas für Schreibfaule, gerade bei iteratoren ist es manchmal ziemlich anstrengend den Typ genau aufzuschreiben.

    std::cbegin(val); // returned einen vector<int>::const_iterator
                      // das auto macht es überflüssig es explizit hinzuschreiben
    for (auto cit = std::cbegin(val);
    // und
    for (std::vector<int>::const_iterator cit;
    // sind das gleiche, das andere ist aber kürzer
    

    pauledd schrieb:

    was macht das * hier?

    if (*cit == *last_number)
    

    Wahrscheinlich bist du in deinem Buch noch nicht zu Pointern gekommen.
    Ein iterator ist ein Objekt der in einem Container auf ein gewisses Objekt zeigt.
    Wenn ich einfach "==" ohne "" verwenden würde, würde ich den Computer fragen sind die Iteratoren cit und last_number gleich.
    Mit anderen Worten zeigen die beiden Iteratoren auf das gleiche Element im Container.
    Ich möchte aber wissen ob das Value auf, dass sie zeigen gleich ist und dafür muss ich den Iterator mit "
    " dereferenzieren.

    Ich hoffe, dass war halbwegs verständlich.



  • Das mit den Iteratoren kannste dir so vorstellen:

    int begin = 0u; // Iterator auf Anfang: vector<int>::iterator begin = vec.begin();
    int end = vec.size(); // Iterator auf Ende: vector<int>::iterator end = vec.end()
    ++begin; // gehe zum nächsten Element: ++begin
    vec[begin]; // lese Wert an Stelle begin: *begin
    begin == end; // vergleiche die Position von begin mit end: begin == end
    


  • Ruvi schrieb:

    Wahrscheinlich bist du in deinem Buch noch nicht zu Pointern gekommen.

    So ist es.

    So ganz erschließt sich mir das noch nicht aber vielen Dank für eure
    Erläuterungen. Ich werde diesen Thread sicher nocheinmal aufsuchen
    und dann mit fortgeschrittenem Wissen herangehen.


Log in to reply