Werte-Tabellen vergleichen und zusammenführen

railrun

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

Eisflamme

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.

railrun

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

Eisflamme

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

railrun

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

Eisflamme

Ja, kul. Waren deine Listen porrös?

Eisflamme

Ü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?

Werner Salomon

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

HighLigerBiMBam

#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

Eisflamme

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.

railrun

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!