Chars zusammenfügen und sortieren

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

campinge

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

Werner Salomon

campinge schrieb:

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'

Das erreicht man, indem man mit std::setw(..) die maximale Anzahl von Zeichen angibt, die in den String eingelesen werden dürfen (hier wahrscheinlich 4)

campinge schrieb:

Beim vergleichsfile ist das erste ein int, damit gehts nicht.

doch das funktioniert (s.u.)

campinge schrieb:

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

wie oben, der String muss begrenzt werden. Hier mein Ansatz:

#include <iomanip> // setw
// ...
struct ap_Entry
{
    // ... operator< usw.
    std::string m_airport;
    double m_latitude;            // Latitude
    double m_longitude;            // Longlitude
};

std::istream& operator>>( std::istream& in, ap_Entry& e )
{   //  Format:
    //      "YWKS-66.686667 111.521667" // Beispiel
    //       1234<-  lat -><- long  ->
    //       |   |         |
    //       |   |         +-- Longitude (double)
    //       |   +-- Latitude (double)
    //       +-- Airport (max. 4 Zeichen)
    //
    return in >> std::setw(4) >> e.m_airport >> e.m_latitude >> e.m_longitude;
} 

struct ap_Compare
{
    // ... operator< usw.
    int m_elevation;
    std::string m_airport;
    double m_latitude, m_longitude;
};
std::istream& operator>>( std::istream& in, ap_Compare& f )
{   // Format:
    //      "10;AGGM;-8.327969;157.263092"  // Beispiel
    //       |  |    |         |
    //       |  |    |         +-- Longitude (double)
    //       |  |    +-- Latitude (double)
    //       |  +-- Airport (hier begrenzt durch ';')
    //       +----- Höhe (int)
    return getline( in >> f.m_elevation >> Char<';'>, f.m_airport, ';' ) >> f.m_latitude >> Char<';'> >> f.m_longitude;
}

wichtig dabei ist, dass die Kennung des Flughafens aus maximal 4 Zeichen bestehen darf (nicht mehr). Hat die Kennung weniger Zeichen (z.B. München := MUC), so muss mindestens ein Leerzeichen folgen! Sonst gehen Zeichen aus der Zahl verloren. Das führt nicht unbedingt zu einem Lesefehler, aber zu fehlerhaften Daten.

campinge schrieb:

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

das mit der Länge kannst Du nicht wissen: versuche zumindest den Kommentar (Format) in den Einlese-Funktionen exakt hinzuschreiben - das hilft schon.
das Einlesen einer Zahl endet, wenn ein Zeichen folgt, dass nicht mehr zu der Zahl gehörig interpretierbar ist. Das Einlesen eines Strings endet i.A. erst mit einem white space Zeichen (z.B. Leerzeichen).
Bei der Vergleichsdatei (ap_Compare) darf dagegen zwischen der Flughafenkennung und dem ';' kein Leerzeichen mehr stehen, das würde getline mit einlesen. Wie vorher schon gesagt, es ist alles vom Format der Dateien abhängig, da ich dies aber nicht exakt kenne, ist da erstmal nur ein Versuch.

Gruß
Werner

campinge

Wiedermal vielen Dank!
das beruhigt mich dann doch, wenn ich's nicht wissen konnte, Jetzt weis ichs jedenfalls

Bei den Flughafenkennungen mache ich mir keine sorgen, hier werden die sogenannten ICAO-Codes verwendet, die sind immer 4-Stellig (München = EDDM)

Dann werd ich mal weiterbasteln !

campinge

ok, schon das nächste 'problem', diesmal aber etas simpleres

std::istream& operator>>( std::istream& in, na_Entry& e )
{   //  Format:
    //      "MCMURDO STATION         NGD  VOR -77.865000 167.180000114.30H" // Beispiel
    //       |12345678901234567890123<-> <-> <-  lat  -><-  long -><-fr->|
    //       ||						 |   |   |			|		   |	 +-- ignore this one
    //       ||						 |   |	 |			|		   +-- frequency (double)
	//		 ||						 |	 |	 |			+-- longlitude (double)
	//		 ||						 |	 |	 +-- latitude (double)
	//		 ||						 |	 +-- type (string)
    //       ||						 +-- name (string)
	//		 |+-- ignoriere 23 zeichen
    //       +-- fullname<unused> (string, 24 zeichen)
    // 
	return (in >> std::setw(1) >> e.m_fullname).ignore(24) >> e.m_name >> std::setw(4)>> e.m_type >> e.m_latitude >> 
std::setw(11) >> e.m_longitude >> std::setw(6) >> e.m_frequency;
}

wie ich strings beim einlesen schneide hab ich jetzt endlich verstanden
Allerdings schienen sich die Entwickler der Ursprungsfiles nicht wirklich sicher zu sein, welches format sie denn jetzt verwenden...

Der Anfang wird perfekt eingelesen, aber im file sind m_longlitude und m_frequency direkt hintereinander. mein std::setw(11) scheint hier getrost ignoriert zu werden. Was muss ich denn dann da verwenden, damit mein double gechnitten wird?

Werner Salomon

Nein, das ist gar nicht simple! iostreams sind dafür gemacht Zahlen und Worte aus Zeichenfolgen so zu lesen, wie Menschen das auch tun. Und bei einem Ausdruck wie

167.180000114.30

kann kein Mensch ohne Zusatzinformation wissen, dass damit 167.180000 und 114.30 gemeint ist.

Ok - Du meinst, dass inklusive des führenden Leerzeichens die Longitude 11 Stellen belegt. iostreams sind auch dafür gemacht, dass man sie praktisch beliebig erweitern kann. Hier wäre mein Vorschlag:

#include <iostream>
#include <sstream> // basic_stringbuf
#include <iomanip> //setw
#include <string>
#include <vector>

// --   Schaltet den Streambuf um und wieder zurück
//      Bem.: falls boost verfügbar, kann diese struct durch 
//          boost::io::basic_ios_rdbuf_saver< char > ersetzt werden
//          erfordert: #include <boost/io/ios_state.hpp>
struct StreambufSwitch // : public boost::noncopyable
{
    StreambufSwitch( std::basic_ios< char >& strm, std::streambuf* sb )
        : m_strm( strm )
        , m_sb_old( m_strm.rdbuf( sb ) )
    {}
    ~StreambufSwitch()
    {
        m_strm.rdbuf( m_sb_old );
    }
private:
    std::basic_ios< char >& m_strm;
    std::streambuf* m_sb_old;
    StreambufSwitch( const StreambufSwitch& );
    StreambufSwitch& operator=( const StreambufSwitch& );
};

// --   liest einen Typ aus einer vorgegebenen Anzahl von Zeichen vom Stream
//      z.B.: int i1, i2; cin >> setw(2) >> readWidth( i1 ) >> i2 >> ...;
//      liest aus "21346 usw.": i1 = 21, i2 = 346, usw.
template< typename T >
struct ConstrainWidthReader
{
    typedef StreambufSwitch basic_ios_rdbuf_saver;
    //typedef boost::io::basic_ios_rdbuf_saver< char > basic_ios_rdbuf_saver;

    ConstrainWidthReader( T& value ) : m_value( value ) {}
    friend std::istream& operator>>( std::istream& in, const ConstrainWidthReader& x )
    {
        const int w = in.width( 0 );
        std::vector< char > chars( w < 0? 0: w );
        if( w <= 0 || in.read( &chars[0], std::streamsize( chars.size() ) ) )
        {   
            // vorgegebene Anzahl 'w' Bytes in einen basic_stringbuf kopieren
            std::basic_stringbuf< char > buf( std::string( chars.begin(), chars.end() ) );
            std::ios_base::iostate state = in.rdstate();
            {
                basic_ios_rdbuf_saver sb_saver( in, &buf );
                if( !(in >> x.m_value) ) // Datum aus dem basic_stringbuf lesen
                    state |= std::ios_base::failbit;
            }
            in.setstate( state );   // Status wieder übernehmen, da rdbuf() diesen löscht
        }
        return in;
    }
private:
    T& m_value;
};
template< typename T >  // Factoryfunktion für ConstrainWidthReader< T >
ConstrainWidthReader< T > constrain_width( T& value )
{
    return ConstrainWidthReader< T >( value );
}

// -- und die Anwendung in na_Entry:
std::istream& operator>>( std::istream& in, na_Entry& e )
{   //  Format:                                         12345678901
    //      "MCMURDO STATION         NGD  VOR -77.865000 167.180000114.30H" // Beispiel
    //       |12345678901234567890123<->  <-> <-  lat -><-  long -><-fr->|
    //       ||                      |    |   |         |          |     +-- ignore this one
    //       ||                      |    |   |         |          +-- frequency (double)
    //       ||                      |    |   |         +-- longitude (double begrenzt auf 11 Stellen!)
    //       ||                      |    |   +-- latitude (double)
    //       ||                      |    +-- type (string begrenzt auf Länge 4)
    //       ||                      +-- name (string)
    //       |+-- ignoriere 23 zeichen
    //       +-- fullname<unused> (string, 1 ?? zeichen)
    //
    char h; // für das 'H' am Ende
    return (in >> std::setw(1) >> e.m_fullname).ignore(23) >> e.m_name >> std::setw(4) >> e.m_type 
        >> e.m_latitude >> std::setw(11) >> constrain_width( e.m_longitude ) >> e.m_frequency >> h;
}

Die Konstruktion hat den Vorteil, dass das identische Streamobjekt zum Einlesen des Wertes benutzt wird. Damit bleiben auch z.B. alle lokalen Einstellungen (std::locale) erhalten.

Gruß
Werner

campinge

oha, soviel zum thema "simpel" o.O

Ich hatte anfangs schon überlegt aus dem m´double m_longlitude einfach einen string zu machen. Ist zwar nicht wirklich elegant, aber wäre natürlich einfacher zu Handhaben gewesen.
Das die Idee keine gute war durfte ich dann beim ersten Testlauf direkt feststellen, da m_longlitude ja nicht immer 11-stellig ist, sondern auch kleiner sein kann (7.654321 z.B)
Mit deinem code läufts jetzt allerdings prime durch. 17 Sekunden im Debug-mode
wiedermals vielen lieben dank!

campinge

Hallo!

Da bin ich wieder!
Aus kompatibilitätsgünden habe ich mich mittlerweile dazu entschlossen, bei den "quellfiles" auf einen anderen Anbieter umzusteigen, die vorherigen waren einfach zu bunt gemischt. (.txt, .dat, .xml) letztere waren sogar in sich so werwunden, dass es schon ein meisterstück gewesen wäre auch nur ansatzweise etwas dafür zu schreiben.

Anyway. Mit dem jetztigen klappt es eigentlich wunderbar, bis auf eine sache:

Beim Einlesen habe ich ei file, indem mehrere strings an verschiedenen stellen vorkommen. Mit einem könnte ich ja umgehen, aber hier grübele ich schon eine ganze Weile lang nach.

std::istream& operator>>( std::istream& in, aw_Entry& e )
{   //  Format:
    //      "MES,1AW1  ,001,ORNAT, 20.000000,  25.000000, 0, 98, ,L" // Beispiel
    //       |	 |		|	|	   |		   |		  |	 |	| |
	//       |	 |		|	|	   |		   |		  |	 |	| +-- m_type (string)
	//       |	 |		|	|	   |		   |		  |	 |	+--(uberspringen)
	//       |	 |		|	|	   |		   |		  |	 +--m_number3 (int)
	//       |	 |		|	|	   |		   |		  +--m_number2 (int)
	//       |	 |		|	|	   |		   +--m_longlitude (double)
	//		 |	 |		|	|	   +--m_latitude (double)
	//		 |	 |		|	+--m_fix (string)
    //       |   |		+--m_number (int)
    //       |   +--m_airway (string)
    //       +--m_country(string)
    //
	return					in >> std::ws >> 
							e.m_country >> Char<','> >>
							e.m_airway >> Char<','> >> 
							e.m_number >> Char<','> >>
							e.m_fix >> Char<','> >>
							e.m_latitude >> Char<','> >> 
							e.m_longitude >> Char<','> >>
							e.m_number2 >> Char<','> >>
							e.m_number3 >>  Char<','> >>  Char<','> >>
							e.m_type;
}

hoffe man kann es erkennen. Es landet halt einfach wieder mehr im ersten string als geplant. diverses abändern mit getline habe ich nicht wirklich hinbekommen, da vor dem ersten char ja kein Char<','> stand...

Dabei habe ich auch direkt noch eine frage: m_latitude und m_longlitude werden ja in jeweils einem double gespeichter. Kann es sein, dass darunter die genauigkeit leidet?
Ich habe vorhin einen Wegpunkt exportiert, der im Ursprungfile 6 Nachkommatellen hat, im erstellten file jedoch nur 4. wie kann das passieren?

Werner Salomon

campinge schrieb:

... Es landet halt einfach wieder mehr im ersten string als geplant. diverses abändern mit getline habe ich nicht wirklich hinbekommen, da vor dem ersten char ja kein Char<','> stand...

Das geht mit getline ganz gut, eben lesen bis ',' - folgendes liest zumindest die Beispielzeile einwandfrei:

struct aw_Entry
{
    std::string m_country;
    std::string m_airway;
    int m_number;
    std::string m_fix;
    double m_latitude;
    double m_longitude;
    int m_number2, m_number3;
    char m_type;
};

std::istream& operator>>( std::istream& in, aw_Entry& e )
{   //  Format:
    //      "MES,1AW1  ,001,ORNAT, 20.000000,  25.000000, 0, 98, ,L" // Beispiel
    //       |   |      |   |       |           |         |  |  | |
    //       |   |      |   |       |           |         |  |  | +-- m_type (string)
    //       |   |      |   |       |           |         |  |  +--(uberspringen)
    //       |   |      |   |       |           |         |  +--m_number3 (int)
    //       |   |      |   |       |           |         +--m_number2 (int)
    //       |   |      |   |       |           +--m_longlitude (double)
    //       |   |      |   |       +--m_latitude (double)
    //       |   |      |   +--m_fix (string)
    //       |   |      +--m_number (int)
    //       |   +--m_airway (string)
    //       +--m_country(string)
    //
    return  getline( getline( in >> std::ws, e.m_country, ',' ) >>
                  e.m_airway >> Char<','> >>   // Bem.: zw. 'airway' und dem ',' muss mindestens ein Space stehen!
                  e.m_number >> Char<','>,
                  e.m_fix, ',' ) >>
                  e.m_latitude >> Char<','> >>
                  e.m_longitude >> Char<','> >>
                  e.m_number2 >> Char<','> >>
                  e.m_number3 >>  Char<','> >>  Char<','> >>
                  e.m_type;
}

Falls der Text 'airway' länger wird und auch bis zum Komma reichen kann, muss das noch so angepasst werden:

return  getline( getline( getline( in >> std::ws, e.m_country, ',' ),
                  e.m_airway, ',' ) >>
                  e.m_number >> Char<','>,
                  e.m_fix, ',' ) >>
                  e.m_latitude >> Char<','> >>
                  e.m_longitude >> Char<','> >>
                  e.m_number2 >> Char<','> >>
                  e.m_number3 >>  Char<','> >>  Char<','> >>
                  e.m_type;

allerdings stehen dann in 'm_airway' auch ggf. alle Leerzeichen bis zum ',' drin. Wenn das stört, so solltest Du diese innerhalb der Lesefunktion noch beseitigen.

campinge schrieb:

Dabei habe ich auch direkt noch eine frage: m_latitude und m_longlitude werden ja in jeweils einem double gespeichter. Kann es sein, dass darunter die genauigkeit leidet?
Ich habe vorhin einen Wegpunkt exportiert, der im Ursprungfile 6 Nachkommatellen hat, im erstellten file jedoch nur 4. wie kann das passieren?

double reicht i.A. völlig aus. Wenn Du im erstellten File nur noch 4 Leerzeichen siehst, so liegt das nicht an der mangelnden Genauigkeit, sondern am Ausgabeformat. Im ostream kann man einen Wert für die Stellen bei Fließkommazahlen angeben. Dieser steht per Default auf 6. Bei zwei VK-Stellen verbleiben dann immer 4 Nachkommastellen.

Schau Dir mal die Manipulatoren 'setprecision' und 'fixed' an.

Gruß
Werner

campinge

Sorry, dass ich mich erst nach so langer Zeit wieder melde.
Erstmal Danke!

Leider habe ich festgestellt, dass wirklich nicht immer ein Leerzeichen zwischen 'airway' und ',' steht.
Ich hab mal selber ein bischen dran herumgebastelt und das ist dabei herausgekommen:

return  ( getline( getline( getline( in >> std::ws, e.m_country, ',' ) >>
				  std::ws, e.m_airway, ',') >>
                  e.m_number >> 
				  Char<','>, e.m_fix, ',' ) >>
                  e.m_latitude >> Char<','> >>
                  e.m_longitude >> Char<','> >>
                  e.m_number2 >> Char<','> >>
                  e.m_number3 >> Char<','>).ignore(3);

damit liest er alles wunderbar ein, leider aber, wie bei dir, auch die Leerzeichen. Irgendwie bekomme ich die nicht raus...

Die Ausgabegenauigkeit habe ich übrigends hinbekommen. Danke für die Links!

Werner Salomon: