Chars zusammenfügen und sortieren

volkard

und jetzt, wo der code aufgeräumt ist,
mir scheint, man könnte fx_Compare nach dem einlesen sortieren und dann statt find lieber lower_bound nehmen. müßte den lauf eigentlich vom stundenbereich in den sekundenbereich drücken.

ich hab fast nix geändert und es auch nicht getestet. so diese richtung meine ich:

#include <algorithm> // sort, find
#include <iostream>
#include <fstream>
#include <string>
#include <deque>

// --   Helferlein zum Einlesen eines erwarteten Zeichens
template< char C >  
std::istream& Char( std::istream& in )
{
    char c;
    if( in >> c && c != C )
        in.setstate( std::ios_base::failbit );
    return in;
}

struct Entry    // Struktur für das Eingangsfile
{
    bool operator<( const Entry& b ) const    // legt die Reihenfolge bei 'sort' fest
    {
        return m_fix < b.m_fix;
    }
    std::string m_fix;            // String für das Fix
    double m_latitude;            // bool für Latitude
    double m_longitude;            // bool für longlitude
};

struct Compare    // Strukur für das Vergleichsfile
{
    explicit Compare( const std::string& fix = std::string() )  // Konstruktor für Vergleiche
        : m_fix( fix )
        , m_latitude(), m_longitude()
        , m_Number()
    {}
    bool operator<( const Compare& b ) const    // legt die Reihenfolge bei 'sort' fest
    {
        return m_fix < b.m_fix;
    }
    bool operator==( const Compare& b ) const
    {
        return m_fix == b.m_fix;
    }
    std::string m_fix;            // String für das Fix
    double m_latitude;            // bool für latitude
    double m_longitude;            // bool für longlitude
    int m_Number;                // int für die nummer
};
bool operator!=( const Compare& a, const Compare& b )
{
    return !(a == b);
}

std::istream& operator>>( std::istream& in, Entry& e ) // Lesen
{   // lese 'fix', ab nächsten char 5 Zeichen ignorieren, lese 'latitude' und 'longitude'
    return (in >> e.m_fix >> std::ws).ignore( 5 ) >> e.m_latitude >> e.m_longitude;
}
std::ostream& operator<<( std::ostream& out, const Entry e ) // Formatieren
{   // Ausgabe im neuen Format
    // z.B.: ENTRE;-31.534170;130.949200
    return out << e.m_fix << ';' << e.m_latitude << ';' << e.m_longitude;
}
std::istream& operator>>( std::istream& in, Compare& f ) // Lesen
{   // lese 'fix' bis';', 'latitude', ';', 'longitude', ';' und 'nummer'
    // z.B.: 00MKK;22.528056;-156.170961;3
    return std::getline( in, f.m_fix, ';' ) >> f.m_latitude >> Char<';'> >> f.m_longitude >> Char<';'> >> f.m_Number;
}
std::istream& comment( std::istream& in ) // überliest Kommentar beginnend mit ';'
{
    while( in >> std::ws && !in.eof() && char(in.peek()) == ';' )
        in.ignore( 999, '\n' );
    return in;
}
std::istream& comment2( std::istream& in ) // überliest Kommentar beginnend mit '/'
{
    while( in >> std::ws && !in.eof() && char(in.peek()) == '/' )
        in.ignore( 999, '\n' );
    return in;
}

int ExportFixes()
{
    using namespace std;
    deque< Entry > fx_Entries;                                      // Container mit Struktur "Entry" erstellen
    {
        std::ifstream fx_fwpNavFIX("navdata/wpNavFIX.txt");         // Input- Datei wpNavFix definieren
        for(Entry e; fx_fwpNavFIX >> comment >> e; )                // Einträge von Entry durchlaufen
        {
            fx_Entries.push_back( e );                              // e in fx_Entries einfügen
        }
        sort( fx_Entries.begin(), fx_Entries.end() );               // fx_Entries sortieren
    }

    deque< Compare > fx_Compare;
    {
        std::ifstream fx_fFixes("navigation/Fixes.db");             // Input-Datei Fixes definieren
        for( Compare f; fx_fFixes >> comment2 >> f; )               // Einträge von Entry durchlaufen
        {
            fx_Compare.push_back( f );
        }
//weg: nix weg, nur marker für neue zeile
        stable_sort( fx_Compare.begin(), fx_Compare.end() );//neu
    }
    ofstream fx_OutFile("navigation_new/Fixes.db");                                // Ausgabedatei definieren
    for( deque< Entry >::iterator e = fx_Entries.begin(); e != fx_Entries.end(); ++e ) //fx_Entries durchlaufen
    {
        // --   alle Einträge aus 'navdata/wpNavFIX.txt' sortiert wegschreiben
        //      hinter jeden Eintrag wird die Zahl geschrieben, die in 'navigation_new/Fixes.db' für diesen Eintrag
        //      gefunden wurde. Falls keiner gefunden wurde, so wird eine '5' angehängt.
        fx_OutFile << *e << ';';
//weg        deque< Compare >::iterator f = find( fx_Compare.begin(), fx_Compare.end(), Compare( e->m_fix ) );
        deque< Compare >::iterator f = lower_bound( fx_Compare.begin(), fx_Compare.end(), Compare( e->m_fix ) );//neu
//weg        if( f != fx_Compare.end() )
        if( f != fx_Compare.end() && f->m_fix==e->m_fix)//neu
            fx_OutFile << f->m_Number;      // Nummer aus 'navigation_new/Fixes.db' für diesen Eintrag anhängen
        else
            fx_OutFile << '5';              // default ist 5
//weg        fx_OutFile << endl;
        fx_OutFile << '\n';//neu, endl macht auch flush, nix gut
    }
    return (true);
}

campinge

Ich hab gerade auf Release umgeschaltet und deinen veränderten code eingefügt.

Resultat : "Fixes Exported in: 0 Hours, 0 Minutes, 14 Seconds"

Genial, danke!!!!!!
Was macht lower_bound jetzt so anders, dass es SO viel schneller geht?

volkard

campinge schrieb:

Resultat : "Fixes Exported in: 0 Hours, 0 Minutes, 14 Seconds"

jup, das trifft meine erwartungen.

miss doch gerade noch, ob es einen merklichen effekt hat, wenn man beiden strukturen noch eine eigene swap-funktion spendiert. das würde glaub ich so gehen:

struct Entry    // Struktur für das Eingangsfile 
{ 
    bool operator<( const Entry& b ) const    // legt die Reihenfolge bei 'sort' fest 
    { 
        return m_fix < b.m_fix; 
    } 
    std::string m_fix;            // String für das Fix 
    double m_latitude;            // bool für Latitude 
    double m_longitude;            // bool für longlitude 
    friend template <typename T>
    std::swap(Entry& a,Entry& b)
    {
        std::swap(a.m_fix,b.m_fix);
        std::swap(a.m_latitude,b.m_latitude);
        std::swap(a.m_longitude,b.m_longitude);
    }
}; 

struct Compare    // Strukur für das Vergleichsfile 
{ 
    explicit Compare( const std::string& fix = std::string() )  // Konstruktor für Vergleiche 
        : m_fix( fix ) 
        , m_latitude(), m_longitude() 
        , m_Number() 
    {} 
    bool operator<( const Compare& b ) const    // legt die Reihenfolge bei 'sort' fest 
    { 
        return m_fix < b.m_fix; 
    } 
    bool operator==( const Compare& b ) const 
    { 
        return m_fix == b.m_fix; 
    } 
    std::string m_fix;            // String für das Fix 
    double m_latitude;            // bool für latitude 
    double m_longitude;            // bool für longlitude 
    int m_Number;                // int für die nummer 
    friend template <typename T>
    std::swap(Compare& a,Compare& b)
    {
        std::swap(a.m_fix,b.m_fix);
        std::swap(a.m_latitude,b.m_latitude);
        std::swap(a.m_longitude,b.m_longitude);
        std::swap(a.m_Number,b.m_Number);
    }
};

campinge

hm, das bringt mir jetzt eine compiler-Fehlermeldung:

(10) error C2059: syntax error : 'template<'
(10) error C2899: typename cannot de used outside a template declaration
(12) error C2334: unexpected token(s) precending '{'; skipping appearant function body

und das halt 2 mal...

volkard

ich habs auch verdreht.

template <typename T> friend

solls heißen.
sorry. und ich weiß nicht sicher, obs damit dann geht.

campinge

oha, das hat's sogar noch schlimmer gemacht:

nur mal ein kleiner Ausschnitt:
'std::swap' : not a function
'std::swap' : dependant name is not a type prefix with 'typename' to indicate a type
'swap' : cannot be a template definition
binary '==' 'const Compare' does not define this operator or a conversion to a type acceptable.....

das geht so dann +100 Zeilen weiter o.O
(56 errors)

drakon

#include <algorithm>

campinge

ist ja schon drin
1. Zeile

Nexus

friend template <typename T> 
    std::swap(Compare& a,Compare& b) 
    { 
        std::swap(a.m_fix,b.m_fix); 
        std::swap(a.m_latitude,b.m_latitude); 
        std::swap(a.m_longitude,b.m_longitude); 
        std::swap(a.m_Number,b.m_Number); 
    }

Eine friend -Definition? Geht das?

Ansonsten machst du einfach ein eigenes swap() .

campinge

jetzt hab ich wieder die fehlermeldungen von oben, klappt also auch nicht.
Was ist denn jetzt eigentlich dieses swap?

drakon

campinge schrieb:

jetzt hab ich wieder die fehlermeldungen von oben, klappt also auch nicht.
Was ist denn jetzt eigentlich dieses swap?

http://www.cplusplus.com/reference/algorithm/swap.html

Reduzier deinen Code mal so, dass du den selbern Fehler noch hast und das hier posten kannst.

campinge

folgendes ist gerade erfolgreich durchgelaufen:

template <typename T>
    void swap(Entry& a,Entry& b)
    {
        std::swap(a.m_fix,b.m_fix);
        std::swap(a.m_latitude,b.m_latitude);
        std::swap(a.m_longitude,b.m_longitude);
    }

hat 11 sekunden gedauert, also nocht mal 3 sekunden schneller geworden

Nexus

campinge schrieb:

Was ist denn jetzt eigentlich dieses swap?

Das soll zwei Instanzen tauschen.

Versuchs doch mal mit Spezialisierung von std::swap() (hier bin ich mir nicht ganz sicher, ob das vom Standard erlaubt ist, aber ich meinte, schon)

template <>
void std::swap<Compare>(Compare& Right, Compare& Left)
{
	std::swap(Left.m_fix, Right.m_fix); 
	std::swap(Left.m_latitude, Right.m_latitude); 
	std::swap(Left.m_longitude, Right.m_longitude); 
	std::swap(Left.m_Number, Right.m_Number); 
}

Oder mit Überladung (nicht im Namensraum std )

void swap(Compare& Right, Compare& Left)
{
	std::swap(Left.m_fix, Right.m_fix); 
	std::swap(Left.m_latitude, Right.m_latitude); 
	std::swap(Left.m_longitude, Right.m_longitude); 
	std::swap(Left.m_Number, Right.m_Number); 
}

Und dann entsprechende friend -Deklarationen in der Klasse. Schöner wäre natürlich, eine Memberfunktion swap() anzubieten, dann kann die von der globalen Funktion aufgerufen werden.

drakon

Versuchs doch mal mit Spezialisierung von std::swap() (hier bin ich mir nicht ganz sicher, ob das vom Standard erlaubt ist, aber ich meinte, schon)

Richtig. Man darf die Standardbibliothek nicht erweitern, aber man darf Spezialisierungen schreiben.

Nexus

drakon schrieb:

Richtig. Man darf die Standardbibliothek nicht erweitern, aber man darf Spezialisierungen schreiben.

Danke. Sind Template-Spezialisierungen die einzige Ausnahme für Erweiterung des std -Namensraums? Und gilt das auch für Klassen wie std::vector<MyClass> ?

volkard

Nexus schrieb:

Eine friend -Definition? Geht das?

ja, an sich schon. die benutze ich mit großer freude für binare operatoren oder sowas. dann steht der triviale code auch innerhalb der klasse und ich habe die vorteile der externen funktion.
hätte vielleicht auch mit swap funktioniert, aber ich hab's verdusselt.

volkard

campinge schrieb:

Was macht lower_bound jetzt so anders, dass es SO viel schneller geht?

es benutzt die binäre suche
http://de.wikipedia.org/wiki/Binäre_Suche

Was ist denn jetzt eigentlich dieses swap

wie bereits gesagt, es vertauscht zwei elemente.
die beschleunigungsidee dahinter ist, daß std::sort und std::stable_sort vermutlich ganz ganz oft swap aufrufen, um zwei elemente zu vertauschen. und ausgerechnet swap kann man gut optimieren.
normalerweise würde swap erledigt werden, indem der dreiecktausch
http://de.wikipedia.org/wiki/Dreieckstausch
für zwei Compare-objekte ausgeführt werden würde. dabei werden dann strings angelegt, strings kopiert, strings gelöscht. für string gibts schon eine spezialisierung für swap => strings können mit swap sauschnell vertauscht werden. und unser swap benutzt das und wird deswegen auch schnell.

hat 11 sekunden gedauert, also nocht mal 3 sekunden schneller geworden

jup. das freut mich.

an weitere geschwindigkeitsoptimierungen zu denken, bringt nichts mehr, denke ich. die wären eher kompliziert und brächten auch nicht mehr als 5 sekunden und würden den code schlecht wartbar machen, fürchte ich.

drakon

Mich nähme jetzt noch Wunder, ob jetzt dieser riesen Sprung alleine von der Optimierung gekommen ist, oder auch ein Grossteil vom umstellen von Debug auf Release.

Kannst du das mal noch schnell auf Debug laufen lassen? (sorry, nimmt mich jetzt gerade Wunder.. :))

campinge

@ volkard erstmal vielen dank für die erklärung!
Jetzt weis ich zumindest, was da passiert ^^

@ drakon: die Optimierung scheint wohl den großteil gebracht zu haben. im debug-mode hats nur 1 Minute und 12 sekunden gedauert

Werner Salomon

volkard schrieb:

@Werner Salomon:

und jetzt, wo der code aufgeräumt ist,
mir scheint, man könnte fx_Compare nach dem einlesen sortieren und dann statt find lieber lower_bound nehmen. müßte den lauf eigentlich vom stundenbereich in den sekundenbereich drücken.

Ja - das liegt auf der Hand. Ich hätte als nächstes vorgeschlagen, den Inhalt von "navigation/Fixes.db" gleich in einem set unterzubringen, dann kann beim Einlesen dieser Datei auch gleich auf evt. doppelte Einträge geprüft werden.
Aber das Ergebnis sollte das gleiche sein.

Rein von Gefühl her ist der Übergang von linearer nach binärer Suche ein erstaunlicher Zeitgewinn.
Wenn man's mal rechnet, wird es klar: bei 188000 Einträgen (in navigation/Fixes.db) sind es im Mittel 94000 Vergleiche pro Zeile. Bei binärer Suche sind es nur ca. 18 Vergleiche - macht Faktor 5200 schneller (!) - 2:26::11 sind 8771 Sekunden dividiert durch 5200 bleiben lächerliche 1,7Sekunden - Das Einlesen und Schreiben der Dateien kommt dann noch dazu, aber wie man sieht liegt das auch im Sekundenbereich.

Gruß
Werner