[gelöst]Sortieren und Aufbereiten von Daten in einem Vectorarray mit Struct



  • Hallo zusammen,

    ich erzeuge ein Vectorarray aus Messdaten mit ca. 200000 Zeilen mit je 4 Werten pro Zeile.

    Eine Zeile sieht dabei so aus:
    X, Y, x2, y2

    Mein Ziel ist es nun effizient Ordnung in das Array zu bringen.
    Leider reichen meine C++-Kenntnisse dafür als Anfänger noch nicht aus.

    In dem rohen Datensatz kommen Kombinationen mehrfach vor.
    So kann es z.B. mehrere Male die Kombination von X und Y mit den entsprechenden Werten von x2 und y2 geben.

    Das darf am Ende nicht mehr sein.
    Jeder X,Y-Kombination muss genau ein x2, y2 Wertepaar zugeordnet werden sein.
    Die Wertepaare dürfen leider nicht interpoliert werden.

    Hierzu möchte ich, sofern ursprünglich mehrere Wertepaare vorhanden sind, das Wertepaar nehmen, dessen x2 und y2-Werte verglichen mit den anderen Wertepaaren derselben X,Y-Kombination am ehesten am Median liegen. Welches Paar genommen wird, wenn nur zwei Wertepaare vorhanden sind, ist egal.

    Anschließend sollen die nicht benötigten Wertepaare aus dem Vektor entfernt werden und der Vektor soll nach X und dann nach Y aufsteigend geordnet werden.

    Oder falls das einfacher ist, könnten die korrekten Daten auch in einen neuen Vektor überführt werden.

    Ich habe probiert mir das selbst mit googlen zu erarbeiten.
    Aber alleine schon wenn es um das Sortieren von Vektoren geht, steige ich da als Anfänger nicht mehr durch 😕

    Außerdem weiß ich nicht, wie man diese Datenaufbereitung so gestaltet, dass sie nicht Ewigkeiten beim Funktionsaufruf benötigt 😉

    Das hier ist mein derzeitiger Code mit einigen erfundenen Beispielwerten:

    #include <stdio.h>
    #include <iostream>
    #include <vector>
    using namespace std;
    
    struct Werte
    {
        int x, y, x2, y2;
    };
    
    vector <Werte> Rohdaten;
    
    int x[10]={2,2,1,3,1,2,1,3,4,2};
    int y[10]={2,2,3,1,1,3,3,1,3,2};
    int x2[10]={200,300,273,900,453,675,234,123,435,500};
    int y2[10]={324,534,346,666,323,676,345,234,566,234};
    
    int main(){
    
        int test;
    
        for (int i=0; i<10; i++)
        {
            Rohdaten.push_back({x[i],y[i],x2[i],y2[i]});
        }
    
        for (uint i=0; i<Rohdaten.size(); i++)
        {
        cout << Rohdaten[i].x << '\t' << Rohdaten[i].y << '\t' << Rohdaten[i].x2 << '\t' << Rohdaten[i].y2 << endl;
        }
    
        cin >> test;
        return 0;
    }
    

    So könnte die Zielmatrix aussehen:

    1	1	453	323
    1	3	234	345
    2	2	500	234
    3	1	123	234
    4	3	435	566
    

    Wie erreiche ich dieses Ziel?
    Ich bin dankbar für jedes kleines bisschen Hilfe 😉

    Vielen Dank 🙂



  • Britzi schrieb:

    Hierzu möchte ich, sofern ursprünglich mehrere Wertepaare vorhanden sind, das Wertepaar nehmen, dessen x2 und y2-Werte verglichen mit den anderen Wertepaaren derselben X,Y-Kombination am ehesten am Median liegen. Welches Paar genommen wird, wenn nur zwei Wertepaare vorhanden sind, ist egal.

    Median von was? Verglichen womit? Versteh ich nicht... 😕



  • Ich würde einen Vergleichoperator für Werte definieren (und die Klasse Werte in Messwert umbenennen). Dann kannst du std::sort auf den Vektor aufrufen und hast einen sortierte Liste.
    Dann musst du nur noch drübergehen und alle doppelten X,Y-Kombinationen aufarbeiten. (Ich würde alles in einen neuen Vektor kopieren, in-place ginge zwar auch, aber kopieren ist einfacher.) Bei gleichem X,Y merkst du dir Start und Ende und kopierst dann das Element in der Mitte.

    Hast du ein Buch, in dem du über Operatorüberladung und std::sort nachlesen kannst?



  • Danke euch beiden für die Hilfe.

    Das von closetomedian klingt super.

    Ich habe online ein Beispiel zur Nutzung von sort gefunden und jetzt mal probiert die Matrix in Abhängigkeit von x, dann y und x2 zu sortieren.

    Edit:
    Es scheint zu funktionieren.

    Ist diese Lösung so in Ordnung oder könnte man das noch optimieren?

    Das Kopieren könnte man dann einfach mit einer for-Schleife und if-Bedingung realisieren oder spricht da etwas dagegen?

    Danke 🙂

    Anbei der aktuelle Code:

    #include <stdio.h>
    #include <iostream>
    #include <vector>
    #include <algorithm> // Für sort
    using namespace std;
    
    struct Werte
    {
        int x, y, x2, y2;
    };
    
    vector <Werte> Messwerte;
    
    //bool sortByX(const Werte &lhs, const Werte &rhs) {return lhs.x < rhs.y;}
    
    bool sortByX(const Werte& a, const Werte& b)
    {
       if (a.x<b.x) return true;
       if (a.x>b.x) return false;
       if (a.y<b.y) return true;
       if (a.y>b.y) return false;
       if (a.x2<b.x2) return true;
       if (a.x2>b.x2) return false;
       return (a.y2<b.y2);
    }
    
    int x[10]={2,2,1,3,1,2,1,3,4,2};
    int y[10]={2,2,3,1,1,3,3,1,3,2};
    int x2[10]={200,300,273,900,453,675,234,123,435,500};
    int y2[10]={324,534,346,666,323,676,345,234,566,234};
    
    void ArrayAusgeben()
    {
        for (uint i=0; i<Messwerte.size(); i++)
        {
        cout << Messwerte[i].x << '\t' << Messwerte[i].y << '\t' << Messwerte[i].x2 << '\t' << Messwerte[i].y2 << endl;
        }
        cout <<"---"<<endl;
    }
    
    int main(){
    
        int test;
    
        for (int i=0; i<10; i++)
        {
            Messwerte.push_back({x[i],y[i],x2[i],y2[i]});
        }
    
        ArrayAusgeben();
    
        sort(Messwerte.begin(), Messwerte.end(), sortByX);
    
        ArrayAusgeben();
    
        cin >> test;
        return 0;
    }
    


  • So,

    ich nähere mich meinem Ziel.

    In der Funktion, die aus dem vorher sortierten Vektor die Elemente kopieren soll, die einmalig vorhanden sind sowie den mittleren Eintrag bei mehreren Einträgen mit derselben X,Y-Kombination ist noch irgendwas falsch.

    Es werden von der Funktion die richtigen Mitteleinträge von Einträgen mit derselben X,Y-Kombination ermittelt.
    Allerdings geht die Sortierung flöten und irgendwie werden einige Elemente kopiert, die nicht kopiert werden sollten.

    Ich sehe leider den Fehler überhaupt nicht.

    Es wäre schon, wenn ihr mal einen Blick auf die Funktion "AuswahlKopieren" werfen könntet 😉

    Es müssten aus der oberen Matrix jede Zeile, die eine X,Y-Kombination, die einmalig vorkommt, sowie bei den mehrfach vorhandenen Paaren die Vektorelemente 1, 4 und 7 in die unterste Matrix übernommen werden.

    Da kommt aber irgendwie Quatsch raus 😞

    1       1       453     323
    1       3       234     345
    1       3       273     346
    2       2       200     324
    2       2       300     534
    2       2       500     234
    2       3       675     676
    3       1       123     234
    3       1       900     666
    4       3       435     566
    ---
    1Mittelelement
    4Mittelelement
    7Mittelelement
    2       2       200     324
    2       2       300     534
    1       1       453     323
    1       3       234     345
    3       1       123     234
    2       2       500     234
    
    #include <stdio.h>
    #include <iostream>
    #include <vector>
    #include <algorithm> // Für sort
    using namespace std;
    
    struct Werte
    {
        int x, y, x2, y2;
    };
    
    vector <Werte> Messwerte;
    vector <Werte> SortierteWerte;
    
    bool sortByXyX2(const Werte& a, const Werte& b)
    {
       if (a.x<b.x) return true;
       if (a.x>b.x) return false;
       if (a.y<b.y) return true;
       if (a.y>b.y) return false;
       if (a.x2<b.x2) return true;
       if (a.x2>b.x2) return false;
       return (a.y2<b.y2);
    }
    
    int x[10]={2,2,1,3,1,2,1,3,4,2};
    int y[10]={2,2,3,1,1,3,3,1,3,2};
    int x2[10]={200,300,273,900,453,675,234,123,435,500};
    int y2[10]={324,534,346,666,323,676,345,234,566,234};
    
    void ArrayAusgeben(vector <Werte> Array)
    {
        for (uint i=0; i<Array.size(); i++)
        {
        cout << Array[i].x << '\t' << Array[i].y << '\t' << Array[i].x2 << '\t' << Array[i].y2 << endl;
        }
        cout <<"---"<<endl;
    }
    
    void AuswahlKopieren() //Die kopierten Elemente stimmen nicht und die Sortierung verschwindet.
    {   double start=0, ende=0 , mitte=0;
        int mittelelement=0;
    
        for (int i=0; i<Messwerte.size(); i++)
        {
            if (Messwerte[i].x == Messwerte[i+1].x && Messwerte[i].y == Messwerte[i+1].y)
            {
                start=i;
                ende=i;
                while(Messwerte[i].x == Messwerte[i+1].x && Messwerte[i].y == Messwerte[i+1].y)
                {
                    i++;
                    ende++;
                }
    
                mitte=(ende-start)/2;
                mittelelement=((double)start+mitte);
                cout << mittelelement << "Mittelelement"<< endl;
                SortierteWerte.push_back({x[mittelelement],y[mittelelement],x2[mittelelement],y2[mittelelement]});
                start=0; ende=0; mitte=0; mittelelement=0;
            }
            else
            {SortierteWerte.push_back({x[i],y[i],x2[i],y2[i]});}
        }
    }
    
    int main(){
    
        int test;
    
        for (int i=0; i<10; i++)
        {
            Messwerte.push_back({x[i],y[i],x2[i],y2[i]});
        }
    
        ArrayAusgeben(Messwerte);
    
        sort(Messwerte.begin(), Messwerte.end(), sortByXyX2);
    
        ArrayAusgeben(Messwerte);
    
        AuswahlKopieren();
    
        ArrayAusgeben(SortierteWerte);
    
        cin >> test;
        return 0;
    }
    

    Vielen Dank 🙂



  • Aha - also werden x2 und y2 auch irgendwann sortiert und da geht's dann um den Median. Hättest Du ja mal schreiben können...

    Eine schöne Aufgabe um sich mit <algorithm> rumzuschlagen.

    Britzi schrieb:

    void AuswahlKopieren() //Die kopierten Elemente stimmen nicht und die Sortierung verschwindet.
    {   double start=0, ende=0 , mitte=0;
        int mittelelement=0;
    
        for (int i=0; i<Messwerte.size(); i++)
        {
            if (Messwerte[i].x == Messwerte[i+1].x && Messwerte[i].y == Messwerte[i+1].y)
            {
                start=i;
                ende=i;
                while(Messwerte[i].x == Messwerte[i+1].x && Messwerte[i].y == Messwerte[i+1].y)
                {
                    i++;
                    ende++;
                }
    
                mitte=(ende-start)/2;
                mittelelement=((double)start+mitte);
                cout << mittelelement << "Mittelelement"<< endl;
                SortierteWerte.push_back({x[mittelelement],y[mittelelement],x2[mittelelement],y2[mittelelement]});
                start=0; ende=0; mitte=0; mittelelement=0;
            }
            else
            {SortierteWerte.push_back({x[i],y[i],x2[i],y2[i]});}
        }
    }
    

    Wo kommen denn da auf einmal doubles her? Und warum?
    Ist i+1 (Z.7) immer im vector? Schau Dir std::vector::at() an (und bau es ein und lass Dein Programm laufen.)

    Mir faellt gerade nix pädagogisch sinnvolles ein...deswegen mal meine Version mit ein paar Dingen, die evtl. interessant für Dich sind.

    #include <iostream>
    #include <vector>
    #include <algorithm>
    
    struct messwert{
      int x,y,x2,y2;
    };
    
    // ganz klassischer Ausgabeoperator - steht in jedem Buch
    std::ostream& operator<<(std::ostream& out, const messwert& m){
      return out << m.x << '\t' << m.y << '\t' << m.x2 << '\t' << m.y2;
    }
    
    // lexikographischer Vergleich.
    // Nur x und y werden verglichen
    bool messwert_cmp(const messwert& a, const messwert& b){
      return a.x<b.x || (!(b.x<a.x) && a.y<b.y);
    }
    
    using messreihe = std::vector<messwert>;
    
    // ein paar Messdaten
    messreihe dummy_create(){
      int x[10]={2,2,1,3,1,2,1,3,4,2};
      int y[10]={2,2,3,1,1,3,3,1,3,2};
      int x2[10]={200,300,273,900,453,675,234,123,435,500};
      int y2[10]={324,534,346,666,323,676,345,234,566,234};
    
      int n = sizeof(x)/sizeof(x[0]);
      messreihe result;
      result.reserve(n);
      for(int i=0; i<n; ++i)
        result.emplace_back(messwert{x[i],y[i],x2[i],y2[i]});
      return result;	   
    }
    
    // s.o.
    std::ostream& operator<<(std::ostream& out, const messreihe& r){
      for(const auto& m : r)
        out << m << '\n';
      return out << "---";
    }
    
    // die Arbeit!
    // r ist sortiert nach x und y
    void bereinigen(messreihe& r){
      using namespace std;
      // wo fangen wir an, wo hoeren wir auf, wohin schreiben wir?
      auto first = begin(r), last = end(r), dest = begin(r);
      while(first!=last){
        // wir bestimmen Anfang und Ende des Bereichs mit
        // diesem Wert. x2 und y2 sind noch egal.
        auto value = messwert{first->x, first->y, 0, 0};
        auto er = equal_range(first, last, value, messwert_cmp);
        auto size = distance(er.first, er.second);
        // Wenn der Bereich nur 1 oder 2 Elemente hat:
        // nimm das erste und kopiere es nach dest
        if (size<3)
          {
    		*dest = *first;
          }
        else
          {
    		// Nach x2 und y2 sortieren.
    		// Aber nur soweit wie nötig, um das mittlere Element zu
    		// erhalten.
    		// http://en.cppreference.com/w/cpp/algorithm/nth_element
    		// Das mittlere Element dann kopieren.
    		nth_element(er.first, er.first+size/2, er.second,
    		    [](const messwert&a, const messwert&b){
    		      return a.x2<b.x2 || (!(b.x2<a.x2)&&a.y2<b.y2); });
    		*dest = *next(er.first, size/2);
          }
        ++dest;
        first = er.second;
      }
      // Den Muell rausbringen nicht vergessen...
      r.erase(dest, last);
    }
    
    int main(){
      auto r = dummy_create();
      std::cout << r << '\n';
      std::sort(begin(r), end(r), messwert_cmp);
      std::cout << r << '\n';
      bereinigen(r);
      std::cout << r << '\n';
    }
    


  • Wow...

    Furble Wurble,
    ich bin sprachlos 🙂

    Dein Code ist zum Lernen absolut super.
    Mein ganzer Code ist ja absoluter Müll im Vergleich.

    Du hast Recht, ich laufe mit i+1 irgendwann aus dem Vector raus. 😞
    Die Doubles mit dem Cast habe ich eingefügt, damit bei der Integerdivision gerundet wird, also damit aus z.B. 3/2 nicht 1, sondern 2 wird.

    Ich habe schon ganz viel zu deinem Code nachgeschlagen und bin auch noch immer dabei ihn Stück für Stück nachzuvollziehen.

    Leider ist dein Code nicht lauffähig und ich bekomme die Fehler mit meinem Laienwissen nicht behoben 😞

    Ich bekomme ganz viele Fehlermeldungen, aber ursächlich ist vermutlich nur diese Zeile:

    using messreihe = std::vector<messwert>;
    // Fehler: expexted nested-name-specifier before 'messreihe', 'messreihe' hast not been declared; uvm.
    

    Schon mal ein paar kleine Fragen zu dem Code:

    int n = sizeof(x)/sizeof(x[0]);
    

    Wieso teilst du hier und nimmst nicht nur sizeof(x)? Schließlich ist sizeof(x[0]) doch immer eins oder nicht?
    Und wieso reservierst du überhaupt Speicher für den Vector anstatt ihn per PushBack einfach kontinuierlich zu befüllen? Hast du so einen Performancegewinn?
    Das ist für mich als Laien leider nicht ersichtlich.

    Zu den Ausgabestreams habe ich bisher online keine Erklärung gefunden.
    Damit gibst du nur ein "Format" vor, wie bestimmte Daten auszugeben sind und diese werden dann, wenn der Stream ausgegeben werden soll in dem Format für den ganzen Datensatz ausgegeben, oder?

    Vielen vielen Dank 🙂



  • Naja...wenn er nicht läuft kann der Code ja so toll auch nicht sein...

    Britzi schrieb:

    Leider ist dein Code nicht lauffähig und ich bekomme die Fehler mit meinem Laienwissen nicht behoben 😞

    Ich bekomme ganz viele Fehlermeldungen, aber ursächlich ist vermutlich nur diese Zeile:

    using messreihe = std::vector<messwert>;
    // Fehler: expexted nested-name-specifier before 'messreihe', 'messreihe' hast not been declared; uvm.
    

    Womit kompilierst Du?

    Vielleicht hilft es die Zeile zu ersetzen:

    typedef std::vector<messwert> messreihe;
    

    Britzi schrieb:

    Schon mal ein paar kleine Fragen zu dem Code:

    int n = sizeof(x)/sizeof(x[0]);
    

    Wieso teilst du hier und nimmst nicht nur sizeof(x)? Schließlich ist sizeof(x[0]) doch immer eins oder nicht?

    Ist das so? Hast Du es mal probiert? http://en.cppreference.com/w/cpp/language/sizeof

    Britzi schrieb:

    Und wieso reservierst du überhaupt Speicher für den Vector anstatt ihn per PushBack einfach kontinuierlich zu befüllen? Hast du so einen Performancegewinn?

    Ja. Genau. Wenn ich doch vorher schon weiss, wieviel Speicher ich brauche, kann ich mir das auch zu nutze machen.

    Britzi schrieb:

    Zu den Ausgabestreams habe ich bisher online keine Erklärung gefunden.
    Damit gibst du nur ein "Format" vor, wie bestimmte Daten auszugeben sind und diese werden dann, wenn der Stream ausgegeben werden soll in dem Format für den ganzen Datensatz ausgegeben, oder?

    ähm...ja...ich glaube, Du meinst das richtige.

    Erst sage ich, dass ein Messwert so-und-so ausgegeben wird.
    Und dann sage ich: wenn ich eine Messreihe ausgebe, gebe ich jeden Messwert gefolgt von einem Zeilenumbruch aus.
    Und wenn ich dafür den operator<<() überlade, kann ich das ganz bequem nutzen.
    Online würde ich nach "input output c++ own type" oder so suchen. Besser wäre ein C++-Buch.



  • Furble Wurble schrieb:

    Naja...wenn er nicht läuft kann der Code ja so toll auch nicht sein...

    Vielleicht hilft es die Zeile zu ersetzen:

    typedef std::vector<messwert> messreihe;
    

    Im Ernst, ich bin total begeistert von deinem Code 🙂
    Er ist für mich total lehrreich, auch wenn ich leider noch nicht alles verstehe.
    Und ich bin ebenfalls total begeistert davon, wass es für tolle Funktionen gibt.

    Z.B. diese nth_element Funktion, ich hätte im Leben nie gedacht, dass sowas exisiert.

    Die Zeile zu ersetzen hat übrigens geholfen!
    Ich arbeite mit Qt 5.2.1 (GCC 4.6.1, 64 bit) unter Ubuntu.

    Britzi schrieb:

    Schon mal ein paar kleine Fragen zu dem Code:

    int n = sizeof(x)/sizeof(x[0]);
    

    Wieso teilst du hier und nimmst nicht nur sizeof(x)? Schließlich ist sizeof(x[0]) doch immer eins oder nicht?

    Ist das so? Hast Du es mal probiert? http://en.cppreference.com/w/cpp/language/sizeof

    Ich habs ausprobiert und habe begriffen, dass hier die Speichergröße der 10 int von 40 durch die Größe eines int geteilt wird, was dann den 10 Elementen enspricht. 🙂

    Das mit der Operatorüberladung habe ich auch nachgelesen.

    Die Hauptfunktion "bereinigen" erschließt sich leider bisher nur so halb.

    Ich schreibe mal neben die Zeilen, was ich glaube verstanden zu haben sowie einige offene Fragen:

    void bereinigen(messreihe& r){ //Die Funktion bereinigen wird mit dem sortieren Vektor 'R' aufgerufen und arbeitet inPlace
      using namespace std;
      auto first = begin(r), last = end(r), dest = begin(r); // first zeigt auf das nullte Element in r, last auf das letzte und dest erstmal auch auf das erste.
      while(first!=last){ //Läuft solange das Element in first nicht dem letzten Element des Vektors entspricht.
    
        auto value = messwert{first->x, first->y, 0, 0};           //Referenzen auf die ints x und y an der Position des first entsprechenden Vektorelements???
        auto er = equal_range(first, last, value, messwert_cmp);   //Gibt die erste und zweite Grenzposition zurück, wo ein Bereich mit denselben Werten endet.
        auto size = distance(er.first, er.second);                 //Errechnet die Länge dieses Bereiches und damit die Anzahl der in dem Bereich befindlichen Elemente
    
        if (size<3) //Wenn der Bereich 1 oder 2 Elemente besitzt, kopiere das erste nach dest.
          {
            *dest = *first; //Kopieren mit Pointern = mehr Performance
          }
        else
          {
            nth_element(er.first, er.first+size/2, er.second,  //Bei Sortierung in der Mitte stehendes Element einzeln in dem Bereichs von first bis second in die Mitte bringen
                [](const messwert&a, const messwert&b){
                  return a.x2<b.x2 || (!(b.x2<a.x2)&&a.y2<b.y2); }); //Wieso steht hier eigentlich nach dem Oder die Bedingung (!(b.x2<a.x2)? 
                                                                     //Es geht hier darum, dass wenn x2 denselben Wert hat, dass dann nach y2 sortiert wird, oder?
                                                                     //Wenn ja, wieso schreibt man nicht b.x2==a.x2?
            *dest = *next(er.first, size/2); // Mittleres Element kopieren. Wieso wird erst das Element in die Mitte gebracht, dann sortiert und dann das Mittlere kopiert? 
    \\Dann ist das gewünschte Element doch gar nicht mehr in der Mitte, oder?
          }
        ++dest; //dest wird incrementiert, weil die im Element dest befindlichen Werte behalten werden sollen.
        first = er.second; //Für neue Runde, fängt beim zweiten Bereich an.
      }
    
      r.erase(dest, last); //Elemente von dest bis last aus dem Vektor löschen.
    }
    
    //Alle Zeilen die mit einer XY-Kombination einmalig vorkommen werden nicht angetastet, da sie keinen Bereich darstellen.
    

    Es wäre schön, wenn ich da bei den Verständnisproblemen noch ein bisschen Nachhilfe bekäme 😉

    Ich muss sagen es macht übrigens richtig Spaß diese ganzen Sachen nachzuschlagen und probieren zu verstehen, wie ein Profi sowas programmiert 🙂



  • Britzi schrieb:

    Die Hauptfunktion "bereinigen" erschließt sich leider bisher nur so halb.

    Ich schreibe mal neben die Zeilen, was ich glaube verstanden zu haben sowie einige offene Fragen:

    void bereinigen(messreihe& r){ //Die Funktion bereinigen wird mit dem sortieren Vektor 'R' aufgerufen und arbeitet inPlace
      using namespace std;
      auto first = begin(r), last = end(r), dest = begin(r); // first zeigt auf das nullte Element in r, last auf das letzte und dest erstmal auch auf das erste.
      while(first!=last){ //Läuft solange das Element in first nicht dem letzten Element des Vektors entspricht.
       
        auto value = messwert{first->x, first->y, 0, 0};           //Referenzen auf die ints x und y an der Position des first entsprechenden Vektorelements???
        auto er = equal_range(first, last, value, messwert_cmp);   //Gibt die erste und zweite Grenzposition zurück, wo ein Bereich mit denselben Werten endet.
        auto size = distance(er.first, er.second);                 //Errechnet die Länge dieses Bereiches und damit die Anzahl der in dem Bereich befindlichen Elemente
        
        if (size<3) //Wenn der Bereich 1 oder 2 Elemente besitzt, kopiere das erste nach dest.
          {
            *dest = *first; //Kopieren mit Pointern = mehr Performance
          }
        else
          {
            nth_element(er.first, er.first+size/2, er.second,  //Bei Sortierung in der Mitte stehendes Element einzeln in dem Bereichs von first bis second in die Mitte bringen
                [](const messwert&a, const messwert&b){
                  return a.x2<b.x2 || (!(b.x2<a.x2)&&a.y2<b.y2); }); //Wieso steht hier eigentlich nach dem Oder die Bedingung (!(b.x2<a.x2)? 
                                                                     //Es geht hier darum, dass wenn x2 denselben Wert hat, dass dann nach y2 sortiert wird, oder?
                                                                     //Wenn ja, wieso schreibt man nicht b.x2==a.x2?
            *dest = *next(er.first, size/2); // Mittleres Element kopieren. Wieso wird erst das Element in die Mitte gebracht, dann sortiert und dann das Mittlere kopiert? 
    \\Dann ist das gewünschte Element doch gar nicht mehr in der Mitte, oder?
          }
        ++dest; //dest wird incrementiert, weil die im Element dest befindlichen Werte behalten werden sollen.
        first = er.second; //Für neue Runde, fängt beim zweiten Bereich an.
      }
      
      r.erase(dest, last); //Elemente von dest bis last aus dem Vektor löschen.
    }
    
    //Alle Zeilen die mit einer XY-Kombination einmalig vorkommen werden nicht angetastet, da sie keinen Bereich darstellen.
    

    Z.6:
    Das hat nix mit Referenzen zu tun.
    first ist ein Iterator - verhält sich also weitestgehend wie ein messwert* (Zeiger auf messwert).
    Ich erstelle eine Variable (value) vom Typ messwert . Die brauche ich einzig um sie equal_range() zu übergeben.
    "Gleichheit" hängt erstmal nur von x und y ab, weil messwert_cmp() nur diese beiden vergleicht. Entsprechend initialisiere ich nur x und y von value .
    x2 und y2 sind beliebig - 0 war nur der erste Wert der mir einfiel.

    Z.12: wieder: first ist ein Iterator. dest auch. Das ist eine ganz schnöde Kopie/Zuweisung. Nur via zwei derefenzierte Iteratoren.

    Z.16/21: Der Witz von nth_element() ist, dass nur soweit wie nötig sortiert wird.
    Wenn ich den Median von 9 8 7 6 5 4 3 2 1 haben will, kann der Algorithmus aufhören, wenn da steht: ? ? ? ? 5 ? ? ? ?
    Die Reihenfolge der übrigen Zahlen ist egal. Hauptsache die 5 steht genau da!

    Z.18: "Old habits die hard.". Aus obskuren Gründen - die beim vergleich von int eh keine Rolle spielen - benutze ich '<' wo immer möglich.

    Britzi schrieb:

    Ich muss sagen es macht übrigens richtig Spaß diese ganzen Sachen nachzuschlagen und probieren zu verstehen, wie ein Profi sowas programmiert 🙂

    Ahhh.
    Das geht natürlich runter wie Butter.
    Alle paar Wochen schlägt hier mal jemand auf, der genügend Interesse und Reife mitbringt, das so zu handhaben.
    Dann lohnt es sich auch für mich, hier Zeit zu investieren.

    (*): nth_element() macht auch keine Aussage über die Reihenfolge links und rechts des nten Elements.
    Wie könnte dann eine allgemeine median() Funktion aussehen?

    #include <algorithm>
    #include <iostream>
    #include <iterator> // begin, end
    
    double median(int*first, int*last)
    {
      // code code code
    }
    
    int main(){
      using namespace std;
      int rg1[] = { 1,2,3,4,5,6,7,8,9 };
      auto d1 = median(begin(rg1), end(rg1));
      std::cout << d1 << '\n'; // 5
    
      int rg2[] = { 0,1,2,3,4,5,6,7,8,9 };
      auto d2 = median(begin(rg2), end(rg2));
      std::cout << d2 << '\n'; // 4,5
    }
    


  • Furble Wurble schrieb:

    (*): nth_element() macht auch keine Aussage über die Reihenfolge links und rechts des nten Elements.
    Wie könnte dann eine allgemeine median() Funktion aussehen?

    #include <algorithm>
    #include <iostream>
    #include <iterator> // begin, end
    
    double median(int*first, int*last)
    {
      // code code code
    }
    
    int main(){
      using namespace std;
      int rg1[] = { 1,2,3,4,5,6,7,8,9 };
      auto d1 = median(begin(rg1), end(rg1));
      std::cout << d1 << '\n'; // 5
    
      int rg2[] = { 0,1,2,3,4,5,6,7,8,9 };
      auto d2 = median(begin(rg2), end(rg2));
      std::cout << d2 << '\n'; // 4,5
    }
    

    Oha: wichtig vergessen. nth_element() sagt zwar nix über die Reihenfolge, aber es sichert folgendes zu:
    Links vom nten Element stehen alle Werte, die nicht größer sind als das nte Element. Rechts vom nten Element der Rest.



  • So, ich habe meine Hausaufgaben gemacht, allerdings nicht so ganz, wie vorgesehen.

    Ich hoffe meine Lösung für eine allgemeine Funktion zur Medianberechnung ist trotzdem in Ordnung. 😉

    Wie sieht denn die Musterlösung aus?

    Furble Wurble schrieb:

    nth_element() sagt zwar nix über die Reihenfolge, aber es sichert folgendes zu:
    Links vom nten Element stehen alle Werte, die nicht größer sind als das nte Element. Rechts vom nten Element der Rest.

    Das bedeutet aber nicht, dass die Elemente bis zum mittleren Element sortiert sind, oder?

    Ich wusste nicht, wie ich mit den übergebenen "Werten" *first und *last umgehen soll. Es hat irgendwie immer nur Fehler gegeben und darum habe ich dann eine andere Lösung umgesetzt:

    #include <algorithm>
    #include <iostream>
    #include <iterator> // begin, end
    #include <vector>
    
    bool sortAufst(const int& a, const int& b)
    {return a<b;}
    
    void Median(std::vector<int> vec)
    {
        if(vec.size()%2!=0)
        {
            std::nth_element(vec.begin(), vec.begin() + vec.size()/2, vec.end());
            std::cout << "Der Median ist " << vec[vec.size()/2] << '\n';
        }
        else
        {   std::sort(vec.begin(),vec.end(),sortAufst); //Das es allgemein sein soll und nth_element nicht sortiert, muss in diesem Fall sortiert werden.
                                                        //Sonst könnte das Element (vec.size()/2)-1 irgend eins sein, was in der Reihenfolge geordnet da nicht stehen würde.
            std::nth_element(vec.begin(), vec.begin() + vec.size()/2, vec.end());
            std::cout << "Der Median beträgt " << vec[(vec.size()/2)-1]<< " und " << vec[vec.size()/2]<< '\n'; 
        }
    }
    
    int main(){
      using namespace std;
    
      std::vector<int> rg1{ 1,2,3,4,5,6,7,8,9 };
    
      std::vector<int> rg2{ 0,1,2,3,4,5,6,7,8,9 };
    
      Median(rg1);
      Median(rg2);
    }
    

    Nochmal zum vorherigen Code.
    Ich habe verstanden, wie alles funktioniert und könnte im Prinzip ein Ablaufdiagramm zeichnen. Aber wie genau die ganzen Argumente und vor Allem von welchen Typen übergeben werden, das muss ich echt in Ruhe nochmal aufarbeiten.

    Man sieht ja an der "Hausaufgabe", dass ich mit den übergebenen Paramentern einfach nichts anzufangen wusste und es auch nicht rausgekriegt habe, wie ich sie nutzen soll 😕

    Iteratoren habe ich in meinem C++ nachgeschlagen.
    Die werden auf Seite 805 einseitig beschrieben ^^
    Ich habe verstanden was sie tun, aber nicht so wirklich, wie sie angewendet werden.
    Bis auf Seite 805 bin ich auch mit dem regulären Lesen noch nicht vorgedrungen.

    Mit der bisherigen Datenverarbeitung ist mein Ziel noch nicht erreicht.
    Ich mags kaum schreiben, weil ich hier schon so viel Hilfe bekommen habe, aber ich machs einfach mal.

    Der nun sortierte Vektor, in dem jede XY-Kombination nur einmal vorkommt wird von mir in einen zweidimensionalen Vektor kopiert. Dabei ist x die eine Dimension und y die zweite. Jetzt habe ich ein Schachbrett und in jedem Feld entsprechend einer XY-Kombination stehen die beiden dazugehörigen Werte von x2 und y2. Das Schachbrett beginnt mit dem Element 0,0.

    Nun habe ich das Problem, dass es in dem Schachbrett Fehlstellen gibt und diese möchte ich gerne auffüllen. Dazu initialisere ich erstmal das ganze Schachbrett vor dem Befüllen mit den Daten aus dem sortierten Vektor mit -1, um die Fehlstellen später einfach auffinden zu können.

    Jetzt nutze ich for-Schleifen und gehe nun von links nach rechts und von oben nch unten durch das ganze Schachbrett. Wenn ich dort eine -1 finde, möchte ich schauen, ob das rechte Element neben der Fehlstelle !=-1 ist und wenn ja, kopiere ich die Werte von diesem Element. Wenn da auch eine -1 ist, schaue ich unterhalb, oberhalb und in den schräg darüber- und darunterliegenden Plätzen nach, ob da Wertepaare sind. Wenn nicht, kopiere ich notfalls das Elemtent von links, auf dem ich vor der Fehlstelle war. So möchte ich verhindern, dass sich eventuell ganze Reihen einseitig von links auffüllen, obwohl andere Elemente näher dran gewesen wären.

    Leider ist meine Lösung mal wieder Käse.
    Sie funktioniert nicht an den Rändern, weil sie sonst aus dem Brett läuft. Das könnte man auch mit If-Bedingungen abfangen, aber das wird ja ein riesieges Knäul aus Bedingungen.

    Hier ist der bisherige Code mit meinem Zusatz:
    (Einmal oben ein Strukt und der neue Vektor, der Rest ist unten)

    Wie könnte man hier geschickt vorgehen?

    #include <iostream>
    #include <vector>
    #include <algorithm>
    
    int xdim=6;
    int ydim=4;
    
    struct wertepaar
    {
        int xp, yp;
    };
    
    std::vector <std::vector<wertepaar> > Wertetabelle (xdim, std::vector<wertepaar>(ydim)); // Später ca. 1000 x 1000
    
    //------------------------------------------------------
    
    struct messwert{
      int x,y,x2,y2;
    };
    
    std::ostream& operator<<(std::ostream& out, const messwert& m){
      return out << m.x << '\t' << m.y << '\t' << m.x2 << '\t' << m.y2;
    }
    
    // lexikographischer Vergleich.
    // Nur x und y werden verglichen
    bool messwert_cmp(const messwert& a, const messwert& b){
      return a.x<b.x || (!(b.x<a.x) && a.y<b.y); 
    }
    
    typedef std::vector<messwert> messreihe;
    
    // ein paar Messdaten
    messreihe dummy_create(){  //Messreihetestdatensatz erzeugen und zurückgeben!
      int x[10]={2,2,1,3,1,2,1,3,4,2};
      int y[10]={2,2,3,1,1,3,3,1,3,2};
      int x2[10]={200,300,273,900,453,675,234,123,435,500};
      int y2[10]={324,534,346,666,323,676,345,234,566,234};
    
      int n = sizeof(x)/sizeof(x[0]); //Muss so sein! Ist hier bei 10 Elementen 40/4=10, weil ein Integer die Größe 4 besitzt.
      std::cout <<sizeof(x)<<'\t'<< sizeof(x[0])<< '\t' << sizeof(int)<<std::endl;
      messreihe result;
      result.reserve(n); //Speicherplatz aus Performancegründen vorher reservieren
      for(int i=0; i<n; ++i) //Vector result mit Elementen füllen.
        result.emplace_back(messwert{x[i],y[i],x2[i],y2[i]}); //Emplace ist besser als PushBack, weil inPalace ohne Copy = höhere Performance
      return result;
    }
    
    // Überladener Ausgabeoperatru für den Vector r
    std::ostream& operator<<(std::ostream& out, const messreihe& r){ 
      for(const auto& m : r)
        out << m << '\n';
      return out << "---";
    }
    
    // die Arbeit!
    // r ist sortiert nach x und y
    void bereinigen(messreihe& r){
      using namespace std;
      // wo fangen wir an, wo hoeren wir auf, wohin schreiben wir?
      auto first = begin(r), last = end(r), dest = begin(r);
      while(first!=last){
        // wir bestimmen Anfang und Ende des Bereichs mit
        // diesem Wert. x2 und y2 sind noch egal.
        auto value = messwert{first->x, first->y, 0, 0};            
        auto er = equal_range(first, last, value, messwert_cmp);   
        auto size = distance(er.first, er.second); 
        // Wenn der Bereich nur 1 oder 2 Elemente hat:
        // nimm das erste und kopiere es nach dest
        if (size<3)
          {
            *dest = *first; 
          }
        else
          {
            // Nach x2 und y2 sortieren.
            // Aber nur soweit wie nötig, um das mittlere Element zu
            // erhalten.
            // http://en.cppreference.com/w/cpp/algorithm/nth_element
            // Das mittlere Element dann kopieren.
            nth_element(er.first, er.first+size/2, er.second,  
                [](const messwert&a, const messwert&b){
                  return a.x2<b.x2 || (!(b.x2<a.x2)&&a.y2<b.y2); });
            *dest = *next(er.first, size/2);
          }
        ++dest;
        first = er.second;
      }
      // Den Muell rausbringen nicht vergessen...
      r.erase(dest, last);
    }
    
    int main(){
      auto r = dummy_create();
      std::cout << r << '\n';
      std::sort(begin(r), end(r), messwert_cmp);
      std::cout << r << '\n';
      bereinigen(r);
      std::cout << r << '\n';
    
    //-----------------------------------------------------------------
    //Wertetabelle mit -1 initialisiren
      for (int iy=0; iy<ydim; iy++)
      {
          for (int ix=0; ix<xdim; ix++)
             {Wertetabelle[ix][iy]={-1,-1};}
      }
    
    //------------------------------------------------------------------
    //Daten aus aufgeräumtem Vektor r in die Wertetabelle kopieren
      for (int i=0; i<xdim; i++)
      {
          if(r[i].x>=0 && r[i].x<=xdim && r[i].y>=0 && r[i].y<=ydim )
             {Wertetabelle[r[i].x][r[i].y]={r[i].x2,r[i].y2};}
      }
    
    //------------------------------------------------------------------
    // Fehlstellen beseitigen
    
      int fehlstellen=0;
    
      for (int iy=0; iy<ydim-1; iy++)
      {
          for (int ix=0; ix<xdim-1; ix++)
          {
              if(Wertetabelle[ix][iy].xp == -1) //Reicht, da negative Werte naturell nicht vorkommen können
              {
                   if (Wertetabelle[ix+1][iy].xp != -1)
                   {
                      Wertetabelle[ix][iy].xp = Wertetabelle[ix+1][iy].xp;
                      Wertetabelle[ix][iy].yp = Wertetabelle[ix+1][iy].yp;
                      fehlstellen++;
                      continue;
                   }
    
                   else if (Wertetabelle[ix][iy+1].xp != -1)
                   {
                      Wertetabelle[ix][iy].xp = Wertetabelle[ix][iy+1].xp;
                      Wertetabelle[ix][iy].yp = Wertetabelle[ix][iy+1].yp;
                      fehlstellen++;
                      continue;
                   }
    
                   else if (Wertetabelle[ix][iy-1].xp != -1)
                   {
                      Wertetabelle[ix][iy].xp = Wertetabelle[ix][iy-1].xp;
                      Wertetabelle[ix][iy].yp = Wertetabelle[ix][iy-1].yp;
                      fehlstellen++;
                      continue;
                   }
    
                   else if (Wertetabelle[ix+1][iy-1].xp != -1)
                   {
                      Wertetabelle[ix][iy].xp = Wertetabelle[ix+1][iy-1].xp;
                      Wertetabelle[ix][iy].yp = Wertetabelle[ix+1][iy-1].yp;
                      fehlstellen++;
                      continue;
                   }
    
                   else if (Wertetabelle[ix-1][iy-1].xp != -1)
                   {
                      Wertetabelle[ix][iy].xp = Wertetabelle[ix-1][iy-1].xp;
                      Wertetabelle[ix][iy].yp = Wertetabelle[ix-1][iy-1].yp;
                      fehlstellen++;
                      continue;
                   }
    
                   else if (Wertetabelle[ix+1][iy+1].xp != -1)
                   {
                      Wertetabelle[ix][iy].xp = Wertetabelle[ix+1][iy+1].xp;
                      Wertetabelle[ix][iy].yp = Wertetabelle[ix+1][iy+1].yp;
                      fehlstellen++;
                      continue;
                   }
    
                   else if (Wertetabelle[ix-1][iy+1].xp != -1)
                   {
                      Wertetabelle[ix][iy].xp = Wertetabelle[ix-1][iy+1].xp;
                      Wertetabelle[ix][iy].yp = Wertetabelle[ix-1][iy+1].yp;
                      fehlstellen++;
                      continue;
                   }
    
                   if (Wertetabelle[ix-1][iy].xp != -1)
                   {
                      Wertetabelle[ix][iy].xp = Wertetabelle[ix-1][iy].xp;
                      Wertetabelle[ix][iy].yp = Wertetabelle[ix-1][iy].yp;
                      fehlstellen++;
                      continue;
                   }
              }
    
          }
    
      }
    
    std::cout << "Es wurden " << fehlstellen << " Fehlstellen ersetzt!" <<std::endl;
    
     //----------------------------------------------------------------
     //Ausgabe
      for (int iy=0; iy<ydim; iy++)
      {
          for (int ix=0; ix<xdim; ix++)
          {
            std::cout << "|" << Wertetabelle[ix][iy].xp << ':' << Wertetabelle[ix][iy].yp << "|";
          }
          std::cout<<std::endl;
      }
    
    }
    

    Vielen Dank nochmal für die super Hilfe! 🙂
    Ich lerne hier echt viel, muss aber auch gestehen, dass es für einen Anfänger z.T. viel auf einmal ist. Da ist noch Nacharbeit meinerseits notwendig 🙂



  • Britzi schrieb:

    Man sieht ja an der "Hausaufgabe", dass ich mit den übergebenen Paramentern einfach nichts anzufangen wusste und es auch nicht rausgekriegt habe, wie ich sie nutzen soll 😕

    Iteratoren habe ich in meinem C++ nachgeschlagen.
    Die werden auf Seite 805 einseitig beschrieben ^^
    Ich habe verstanden was sie tun, aber nicht so wirklich, wie sie angewendet werden.

    Ich hab' vorgeschlagen zwei Zeiger zu verwenden - die sind quasi die "Ur-Iteratoren" - und lassen sich auch mit den std Algorithmen zu verwenden.
    Daher hatte ich an irgendwie sowas gedacht:

    #include <cassert>
    
    double median(int *first, int *last)
    {
      using namespace std;
      assert(first!=last);
    
      // "mittleres" Element hinsortieren
      const auto N = distance(first, last);
      auto x = next(first, N/2);
      nth_element(first, x, last);
    
      // reicht schon, wenn N ungerade ist
      if(N%2==1) return *x;
    
      // sonst auch noch den Vorgänger hinsortieren
      // als "zweites mittleres Element" :)
      auto x2 = prev(x);
      nth_element(first, x2, x);
    
      return (*x+*x2)/2.0;
    }
    

    Dein eigentliches Anliegen ist ein schon ein dickeres Brett...

    Das mit den Rändern ist aber eigentlich kein (großes) Problem. Warum glaubst Du, dass das ein Knäuel gibt?



  • Ok, vielen Dank 🙂

    Du bist wirklich eine große Hilfe!

    Die Musterlösung studiere ich mal in Ruhe.
    Pointer... ja, das dazugehörige Buchkapitel muss ich nochmal durcharbeiten.

    Zu dem Brett:
    Das ist also ok, dass einfach mit for-Schleifen durchzuackern und sämtliche If-Bedingungen aufzustellen?

    Das mache ich nachher einfach mal auch für die Ränder.

    Dick in Bezug auf die Anzahl der Elemente?
    Das ist aber noch händelbar, oder?

    Es geht darum, dass ich dieses Brett so weit aufbereite, dass es keine Fehlstellen mehr hat.

    Dann schiebe ich es in eine Textdatei, aus der das gute Brett bei Softwarestart wieder in den zweidimensionalen Vektor eingelesen wird, um auf die Werte zugreifen zu können.



  • Ich habe nun alle If-Bedingungen eingefügt und einige kleinere Fehler beseitigt.

    Es funktioniert alles einwandfrei!

    Vielen Dank nochmals für die tolle Hilfe 🙂

    Ich habe viel lernen können und noch viel aufzuarbeiten.


Log in to reply