3. Werte-Tabellen vergleichen und zusammenführen

Werte-Tabellen vergleichen und zusammenführen

  • E

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

    0
  • E

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

    0
  • W

    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

    0
  • H
     

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

    0
  • E

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

    0
  • R

    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!

    0
Anmelden zum Antworten