3. Chars zusammenfügen und sortieren

Chars zusammenfügen und sortieren

  • C

    😮 😮 😮

    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?

    0
  • V

    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);
    }
};
    0
  • C

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

    0
  • V

    ich habs auch verdreht.

    template <typename T> friend

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

    0
  • C

    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)

    0
  • D
     

    #include <algorithm>
    0
  • C

    ist ja schon drin
    1. Zeile 😉

    0
  • N
     

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

    0
  • C

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

    0
  • D

    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.

    0
  • C

    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 🙂

    0
  • N

    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.

    0
  • D

    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.

    0
  • N

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

    0
  • V

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

    0
  • V

    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.

    0
  • D

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

    0
  • C

    @ 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

    0
  • W

    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

    0
  • C

    ok, Ich habe vorhin mal kurtz versucht den code für mein nächstes file umzubauen. Das hat eigentlich ganz gut geklappt, bis auf das einlesen.

    Hier hab ich noch ein paar Probleme:

    airports.dat // hiervon wird eingelesen

    YWKS-66.686667 111.521667
    SCGZ-54.931072 -67.626261
    SAWH-54.843333 -68.295556

    airports.db // hiermit verglichen

    10;AGGM;-8.327969;157.263092
    22;ANAU;-0.547458;166.9191
    11;AYBK;-5.422317;154.672667

    code

    std::istream& operator>>( std::istream& in, ap_Entry& e ) // Lesen
{   // lese 'fix', ab nächsten char 5 Zeichen ignorieren, lese 'latitude' und 'longitude'
    return (in >> e.m_airport >> std::ws).ignore('-') >> e.m_latitude >> e.m_longitude;
}

std::istream& operator>>( std::istream& in, ap_Compare& f ) // Lesen
{   // lese 'fix' bis';', 'latitude', ';', 'longitude', ';' und 'nummer'
    // z.B.: 325;EDDF;22.528056;-156.170961;3
	return std::getline( in, f.m_elevation, ';' ) >> f.m_airport >> Char<';'> >> f.m_latitude >> Char<';'> >> f.m_longitude;
}

    Das problem ist, dass ich diesemal beim Einlesen keine leerzeichen habe, daher wird die erste koordinate mit dem ersten kürzel als ein Wort eingelesen.
    e.m_airport = 'EDDF47.385719'
    e.m_latitude = '132.473017'
    e.m_longlitude = '0.000000'

    Beim vergleichsfile ist das erste ein int, damit gehts nicht. wenn ich jetzt das int als string erstelle, so wird zwar eingelesen, aber ab dem kürzel hängt dann wieder alles in f.m_airport drin, latitude und longlitude bleiben leer...
    f.m_elevation = '5'
    f.m_airport = 'AGGA;-89.482753;102.572047'
    f.m_latitude = '0.00000000000'
    f.m_longlitude = '0.00000000000'

    anscheinend hab ich da etwas doch noch nciht so ganz verstanden...

    0
Anmelden zum Antworten