Werte-Tabellen vergleichen und zusammenführen



  • Eisflamme schrieb:

    Also überlappen sich Tabelle 1 und 2 stets in der Weise, dass es sich quasi um überschneidende Ausschnitte einer ungenannten dritten großen Tabelle handelt?

    Kann es Duplikate geben? Sonst hat man hier ein Problem:

    Tab 1)
    1
    4
    2
    3
    4

    Tab 2)
    4
    2
    4

    Wie soll das gemerged werden?

    Ich denke, vector ist schon ganz gut. Die Frage, die sich hier stellt, ist eher welchen Algorithmus Du anwenden möchtest. Vielleicht lässt sich das gar nicht fehlerfrei umsetzen, das wär schade.

    Wie ich schon sagte, so etwas sollte nicht vorkommen... Er sollte also prüfen, ob wenigstens 2 Elemente vor dem mergen hintereinander passen, andernfalls vielleicht eine Fehlermeldung ausgeben...



  • Na ja, das waren ja zwei andere Fragestellungen.

    Also die Annahmen sind:
    - es gibt keine doppelten Elemente
    - wenn es eine Dopplung gibt, sollten die Einträge solange übereinstimmen, bis eine der beiden Liste zu Ende ist, der überlappende Teil ist dann das Anhängsel

    Dann:

    typedef vector<int> WhatEverVector;
    typedef WhatEverVector::const_iterator WhatEverVectorIterator;
    
    WhatEverVector merge(const WhatEverVector& v1, const WhatEverVector& v2)
    {
        WhatEverVector r;
    
        // Find Same Element
        WhatEverVectorIterator n, m;
        std::size_t nnum, mnum;
        for(nnum = 0, n = v1.begin(); n != v1.end(); ++n, ++nnum)
            for(mnum = 0, m = v2.begin(); m < v2.end(); ++m, ++mnum)
                if(*n == *m)
                    goto afterLoop;
        afterLoop:
    
        if(m == v2.end())
            throw std::runtime_error("Lists are not mergeable.");
    
        if(nnum >= mnum)
            r.insert(r.begin(), v1.begin(), n);
        else
            r.insert(r.begin(), v2.begin(), m);
    
        const std::size_t MIN_MATCHES = 2;
        // Now, Check if vectors are mergeable
        for(std::size_t counter = 0; nnum < v1.size() && mnum < v2.size() && counter < MIN_MATCHES; ++nnum, ++mnum, ++counter)
            if(v1[nnum] != v2[mnum])
                throw std::runtime_error("Lists are not mergeable");
    
        // If yes, add vector which hasn't been added yet to result
        if(nnum >= mnum)
            r.insert(r.end(), m, v2.end());
        else
            r.insert(r.end(), n, v1.end());
        return r;
    }
    

    Ungetestet, sicherlich nicht super-sauber, bei den copys ist was falsch, für sonstige korrekte Wirkweise garantiere ich ebenfalls nicht, aber ich denke, die Idee kann man nachvollziehen.



  • Danke Eisflamme!
    Hast du das so schnell zusammengebastelt? 😮
    Dafür würde ich Stunden || Tage benötigen...
    Und es sieht sauberer als mein angefangenes Gebastel...

    Danke noch einmal...



  • Is nur hier im Forum hingeklatscht, daher sind da auch sicher viele Flüchtigkeitsfehler drin. Wie gesagt, sollte nur ne Idee sein.



  • Ok, sorry, hab schon nen ersten Fehler gefunden: copy benötigt, dass der Speicher zusätzlich reserviert wurde, sonst dumpts. Daher nutze ich nun insert. Hab Code oben editiert!

    Außerdem sollten die Argumente obv konstante Referenzen sein und der Iterator daher natürlich auch ein const_iterator. Ist editiert.

    Und der dritte Fehler: Das break oben hat ja nur die innere Schleife beendet. Da es kein double-break gibt, bin ich böööööööööööööööööööööööööööööööööööööse und nutze ein goto. Das sollte man aber normalerweise nie machen. Keine Ahnung, mir gefällt das da besser als eine extra bool-Variable, die man nach jedem Durchlauf der inneren Schleife abfragen muss... Aber nimm Dir daran kein Beispiel, gotos sollte man im Normalfall nie benutzen!

    Das ist aber oben jetzt alles reineditiert. Kannst ja sagen, ob Du weitere Fehler findest.

    Kann auch gut sein, dass man das eleganter lösen kann, aber war ja nur so hingeklatscht, hm...



  • Ich hab gerade gesehen, dass du noch einmal alles überarbeitet hast.
    Jetzt läuft es wie eine 1 😉
    Eine Frage:
    Du programmierst unter Windows oder warum meckert g++ bei std::runtime_error?
    Manchmal hat man das Gefühl, dass man in einem Jahr nichts gelernt hat, wenn man sieht, wie schnell und einfach es manchen Leuten von der Hand geht...



  • Geht's, wenn Du <stdexcept> inkludierst?

    Und puh... ich programmiere C++ streng genommen (mit vielen, teilweise über ein Jahr langen Pausen) seit 8 Jahren und ich bin der totale n00b. Mein Codedesign ist schlecht, ich habe hier viele wirklich dumme Flüchtigkeitsfehler eingebaut und ich hänge auch so ständig hier im Forum rum und lese viel.

    Dennoch bin ich ein kleiner Fisch und kaum zu gebrauchen. Glaub mir, wenn man die investierte Zeit in Bezug zur Leistung vergleicht wirst Du deutlich besser als ich abschneiden. Ein Jahr ist ohnehin kurz und die Hauptsache ist dann sowieso, dass es Spaß macht, also schmeiß solche Aussagen direkt übern Kutter.

    Aber es freut mich, dass Dir dieser Codeschnipsel hilft. 🙂



  • Okay,

    ein kleinen Fehler hab ich noch gefunden. Wenn ich die beiden Vektoren vertausche, kommt Bullsh!t raus. Also wenn das erste Element aus Tabelle 1 das vorletzte Element aus Tabelle 2 ist, schreibt er alles stumpf hintereinander (das letzte Element aus Tabelle 1 in diesem Beispiel lässt er dann weg).

    449119011
    1196571958
    1196571891
    25553429
    1196571854
    24673958
    258336940
    25553430
    24673940
    25553431
    24673937
    287763108
    287763107
    24673935
    766939640
    434179167
    25553428
    24673961
    434179168
    449119011
    1196571958
    1196571891
    25553429
    


  • Hm, musste Mal debuggen, ich hab jetzt leider keine Zeit mehr. Vll schau ich nochmal später oder morgen rein. 🙂



  • Eisflamme schrieb:

    Hm, musste Mal debuggen, ich hab jetzt leider keine Zeit mehr. Vll schau ich nochmal später oder morgen rein. 🙂

    Kommando zurück, funktioniert bestens!
    Danke 😃



  • Ja, kul. 🙂 Waren deine Listen porrös?



  • Übrigens klappt der Code nicht für den Fall, dass eine Liste die andere komplett umfasst. In dem Fall, würde man sogar die Liste kürzen, glaube ich. Dagegen hilft die zweite if-Abfrage, die in die zwei inserts verzweigt, umzuändern in so etwas wie v1.size() - nnum <= v2.size() - mnum. Aber evtl. muss man die Schleife davor dann noch etwas ändern. Ist halt nur für den Überlappungsfall gebaut.

    Wo hast Du überhaupt so eine Datenbasis?



  • Hallo railrun,

    Willkommen als registriertes Mitglied im C++-Forum.

    Soweit ich das sehe, hat der Algorithmus, den Eisflamme vorgeschlagen hat, die Komplexität von O(n^2). D.h. seine Dauer wächst quadratisch mit der Anzahl der Elemente in den beiden Tabellen. Dies ist aber negativ, vor allen bei Tabellen mit vielen Elementen und es muss auch nicht so sein, wenn man nur das erste Element von Tabelle 2 in Tabelle 1 sucht.

    Folgender Vorschlag hat nur O(n) - zumal Du gleiche Elemente in den Tabellen (fast) ausschließt.

    #include <algorithm> // std::find, std::equal
    #include <iterator> // std::distance
    #include <iostream>
    #include <vector>
    
    template< typename C, typename In >
    C merge( const In& t1, const In& t2 )
    {
        typename In::const_iterator k;
        typename In::const_reverse_iterator i = t1.rbegin();
        do
        {
            i = std::find( ++i, t1.rend(), t2.front() ); // sucht das erste Element von t2 (t2.front()) in t1 (von hinten)
            typedef typename In::size_type size_type;
            if( i == t1.rend() || size_type(std::distance( i.base(), t1.end() )) >= t2.size() )
                throw std::runtime_error( "kein merge moeglich" );
            k = i.base(); // Bem.: k zeigt jetzt eine Position hinter(!) das gefundenen Element in t1
        }
        while( !std::equal( --k, t1.end(), t2.begin() ) ); // prüft, ob die Sequenz [k,t1.end()) == [t2.begin(),..) ist
        C result( t1.begin(), k );
        result.insert( result.end(), t2.begin(), t2.end() );
        return result;
    }
    
    int main()
    {
        using namespace std;
        const int arr1[] = { 12, 23, -2, 67, 1, 14, 2, 9, 12, 12, 34, 81 };
        const int arr2[] = { 12, 12, 34, 81, 1, 2, 3, 5 };
        vector< int > t1( arr1, arr1 + sizeof(arr1)/sizeof(*arr1) );
        vector< int > t2( arr2, arr2 + sizeof(arr2)/sizeof(*arr2) );
        vector< int > m = merge< vector< int > >( t1, t2 ); // Typ des gewünschten Ergebnis-Containers angeben.
        copy( m.begin(), m.end(), ostream_iterator< int >( cout, " " ) );
        cout << endl;
        return 0;
    }
    

    @Eisflamme: ich habe dafür aber viel länger gebraucht als Du für Deinen Vorschlag.

    Gruß
    Werner



  • #include <vector>
    #include <iostream>
    #include <algorithm>
    #include <iterator>
    
    typedef std::vector<int> vec;
    typedef vec::iterator veci;
    
    int main()
    {
    	const int arr1[] = { 12, 23, -2, 67, 1, 14, 2, 9, 12, 12, 34, 81 }; 
        const int arr2[] = { 12, 12, 34, 81, 1, 2, 3, 5 }; 
        vec v1( arr1, arr1 + sizeof(arr1)/sizeof(*arr1) ); 
        vec v2( arr2, arr2 + sizeof(arr2)/sizeof(*arr2) ); 
    
    	for(veci i = v1.begin(); i != v1.end(); ++i)
    		v2.erase(std::remove(v2.begin(), v2.end(), *i), v2.end());
    
    	v1.insert(v1.end(), v2.begin(), v2.end());
    
    	std::copy(v1.begin(), v1.end(), std::ostream_iterator<int>( std::cout, " " ) );
    }
    

    Edit: Werners ist schneller als dieser Ansatz, aber ich konnte nicht widerstehen 😉



  • Werner:
    Natürlich, das ist sehr elegant! Ich hatte ganz vernachlässigt, dass natürlich das erste Element einer Range in der anderen vorkommt. Aber eine Voraussetzung war auch, dass Range 1 und 2 vertauschbar sind, d.h. nach der erfolglosen Suche von Element 1 aus Range 2, muss man das noch anders formulieren. 🙂 Das wollte ich mit einem Schlag abdecken, daher hab ich nicht so "genial" gedacht.

    Aber auf die Lösung wär ich gar nicht gekommen, da ich equal nicht kannte, distance gesucht aber wegen mangelnder Suchlust nicht gefunden habe und mit den reverse Iteratoren immer irgendwas falsch mache. ^^ Sauber.

    Aber du bedenkst doch sogar noch einen Sonderfall, oder? Wann wird deine Schleife denn nicht sofort false und beendet sich? Du erlaubst Duplikate, oder?

    HighLigerBiMBam:
    Das geht auch nur in eine Richtung hat auch quadratische Laufzeit. Ist aber ansonsten chicer, da natürlich viel kürzer als meine blöde Variante. 🙄



  • Vielen Dank an alle für die vielen Beispiele und die investierte Mühe. 🙂
    Ich versuche noch teilweise die genauen Abläufe zu verstehen, was wohl dem scheinbar mangelnden Wissen geschuldet ist (1 Jahr Selbststudium reicht wohl nicht aus). Ich werde mich mal noch tiefer einlesen müssen. 😞

    Wenn ich auf Fragen stoße wo ich gar nicht weiterkomme, werde ich mich hier bestimmt wieder blicken lassen.
    Danke noch einmal an Alle!


Anmelden zum Antworten