Templates, kann <unknown> und <unnamed> den Code langsamer machen?
-
Hallo,
folgender Code:
// suche Eintrag, der gemäß T::operator == gleich obj ist; // gib NULL zurück, falls keins vorhanden T const* find ( T const& obj ) const { // lineare Suche, jedoch kann, nachdem ein Eintrag gefunden wurde, der größer als obj ist, // wegen der aufsteigenden Monotonie der Einträge die Suche abgebrochen werden for ( Knoten* lauf = _first ; lauf != NULL ; lauf = lauf->next ) if ( lauf->data == obj ) return &( lauf->data ) ; else if ( lauf->data > obj ) return NULL ; return NULL ; }
,
der in einer sortierten einfach verketteten Liste nach obj sucht.
Ich habe das Problem, dass der Code in einer sortierten Liste langsamer als in einer unsortierten ist, was von den Daten her nicht sein kann. Selbst wenn die sortierte und die unsortierte Liste exakt dieselben Daten beinhalten, ist find() bei der sortierten Liste langsamer. Die sortierte Liste ist abgeleitet von der unsortierten Liste.
Beim find() der sortierten Liste zeigt mir der Compiler "<unknown> ListenContainer<T>::lauf" an, wenn ich über die Laufvariable "lauf" in der for-Schleife gehe. Wenn ich über "lauf->data" gehe, zeigt er mir "<unknown> <unnamed>::data" an.
Kann es sein, dass der Code bei der sortierten Liste langsamer ist, weil er bei jedem Aufruf von find() erst den Typ von Knoten und data ermitteln muss? Wenn ja, wie kann ich ihm den Typ bekannt machen? Anders kann ich mir nicht mehr erklären, warum der Code selbst bei unsortierter und sortierter Liste verschieden schnell ist, obwohl beide dieselben Daten beinhalten
Jemand einen Tipp?
Danke,
Thilo
-
Kennst Du das Sprichwort, "Wer viel misst, misst Mist"? Zeig mal vollständigen[1], kompilierbaren Code, insbesondere Deinen Messcode.
-
Dieses find() auf der unsortierten Liste ist natürlich schneller, denn es lügt wie gedruckt.
-
volkard schrieb:
Dieses find() auf der unsortierten Liste ist natürlich schneller, denn es lügt wie gedruckt.
Nein, auf der unsortierten Liste wird natürlich ein anderes find() verwendet mit linearer Suche, ohne den '<'-Vergleich.
Hier der gesamte Code, ist eben nicht ganz kurz:
main.cpp
#include <iostream> #include <valarray> #include <string> #include <vector> #include "Stoppuhr.h" #include "ListenContainer.h" #include "SortListe.h" using namespace std ; // MergeSort für abstrakte Container template < typename Container, // Typ des unsortierten Containers typename SortCont > // Typ des sortierten Containers void mergeSort ( Container& container, SortCont& sortCont ) { // Trivialfall if ( container.single() ) { sortCont = container.first() ; return ; } // teile pair< Container, Container >& paar = container.split() ; // herrsche SortCont sortiert1, sortiert2 ; mergeSort( paar.first, sortiert1 ) ; mergeSort( paar.second, sortiert2 ) ; // vereinige sortCont.merge( sortiert1, sortiert2 ) ; } // mergeSort() // Hauptprogramm int main ( int narg, char* argv[] ) { int n = 2500 ; ListenContainer<int> L ; SortListe<int> SL ; for ( int i = -n ; i < n ; ++i ) L.insert( -i-1 ) ; ListenContainer<int> L2 = L ; mergeSort( L2, SL ) ; Stoppuhr uhr ; size_t d = 100 ; uhr.start() ; for ( size_t j = 0 ; j < d ; ++j ) for ( int i = -n ; i < n ; ++i ) if ( L.find( i ) ) true ; cout << "ListenContainer: " << uhr.stopp() << endl ; uhr.start() ; for ( size_t j = 0 ; j < d ; ++j ) for ( int i = -n ; i < n ; ++i ) if ( SL.find( i ) ) true ; cout << "SortListe1: " << uhr.stopp() << endl ; return 0 ; } // main()
SortListe.h
#ifndef SORTLISTE_H #define SORTLISTE_H #define TEST 1 #include "ListenContainer.h" /** * Generische Klasse für einen einfachen Listen-Container * mit Standard-Schnittstelle. Sein Inhalt ist immer * gemäß T::operator < aufsteigend sortiert. */ template < typename T > class SortListe : public ListenContainer<T> { public: /*** Konstruktoren ***/ // Standardkonstruktor SortListe () : ListenContainer<T>() { } // Kopierkonstruktor von SortListe<T> SortListe ( SortListe<T> const& liste ) { (*this) = liste ; } #if TEST == 1 // Quasi-Kopierkonstruktor von Array // TODO: nur für Testzwecke SortListe ( vector<T> const& array ) : ListenContainer<T>( array ) { } #endif /*** get-Methoden ***/ // suche Eintrag, der gemäß T::operator == gleich obj ist; // gib NULL zurück, falls keins vorhanden T const* find ( T const& obj ) const { // lineare Suche, jedoch kann, nachdem ein Eintrag gefunden wurde, der größer als obj ist, // wegen der aufsteigenden Monotonie der Einträge die Suche abgebrochen werden for ( Knoten* lauf = _first ; lauf != NULL ; lauf = lauf->next ) if ( lauf->data == obj ) return &( lauf->data ) ; else if ( lauf->data > obj ) return NULL ; return NULL ; } /*** set-Methoden ***/ #if TEST == 1 // füge neuen Eintrag in das Objekt ein // TODO: geht mit binärer Suche besser void insert ( T const& obj ) { if ( empty() ) { ListenContainer<T>::insert( obj ) ; return ; } else if ( single() ) // Liste hat einen Eintrag { if ( _first->data < obj ) _first->next = new Knoten( obj, NULL ) ; // füge hinten an else _first = new Knoten( obj, _first ) ; // füge vorne an } else // Liste hat min. 2 Einträge { Knoten* lauf = _first ; Knoten* laufVorg = NULL ; for ( ; lauf != NULL && lauf->data < obj ; laufVorg = lauf, lauf = lauf->next ) ; if ( lauf == _first ) _first = new Knoten( obj, _first ) ; // füge vor erstes Element ein else if ( lauf == NULL ) laufVorg->next = new Knoten( obj, NULL ) ; // füge hinter letztes Element ein else { laufVorg->next = new Knoten( obj, lauf ) ; } } ++_n ; } #endif // Zuweisungsoperator für SortListe<T> SortListe<T>& operator = ( SortListe<T> const& liste ) { if ( this != &liste ) ListenContainer<T>::operator=( liste ) ; return (*this) ; } // mische die beiden sortierten Parameter-Listen zusammen // ins Objekt, diese sind danach leer; gib das Objekt selbst zurück SortListe& merge ( SortListe& liste1, SortListe& liste2 ) { clear() ; // lösche Einträge des eigenen Objektes und gebe Speicher frei if ( liste1.empty() ) _first = liste2._first ; // liste1 ist leer -> neue Liste = liste2 else if ( liste2.empty() ) _first = liste1._first ; // liste2 ist leer -> neue Liste = liste1 else // beide Listen sind nicht leer { /* Im Folgenden sind lauf1 und lauf2 Zeiger auf Listenknoten beider Listen, also lauf1 auf einen Listenknoten von liste1 und lauf2 auf einen Listenknoten von liste2 bzw. lauf1 auf einen Listenknoten von liste2 und lauf2 auf einen Listenknoten von liste1. Der eine Listenknoten wird immer solange inkrementiert, bis der Schlüssel seines Nachfolgers größer als der Schlüssel des anderen Listenknotens ist. Dann werden die Zeiger vertauscht und es wird genauso verfahren. Anschaulich wird eine Kette durch beide Listen erzeugt. Zum Beispiel mit einer Liste mit Einträgen (1,3,5,10) und einer zweiten Liste mit Einträgen (2,7,9,11,12,17): 1 3-5 10 |/ / /| 2 7-9 11-12-17 */ Knoten* lauf1 = NULL ; Knoten* lauf2 = NULL ; // setze ersten Knoten des Objekts auf Knoten mit minimalem Schlüssel if ( liste1._first->data <= liste2._first->data ) { _first = liste1._first ; lauf2 = liste2._first ; } else { _first = liste2._first ; lauf2 = liste1._first ; } // erster Laufknoten lauf1 = _first ; while ( true ) { // inkrementiere, bis Nachfolger-Schlüssel größer als Schlüssel des anderen Laufknotens oder der Laufknoten // am Ende seiner Liste angekommen ist for ( ; lauf1->next != NULL && lauf1->next->data <= lauf2->data ; lauf1 = lauf1->next ) ; // ein Laufknoten ist am Ende seiner Liste angekommen, hänge den Rest des anderen Laufknotens an if ( lauf1->next == NULL ) { lauf1->next = lauf2 ; break ; } // Zeiger wechseln Knoten* temp = lauf2 ; lauf2 = lauf1 ; lauf2 = lauf2->next ; lauf1->next = temp ; lauf1 = lauf1->next ; } } // aktualisiere Größe des eigenen Objekts _n = liste1.size() + liste2.size() ; // leere Parameterlisten, ohne Speicher freizugeben (denn dieser hängt jetzt am eigenen Objekt) liste1._first = NULL ; liste1._n = 0 ; liste2._first = NULL ; liste2._n = 0 ; return (*this) ; } // Zuweisung mit einem einzelnen Eintrag SortListe& operator = ( T const& entry ) { clear() ; ListenContainer<T>::insert( entry ) ; return (*this) ; } } ; // class SortListe<T> #endif // SORTLISTE_H
ListenContainer.h
#ifndef LISTENCONTAINER_H #define LISTENCONTAINER_H #define TEST 1 #include <iostream> #include <utility> // für Typ pair<> #include <sstream> using namespace std ; /** * Generische Klasse für einen einfachen Listen-Container * mit Standard-Schnittstelle */ template < typename T > class ListenContainer { protected: // gekapselte innere Klasse für Listenknoten class Knoten { public: // Eintrag = Datenobjekt T data ; // Verweis auf Nachfolger Knoten* next ; // Konstruktor Knoten ( T const& argData, Knoten* argNext = NULL ) : data( argData ), next( argNext ) { } } ; /*** geschützte Attribute ***/ // Verweis auf ersten Knoten Knoten* _first ; // Anzahl der Einträge im Objekt size_t _n ; public: // gekapselte innere Klasse class iterator { Knoten* _node ; // Verweis auf aktuellen Eintrag public: // Initialisierungskonstruktor iterator ( Knoten* argNode ) : _node( argNode ) { } // lesender Zugriff auf aktuellen Eintrag T const& operator * () const { return _node->data ; } // verweist Objekt auf anderen Eintrag als it? bool operator != ( iterator const& it ) const { return _node != it._node ; } // Inkrement void operator ++ () { _node = _node->next ; } } ; // class Iterator // gib Iterator auf ersten Eintrag zurück iterator begin () const { return iterator( _first ) ; } // gib Iterator auf ungültigen Eintrag zurück iterator end () const { return iterator( NULL ) ; } /*** Konstruktoren ***/ // Standardkonstruktor, init. leere liste ListenContainer () : _n( 0 ), _first( NULL ) { } // Quasi-Kopierkonstruktor von Array ListenContainer ( vector<T> const& array ) : _n( 0 ), _first( NULL ) { (*this) = array ; } // Kopierkonstruktor von ListenContainer<T> ListenContainer ( ListenContainer<T> const& liste ) : _n( 0 ), _first( NULL ) { (*this) = liste ; } /*** get-Methoden ***/ // ist Objekt leer? bool empty () const { return size() == 0 ; } // enthält das Objekt genau einen Eintrag? bool single () const { return size() == 1 ; } // gib Anzahl der Einträge im Objekt zurück size_t size () const { return _n ; } // gib ersten Eintrag im Objekt aus // wirf Exception, falls Objekt leer T first () const { if ( empty() ) throw "ListenContainer<T>::T first () const: Liste ist leer!" ; return _first->data ; } // gib ersten Eintrag dem Schlüsselwert von obj aus // oder NULL, falls es keinen gibt T const* find ( T const& obj ) const { // lineare Suche for ( Knoten* lauf = _first ; lauf != NULL ; lauf = lauf->next ) if ( lauf->data == obj ) return &( lauf->data ) ; return NULL ; } // ist Objektinhalt gemäß T::operator < aufsteigend sortiert? bool sortiert () const { if ( empty() || single() ) return true ; // direkter Vergleich zwischen jeweils zwei Einträgen for ( Knoten* lauf = _first ; lauf->next != NULL ; lauf = lauf->next ) if ( lauf->next->data < lauf->data ) return false ; return true ; } /*** set-Methoden ***/ // lösche alle Einträge im Objekt void clear () { while ( _first != NULL ) { Knoten* temp = _first ; _first = _first->next ; delete temp ; } _n = 0 ; } #if TEST == 1 // füge neuen Eintrag am Anfang in das Objekt ein void insert ( T const& obj ) { _first = new Knoten( obj, _first ) ; ++_n ; } #endif // teile Inhalt des Objekts hälftig auf in zwei neue Objekte; // das Objekt ist danach leer pair< ListenContainer, ListenContainer > split () { pair< ListenContainer<T>, ListenContainer<T> > paar ; if ( empty() ) return paar ; size_t haelfte = _n/2 ; paar.first._first = _first ; paar.first._n = haelfte ; paar.second._n = _n % 2 == 0 ? haelfte : haelfte + 1 ; // laufe bis zur Hälfte der Einträge Knoten* lauf = _first ; for ( size_t i = 0 ; i < haelfte - 1 ; lauf = lauf->next, ++i ) ; // schneide bei der Hälfte ab und überlasse den Rest der Kette der zweiten Hälfte Knoten* temp = lauf->next ; lauf->next = NULL ; // abschneiden paar.second._first = temp ; // Objekt leeren, ohne Speicher freizugeben (dieser befindet sich jetzt in den beiden Hälften) _first = NULL ; _n = 0 ; return paar ; } // Zuweisungsoperator für ListenContainer<T> ListenContainer<T>& operator = ( ListenContainer<T> const& liste ) { if ( this == &liste ) return (*this) ; clear() ; if ( liste.empty() ) return (*this) ; // kopiere ersten Eintrag von liste _first = new Knoten( liste._first->data, NULL ) ; // kopiere Einträge von liste an das Ende vom Objekt Knoten* last = _first ; for ( Knoten* lauf = liste._first->next ; lauf != NULL ; lauf = lauf->next, last = last->next ) last->next = new Knoten( lauf->data, NULL ) ; _n = liste._n ; return (*this) ; } // Zuweisungsoperator für vector<T> ListenContainer<T>& operator = ( vector<T> const& array ) { clear() ; if ( array.empty() ) return (*this) ; // kopiere ersten Eintrag von array _first = new Knoten( array[ 0 ], NULL ) ; // kopiere Einträge von array an das Ende vom Objekt Knoten* last = _first ; for ( vector<T>::const_iterator it = array.begin() + 1 ; it != array.end() ; ++it, last = last->next ) last->next = new Knoten( *it, NULL ) ; _n = array.size() ; return (*this) ; } /*** Ausgabe auf ostream ***/ friend ostream& operator << ( ostream& ostr, ListenContainer const& liste ) { ostr << "[" ; for ( Knoten* lauf = liste._first ; lauf != NULL ; lauf = lauf->next ) ostr << " " << lauf->data ; return ostr << " ]" ; } /*** Destruktor ***/ ~ListenContainer () { while ( _first != NULL ) { Knoten* temp = _first ; _first = _first->next ; delete temp ; } } } ; // class ListenContainer<T> #endif // LISTENCONTAINER_H
Stoppuhr.h
#ifndef STOPPUHR_H #define STOPPUHR_H #include <iostream> #include <ctime> // für clock() using namespace std ; /** * einfache Klasse zur Zeitmessung * Autor: Martin Oellrich, April 2015 */ class Stoppuhr { private: /*** private Attribute ***/ // letzte Startzeit double _startZeit ; public: /*** Konstruktoren ***/ // Standardkonstruktor, startet Zeitmessung Stoppuhr () { start() ; } /*** get-Methoden ***/ // gib laufende Zeit aus, halte Zeitmessung nicht an double stopp () const { return ( clock() - _startZeit ) / CLOCKS_PER_SEC ; } /*** set-Methoden ***/ // starte Messung neu void start () { _startZeit = clock() ; } /*** Ausgabe auf ostream ***/ friend ostream& operator << ( ostream& ostr, Stoppuhr const& uhr ) { return ostr << uhr.stopp() << " s" ; } } ; // class Stoppuhr #endif // STOPPUHR_H
Danke
-
#if 1 //genau so schnell (wenn L auch sortiert; sonst schneller) for( auto i = L.begin(), e = L.end(); i != e; ++i ) SL.insert( *i ); #else //langsamer ListenContainer<int> L2 = L; mergeSort( L2, SL ); #endif
-> liegt an deinem mergesort (die kommentare sind natürlich nicht aufs kopieren sondern aufs finden bezogen)
der vorteil einer list ist ja eigtl, dass man da ohne ein einziges new sortieren kann
aber du verstreust die adressen ewig weit:sortCont = container.first(); //-> SortListe& operator = ( T const& entry ) { clear(); ListenContainer<T>::insert( entry ); return ( *this ); }
bb
PS: Dein mergesort crasht bei leerer liste.
und spätestens
ListenContainer<int> L; SortListe<int> SL; for( int i = -n; i < n; ++i ) L.insert( -i - 1 ); ListenContainer<int> L2 = L; //DASS DAS HIER NOTWENDIG IST mergeSort( L2, SL ); //WEIL 'mergeSort( L, SL );' L KAPUTT MACHT
sollte dir zu denken geben.
weil es sehr nach aufgabenstellung klingt, kannst du das wohl aber nicht ändern?! genau wie merge und split - find das mit den drei listen pro aufruf extrem schwer zu lesen...wenn doch keine aufgabenstellung: was spricht dagegen, bei split nur die hälfte abzutrennen und in ne neue liste zu stecken, den rest in der ursprünglichen liste zu lassen? (merge analog dazu)
dann würde dein mergesort auch ohne das new auskommenedit:
totaler mist:SortListe& operator = ( T const& entry ) { clear(); ListenContainer<T>::insert( entry ); return ( *this ); }
weil dadurch
list = 3;
legaler code wird.also änder merge und split und mach die ganzen krücken weg, die du nur deshalb brauchtest.
dann sollte dein mergesort auch so in etwa aussehen:template< typename T, typename R > void mergesort_detail(T& von, R& nach) { //... } template< typename T, typename R > R mergesort(const T& obj) { T cpy(obj); R ret_val; mergesort_detail(obj, ret_val); return ret_val; } //oder gleich: // template< typename T, typename R > // R mergesort(T cpy)
-
Thilo87 schrieb:
Wenn ich über "lauf->data" gehe, zeigt er mir "<unknown> <unnamed>::data" an.
Kann es sein, dass der Code bei der sortierten Liste langsamer ist, weil er bei jedem Aufruf von find() erst den Typ von Knoten und data ermitteln muss? Wenn ja, wie kann ich ihm den Typ bekannt machen?
Nö.
Templates werden immer statisch compiliert, der Typ muss da (EDIT: zur Laufzeit) nie "gesucht" werden. Der Grund warum irgendwo "unknown" angezeigt wird ist vermutlich dass die IDE die passenden Debug-Infos nicht findet. z.B. weil die IDE zu doof ist sie zu finden oder auch weil der Compiler zu doof war passende Debug-Info zu generieren.
-
Ja, die Methodenköpfe und Beschreibungen, was die Methoden machen, sind großteils vorgegeben, also split() und merge(). Genauso das Merge-Sort.
Diese Zuweisungsoperatoren mit einem einzelnen Element mag mein Professor War auch vorgegeben.
Na gut, dann liegt es wohl daran, dass die Adressen durch das new so weit gestreut werden.
Grüße und Danke
-
ist noch ne menge drin, was mir nicht so sehr gefällt; aber z.b. kann dein mergesort jetzt ohne new sortieren...
#include <iostream> #include <utility> template < typename T > class ListenContainer { protected: class Knoten { public: // Eintrag = Datenobjekt T data; // Verweis auf Nachfolger Knoten* next; // Konstruktor Knoten( T const& argData, Knoten* argNext ) : data( argData ), next( argNext ) { } }; Knoten* _first; size_t _n; public: class iterator { Knoten* _node; public: iterator( Knoten* argNode ) : _node( argNode ) { } T const& operator * ( ) const { return _node->data; } bool operator != ( iterator const& it ) const { return _node != it._node; } void operator ++ ( ) { _node = _node->next; } }; iterator begin() const { return iterator( _first ); } iterator end() const { return iterator( NULL ); } ListenContainer() : _n( 0 ), _first( NULL ) { } ListenContainer( ListenContainer<T> const& liste ) : _n( 0 ), _first( NULL ) { ( *this ) = liste; } bool empty() const { return size() == 0; } bool single() const { return size() == 1; } size_t size() const { return _n; } void insert( T const& obj ) { _first = new Knoten( obj, _first ); ++_n; } T first() const { if( empty() ) throw "ListenContainer<T>::T first () const: Liste ist leer!"; return _first->data; } iterator find( T const& obj ) const { auto i( begin() ), e( end() ); for( ; i != e; ++i ) { if( *i == obj ) return i; } return e; } bool sortiert() const { if( empty() ) return true; for( Knoten* lauf = _first; lauf->next != NULL; lauf = lauf->next ) if( lauf->next->data < lauf->data ) return false; return true; } void swap( ListenContainer& other ) { using std::swap; swap( _n, other._n ); swap( _first, other._first ); } void clear() { while( _first != NULL ) { Knoten* temp = _first; _first = _first->next; delete temp; } _n = 0; } std::pair< ListenContainer, ListenContainer > split() { pair< ListenContainer<T>, ListenContainer<T> > ret_val; if( empty() ) return ret_val; ret_val.first._first = _first; ret_val.first._n = _n / 2; ret_val.second._n = _n - ret_val.first._n; // laufe bis direkt vor die Hälfte der Einträge Knoten* lauf = _first; for( size_t i = 0; i < ret_val.first._n - 1; lauf = lauf->next, ++i ); // abschneiden Knoten* mid = lauf->next; lauf->next = NULL; ret_val.second._first = mid; // Objekt leeren, ohne Speicher freizugeben _first = NULL; _n = 0; return ret_val; } ListenContainer<T>& operator = ( ListenContainer<T> const& liste ) { if( this == &liste ) return ( *this ); clear(); if( liste.empty() ) return ( *this ); // kopiere ersten Eintrag von liste _first = new Knoten( liste._first->data, NULL ); // kopiere Einträge von liste an das Ende vom Objekt Knoten* last = _first; for( Knoten* lauf = liste._first->next; lauf != NULL; lauf = lauf->next, last = last->next ) last->next = new Knoten( lauf->data, NULL ); _n = liste._n; return *this; } ~ListenContainer() { clear(); } }; template< typename T > std::ostream& operator << ( std::ostream& ostr, ListenContainer<T> const& liste ) { ostr << "["; for( auto i( liste.begin() ), e( liste.end() ); i != e; ++i ) ostr << " " << *i; return ostr << " ]"; } template< typename T > void swap( ListenContainer<T>& lhs, ListenContainer<T>& rhs ) { lhs.swap( rhs ); } template < typename T > class SortListe : public ListenContainer<T> { public: SortListe(){} SortListe( SortListe<T> const& liste ) { *this = liste; } iterator find( T const& obj ) const { auto i( begin() ), e( end() ); for( ; i != e; ++i ) if( *i == obj ) return i; else if( *i > obj ) break; return e; } SortListe<T>& operator = ( SortListe<T> const& liste ) { ListenContainer& lhs = static_cast<ListenContainer&>( *this ); const ListenContainer& rhs = static_cast<const ListenContainer<T>&>( liste ); lhs = rhs; return *this; } void merge( SortListe& liste1, SortListe& liste2 ) { clear(); // lösche Einträge des eigenen Objektes und gebe Speicher frei if( liste1.empty() ) _first = liste2._first; // liste1 ist leer -> neue Liste = liste2 else if( liste2.empty() ) _first = liste1._first; // liste2 ist leer -> neue Liste = liste1 else // beide Listen sind nicht leer { /* Im Folgenden sind lauf1 und lauf2 Zeiger auf Listenknoten beider Listen, also lauf1 auf einen Listenknoten von liste1 und lauf2 auf einen Listenknoten von liste2 bzw. lauf1 auf einen Listenknoten von liste2 und lauf2 auf einen Listenknoten von liste1. Der eine Listenknoten wird immer solange inkrementiert, bis der Schlüssel seines Nachfolgers größer als der Schlüssel des anderen Listenknotens ist. Dann werden die Zeiger vertauscht und es wird genauso verfahren. Anschaulich wird eine Kette durch beide Listen erzeugt. Zum Beispiel mit einer Liste mit Einträgen (1,3,5,10) und einer zweiten Liste mit Einträgen (2,7,9,11,12,17): 1 3-5 10 |/ / /| 2 7-9 11-12-17 */ Knoten* lauf1 = NULL; Knoten* lauf2 = NULL; // setze ersten Knoten des Objekts auf Knoten mit minimalem Schlüssel if( liste1._first->data <= liste2._first->data ) { _first = liste1._first; lauf2 = liste2._first; } else { _first = liste2._first; lauf2 = liste1._first; } // erster Laufknoten lauf1 = _first; while( true ) { // inkrementiere, bis Nachfolger-Schlüssel größer als Schlüssel des anderen Laufknotens oder der Laufknoten // am Ende seiner Liste angekommen ist for( ; lauf1->next != NULL && lauf1->next->data <= lauf2->data; lauf1 = lauf1->next ); // ein Laufknoten ist am Ende seiner Liste angekommen, hänge den Rest des anderen Laufknotens an if( lauf1->next == NULL ) { lauf1->next = lauf2; break; } // Zeiger wechseln Knoten* temp = lauf2; lauf2 = lauf1; lauf2 = lauf2->next; lauf1->next = temp; lauf1 = lauf1->next; } } // aktualisiere Größe des eigenen Objekts _n = liste1.size() + liste2.size(); // leere Parameterlisten, ohne Speicher freizugeben (denn dieser hängt jetzt am eigenen Objekt) liste1._first = NULL; liste1._n = 0; liste2._first = NULL; liste2._n = 0; } }; template < typename Container, // Typ des unsortierten Containers typename SortCont > // Typ des sortierten Containers void mergeSort( Container& container, SortCont& sortCont ) { if( container.empty() ) return; // Trivialfall if( container.single() ) { swap( sortCont, container ); return; } // teile std::pair< Container, Container > paar = container.split(); // herrsche SortCont sortiert1, sortiert2; mergeSort( paar.first, sortiert1 ); mergeSort( paar.second, sortiert2 ); // vereinige sortCont.merge( sortiert1, sortiert2 ); } #include <iostream> #include <ctime> class Stoppuhr { private: /*** private Attribute ***/ // letzte Startzeit double _startZeit; public: /*** Konstruktoren ***/ // Standardkonstruktor, startet Zeitmessung Stoppuhr() { start(); } /*** get-Methoden ***/ // gib laufende Zeit aus, halte Zeitmessung nicht an double stopp() const { return ( std::clock() - _startZeit ) / CLOCKS_PER_SEC; } /*** set-Methoden ***/ // starte Messung neu void start() { _startZeit = clock(); } /*** Ausgabe auf ostream ***/ friend std::ostream& operator << ( std::ostream& ostr, Stoppuhr const& uhr ) { return ostr << uhr.stopp() << " s"; } }; using namespace std; #include <algorithm> ListenContainer<int> gimme(int n) { ListenContainer<int> L; for( int i = -n; i < n; ++i ) { L.insert( -i - 1 ); } return L; } int main() { int n = 2500; ListenContainer<int> L = gimme(1000); ListenContainer<int> L2 = gimme(1000); SortListe<int> SL_tmp; mergeSort( L2, SL_tmp ); // SortListe<int> SL = SL_tmp; - schnell // SortListe<int>& SL = SL_tmp; - langsam Stoppuhr uhr; size_t d = 100; size_t a( 0 ); uhr.start(); for( size_t j = 0; j < d; ++j ) for( int i = -n; i < n; ++i ) if ( L.find( i ) != L.end() ) ++a; cout << "ListenContainer: " << uhr.stopp() << endl ; size_t b( 0 ); uhr.start() ; for ( size_t j = 0 ; j < d ; ++j ) for ( int i = -n ; i < n ; ++i ) if ( SL.find( i ) != SL.end() ) ++b; cout << "SortListe1: " << uhr.stopp() << endl ; cout << a << " = " << b << endl; system( "PAUSE" ); }
-
Danke, leider dürfen wir das so nicht verändern. Das MergeSort soll bleiben, wie es ist. Das war vom Professor vorgegebener Code.
Ich frage mich gerade, wie man experimentell nachweisen könnte, dass die Speicherplätze in der SortListe und im ListenContainer unterschiedlich weit verteilt sind. Wie wäre es damit, als Methode im ListenContainer bzw. in der abgeleiteten Klasse SortListe?
unsigned long long abstand() const { unsigned long long summe = 0 ; for ( Knoten* lauf = _first ; lauf->next != NULL ; lauf = lauf->next ) summe += abs( long long( ( &lauf->data - &lauf->next->data )*sizeof(T) ) ) ; return summe ; }
Funktioniert das korrekt, wie es soll, d.h. gibt das den Gesamtabstand zwischen allen Daten im Speicher aus?
-
Das MergeSort soll bleiben, wie es ist. Das war vom Professor vorgegebener Code.
dann schreib zumindest in die "doku" obendrüber, dass die liste nicht leer sein darf oder frag deinen prof, ob er das noch nicht gemerkt hat und vll ändern will
abstand
(davon abgesehen, dass du nicht auf empty() prüfst und du dann nen nullptr dereferenzierst)
ist mMn allein nicht aussagekräftig.
allerdings kann ich dir auch nicht genau sagen, in wie fern man dort die größe des cpu caches berücksichtigen muss. sicher spielt auch die größe der memory pages eine rolle (bzw nur, ob es die gleiche page ist oder nicht).aber all das sollte eigtl gar keine rolle spielen, weil du bei einer list ja nicht davon ausgehst, dass die elemente so schön dicht nacheinander im speicher liegen.
wenn du geschwindigkeit willst, wirst du so gut wie nie eine liste nehmen.wenn du gerecht prüfen willst, solltest du so testen:
//pseudocode L = list_erstellen; SL = list_erstellen; L.sort() //auch sortieren //rest wie gehabt mit stoppuhr + find
bb