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 auskommen

    edit:
    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


Log in to reply