Datei in eine std::map einlesen und nach Value sortieren

[out]

engoaona schrieb:

Würde ich nicht so machen. Um die Werte aufzunehmen bietet sich eine std::unordered_map (aka hashtable) an, gibt es seit C++ und ist um einiges schneller.
Sortieren würde ich anders. Das in einem Baum zu tun ist relativ ineffizient.
Ich hätte am Schluss alle Werte in einen std::vector<std::pair<int, std::string*> > reinkopiert und den sortiert.

Danke, die beiden Tipps waren echt gut. Ich die Zeit dadurch noch von 3,5 auf 2,8 Sekunden im Schnitt drücken.
Hier nochmal die Version, für alle die, die es interessiert:

#include <algorithm>
#include <ctime>
#include <fstream>
#include <functional>
#include <iterator>
#include <unordered_map>
#include <string>
#include <utility>
using namespace std;

void create_file( unsigned size )
{
	ofstream file( "test.txt" );
	char key = 'A';
	for(unsigned i=0; i<size; ++i,++key)
	{
		key = ( key <= 'Z' ? key : 'A' );
		file << key << ' ' << rand()%10 << '\n';
	}
}

void read_file( string& content )
{
	ifstream file( "test.txt" );

	file.seekg(0, ios_base::end);
	const unsigned size = file.tellg();
	file.seekg(0, ios_base::beg);

	content.resize( size );
	file.read( &content[0], size );
}

void evaluate_file( string& content, unordered_map<string,unsigned>& evaluation )
{
	replace( content.begin(),content.end(), '\n', ' ' ); 

	string::size_type start = content.find_first_not_of( ' ', 0 );
	string::size_type stop  = content.find( ' ' );

	while( string::npos!=start )
	{
		const string& key = content.substr(start,stop-start);

		start = content.find_first_not_of( ' ', stop  );
		stop  = content.find             ( ' ', start );

		if( string::npos==start )
			break;

		evaluation[key] += stoi( content.substr(start,stop-start) );

		start = content.find_first_not_of( ' ', stop  );
		stop  = content.find             ( ' ', start );
	}
}

void sort_by_value( const unordered_map<string,unsigned>& evaluation, vector<pair<const string*,unsigned>>& evaluation_sorted )
{
	for( auto it=begin(evaluation); it!=end(evaluation); ++it )
	{
		evaluation_sorted.push_back( make_pair( &(it->first), it->second ) );
	}

	sort( begin(evaluation_sorted), end(evaluation_sorted), 

		[]( const pair<const string*,unsigned>& lhs,  const pair<const string*,unsigned>& rhs )
		{
			return lhs.second>rhs.second;
		}
	);
}

int main()
{
	srand( time(NULL) );
	create_file( 20 * 1024 * 1024 ); // Eine Zeile hat 5 Zeichen (Windows) ---> 100 MB

	string content;
	read_file( content ); // Einlesen: 0,18 Sekunden

	unordered_map<string,unsigned> evaluation;
	evaluate_file( content, evaluation ); // Parsen: 2,6 Sekunden 

	vector<pair<const string*,unsigned>> evaluation_sorted;
	sort_by_value( evaluation, evaluation_sorted ); // Nach Value sortieren: 16 us 
}

Nebenbei noch:
Compiler: MSVC 2012
Optimierung: /O2
BS: Win7 64-bit
CPU: i5-2500
RAM: 8GB

Von 12,5 auf 2,8 Sekunden, ich glaub schneller ist es nicht mehr machbar. Und gerade sehe ich, dass ich mir angewöhnen sollte, alle C++11 Features zu nutzen, wenn ich schon eines nutz .

[out]

Kellerautomat schrieb:

std::string ist imo ein ziemlich ungeeigneter Datentyp fuers Parsen. Probiers mal mit eine ref_string Klasse, damit sparst du dir Kopien.

Gute Idee, gleich mal teste.

[cooky451]

out schrieb:

cooky451 schrieb:

out schrieb:

1. Die zu jedem Namen gehörigen Werte aufaddieren.
2. Das Ganze absteigend nach den Werten sortieren.

Warum liest du dann nicht sofort in eine map?

Ich kann dir nicht ganz folgen, cooky451. Was meinst du genau?

Du brauchst doch offensichtlich keine Zuordnung Name->Nummer, sondern nur Nummer->Name. Wenn du das einfach in eine (multi)map<unsigned, std::string> lesen würdest, ist alles sofort sortiert so wie du es haben willst und du musst nicht sinnloserweise irgendwelche Paare switchen. Irgendwas muss ich falsch verstanden haben, denn das macht so genau 0 Sinn.

[Michael E.]

cooky451: Die Punkte eines Namens muss man aufsummieren.

[out]

cooky451 schrieb:

out schrieb:

cooky451 schrieb:

out schrieb:

1. Die zu jedem Namen gehörigen Werte aufaddieren.
2. Das Ganze absteigend nach den Werten sortieren.

Warum liest du dann nicht sofort in eine map?

Ich kann dir nicht ganz folgen, cooky451. Was meinst du genau?

Du brauchst doch offensichtlich keine Zuordnung Name->Nummer, sondern nur Nummer->Name. Wenn du das einfach in eine (multi)map<unsigned, std::string> lesen würdest, ist alles sofort sortiert so wie du es haben willst und du musst nicht sinnloserweise irgendwelche Paare switchen. Irgendwas muss ich falsch verstanden haben, denn das macht so genau 0 Sinn.

ALle Nummer, die zu einem Namen gehören, muss ich aufaddieren. Danach muss ich alle gewonnenen Summen absteigend sortieren. Wie würdest du dann die Nummern aufaddieren?

[Werner Salomon]

Hallo out,

auch wenn ich folgenden Code niemanden empfehlen würde, so ersetze doch damit bitte Deine read_file -Funktion und poste uns die Ergebnisse Deiner Zeitmessung.

#include <fstream>
#include <iostream>
#include <map>
#include <string>
#include <locale>

namespace special
{
    struct map_reader
    {
        map_reader( std::map< std::string, unsigned >& destination )
            : destination_( &destination )
        {}
        std::map< std::string, unsigned >* destination_;
    };

    template< typename E, typename Traits >
    std::basic_istream< E, Traits >& operator>>( std::basic_istream< E, Traits >& in, map_reader mr )
    {
        std::basic_istream< E, Traits >::sentry ok( in );
        if( ok )
        {
            std::ios_base::iostate state = std::ios_base::goodbit;
            try
            {
                const std::ctype< E >& ctype_ = std::use_facet< std::ctype< E > >( in.getloc() );
                for(;;)
                {
                    // --   skip leading whitespace
                    Traits::int_type m = in.rdbuf()->sgetc();
                    for( ;; m = in.rdbuf()->snextc() )
                    {
                        if( Traits::eq_int_type( m, Traits::eof() ) )
                        {
                            state |= std::ios_base::eofbit;
                            break;
                        }
                        else if( !ctype_.is( std::ctype_base::space, Traits::to_char_type(m) ) )
                            break;    // kein whitespace
                    }
                    if( state != std::ios_base::goodbit )
                        break; // EOF

                    // --   read text
                    std::basic_string< E > txt(1,Traits::to_char_type(m));
                    for( m = in.rdbuf()->snextc();; m = in.rdbuf()->snextc() )
                    {
                        if( Traits::eq_int_type( m, Traits::eof() ) )
                        {
                            state |= std::ios_base::eofbit | std::ios_base::failbit;
                            break;
                        }
                        const E c = Traits::to_char_type(m);
                        if( ctype_.is( std::ctype_base::space, c ) )
                            break;
                        txt.append( 1, c );
                    }
                    if( state != std::ios_base::goodbit )
                        break; // fail

                    // --   skip leading whitespace before number
                    for( m = in.rdbuf()->snextc();; m = in.rdbuf()->snextc() )
                    {
                        if( Traits::eq_int_type( m, Traits::eof() ) )
                        {
                            state |= std::ios_base::eofbit | std::ios_base::failbit;
                            break;
                        }
                        else if( !ctype_.is( std::ctype_base::space, Traits::to_char_type(m) ) )
                            break;    // kein whitespace
                    }
                    if( state != std::ios_base::goodbit )
                        break; // fail

                    // --   read number
                    unsigned val = 0;
                    bool read_some = false;
                    for( ;; m = in.rdbuf()->snextc(), read_some = true )
                    {
                        if( Traits::eq_int_type( m, Traits::eof() ) )
                        {
                            state |= std::ios_base::eofbit;
                            break;
                        }
                        const E c = Traits::to_char_type( m );
                        if( !ctype_.is( std::ctype_base::digit, c ) )
                            break;
                        (val *= 10) += int(c - '0');
                    }
                    if( !read_some )
                    {
                        state |= std::ios_base::failbit;
                        break;
                    }
                    mr.destination_->operator[]( txt ) += val; // <== hier wird der Wert addiert
                }
            }
            catch( ... )
            {
                state |= std::ios_base::badbit;
                if( in.exceptions() & std::ios_base::badbit )
                    throw;
            }
            in.setstate( state );
        }
        return in;
    }
}

void read_file( std::map<std::string,unsigned>& content )
{
    using namespace std;
    ifstream file( "test.txt" );
    if( !(file >> special::map_reader( content )) )
        cerr << "Fehler beim Lesen von 'content'" << endl;
}

auf meinem PC schlägt er die Variante von Michael um den Faktor 2.

Gruß
Werner

[out]

Hallo Werner

Meine beste Version, welche ich zuletzt gepostet habe, benötigt 2,8 Sekunden. Verwende ich deine read_file -Funktion, dauert er nur noch 1,39 Sekunden . Und wenn ich bei dir jetzt noch std::map durch std::unordered_map ersetze, bin ich bei unglaublichen 1,12 Sekunden :). Danke für die Hilfe, die Zeit ist echt der Hammer, auch wenn ich den Quellcode nicht ganz verstehe. Allerdings möchte ich noch Nachfrage, wieso du diesen Code niemandem empfehlen würdest?

[Michael E.]

Was soll ich sagen, Werner ist einfach ein Gott mit den C++-Streams.

Dann muss ich meine Aussage wohl korrigieren: C++-Streams sind unglaublich langsam, wenn man sie so naiv wie ich verwendet

[Eisflamme]

Dachte ich mir's doch.

Habe mir den Code wieder abgelegt. Diesmal habe ich ctype dazugelernt, das ist ja auch ein wirklich praktisches Ding. V.a. wenn man zeichenweise Hexadezimal- oder Fließkommazahlen lesen möchte, bietet es sich wohl auch an.

[Werner Salomon]

Hallo alle,

out schrieb:

Allerdings möchte ich noch nachfragen, wieso du diesen Code niemandem empfehlen würdest?

Geschwindigkeit ist nicht alles. Die erste Variante von out - ganz klassisch:

//
    string key;
    unsigned val;
    while( file >> key >> val ) { // usw.

.. kann jeder mit ein wenig Erfahrung in der Anwendung von istream in Minuten hinschreiben. Dafür erhält man einen funktionsfähigen, einfachen, sicheren und ausbaufähigen Programmcode. So wäre eine Änderung des Typs von 'val' oder ein anderes Zahlenformat, wenn es z.B. Fließkommazahlen wären, kein Problem.

Die Variante von Michael war dann schon anders. Zunächst springt einem der Kommentar ins Auge:

char text[80];   // Hast du eine garantierte maximale Zeilenlänge?

Aha - was ist, wenn die Zeilen länger werden? Vielleicht nicht in dieser und der nächsten Version, aber dann irgendwann?
Anschließend bekomme ich beim Compilieren drei Sicherheitswarnungen um die Ohren gehauen. Ok - ist ja nur zum Test. Und dann packe ich die Datei 'test.txt' in ein falsches Directorie und .. crash! Nach 5 Minuten debuggen wird klar: fclose(fp) hätte in den Scope if(fp){.. gehört. fp darf nicht =0 sein, wenn fclose gerufen wird. Mit dem RAII der streams passiert sowas einfach nicht.

Meine Variante sollte sicher sein, aber das Risiko, dass dort noch ein Fehler in der Fehlerbehandlung ist, ist hoch. Die Variante ist ausgelutscht - ein paar Beispiele:

- Zeile 56:

txt.append( 1, c );

.. warum nicht ein txt.push_back(c) ? Nun, weil dass in der von mir verwendeten Dinkumware C++-Lib signifikant langsamer ist. Das muss überhaupt nicht so sein, dass ist einfach so.

- Zeile 45

// --   read text
                    std::basic_string< E > txt(1,Traits::to_char_type(m));
                    for( m = in.rdbuf()->snextc();; m = in.rdbuf()->snextc() )

müsste sauber heißen:

// --   read text
                    std::basic_string< E > txt;
                    for( m = in.rdbuf()->sgetc();; m = in.rdbuf()->snextc() )

hier mache ich mir zunutze, dass im Vorfeld bereits festgestellt wurde, dass m weder EOF noach ein White-Space-Character ist. Man kann es also direkt in den txt übernehmen. Aber was, wenn der Code noch mal überarbeitet wird? Ist das dann auch noch klar?

- Zeile 62

// --   skip leading whitespace before number
                    for( m = in.rdbuf()->snextc();; m = in.rdbuf()->snextc() )

gleiches Spiel wie oben. Ich überspringe frech ein Zeichen, da ich hier noch weis, es gehört nicht dazu.

Um es kurz zu machen, kein 'schöner' Code, den man gern bearbeitet. Und er ist sehr speziell auf das Bedürfnis von out zugeschnitten. So z.B. das Einlesen des unsigned- Wertes. Das ist zum Glück das einfachste Zahlenformat, was man sich vorstellen kann. Einen möglichen Overflow habe ich hier mal großzügig ignoriert.

Aber wo geht jetzt die Zeit von der klassischen Variante 1 hin?
Wie Eisflamme schon erwähnte, wird mit jedem Streaming-Operator-Aufruf ein sentry-Objekt erstellt, das wäre jetzt nicht so schlimm, aber das sentry holt sich mit use_facet<>() die ctype-Facette. Wobei hier eine Kopie des std::locale-Objekts erzeugt wird (Methode std::ios_base::getloc()). Was auch keine großen Datenmengen bewegt, denn es funktioniert in meiner C++-Lib via Referenz-Counting, was aber Multi-Thread-Sicher implementiert ist - und das kostet!
Im eigentlichen Lesecode wird dann nochmal use_facet aufgerufen - mit std::ctype<> beim string lesen und mit std::num_get<> beim Zahl lesen. D.h. man kommt pro Datensatz auf 4 use_facet-Aufrufe.
Erschwerend kommt hier hinzu, dass die von out erzeugt Datei den GAU für das Streaming darstellt, da alle Werte nur aus einem einzigen Zeichen bestehen. Das obige betrifft ja immer den Overhead pro Wert, und der macht sich umso mehr bemerkbar, umso weniger Zeichen pro Wert die Datei füllen. Oder anders ausgedrückt - eine Datei gleicher Größe mit mehr Zeichen pro Wert, hätte weniger Werte und damit auch weniger use_facet-Aufrufe.
Ja und dann ist da noch noch die num_get-Implementierung der Dinkumware-C++-Lib. C++ sei Dank ist ja der genaue Zahlentyp, der da eingelesen wird, schon seit der Compilezeit bekannt - und tief unten in den Niederungen von num_get wird ein scanf-Format-String zusammen gebaut und mit diesem ein sscanf gerufen. Da braucht man sich wirklich nicht wundern, wenn das Gesamtpaket langsamer ist als die C-Version.

Und so kommt einiges zusammen, was das Streamen 'langsam' macht.
Btw.: Ich war bisher der Meinung, dass das Einlesen von 1MB Textdatei in unter einer Sekunde flott genug ist. Ich habe schon C-Code gesehen, der dafür eine ganze Minute gebraucht hat. Ergo sind 12,5s für 100MB doch eine stolze Leistung - oder nicht?

Michael E. schrieb:

Dann muss ich meine Aussage wohl korrigieren: C++-Streams sind unglaublich langsam, wenn man sie so naiv wie ich verwendet

.. sooo langsam nun auch wieder nicht. Und nicht naiv, sondern einfach, sicher und ausbaufähig.

Gruß
Werner

... und das war mein 2000.Beitrag als registrierter User

[cooky451]

Kellerautomat schrieb:

std::string ist imo ein ziemlich ungeeigneter Datentyp fuers Parsen. Probiers mal mit eine ref_string Klasse, damit sparst du dir Kopien.

Das ist so alles viel zu langsam, weil man dauernd strings kopiert.

Ich behaupte mal das ganze geht mit einem eigenen Parser und ~4MB großen Cache locker in 1/10 Sekunde. Wenn nicht noch schneller. Ich habe leider keine Zeit das gerade zu bauen, aber nur so als Idee, wenn du wirklich Performance willst.

Siehe auch http://www.c-plusplus.net/forum/294002-10, nicht besonders schön, aber du siehst die Grundidee.

[Eisflamme]

cooky:
Wieso ist denn die Stream-Variante langsamer? Ich finde nicht, dass man den Ansatz in dem von Dir verlinkten Post sieht. Du benutzt Schleifen und dann mystische Funktionen wie parseFloat. Hier iterieren wir ein einziges Mal über die ganze Datei. Was imo halt langsam sein könnte ist das Hinzufügen von Zeichen zu einem string, wie hast Du das denn gelöst? Oder an welcher Stelle ist Deine Variante optimierter?

[cooky451]

Da ich momentan kein Internet bei mir habe und nur in der Uni schreiben kann, kann ich das jetzt leider schlecht demonstrieren. Aber die Grundidee ist, dass der Parser nur zwei Pointer hat (begin, end) und darauf wird dann die Gleichheit verglichen. Das spart jegliche Kopie. (Denn genau genommen muss man bei dieser Testmap ja nur 26 Strings erstellen, und die anderen x-tausend müssen nur verglichen werden.)
parseFloat etc. rufen nur C Funktionen auf wenn ich mich richtig erinnere, und sind ja auch uninteressant hier. Nur parseString sollte halt ganz wesentlich schneller sein. Die Implementierung ist eigentlich auch denkbar einfach, einfach von !isspace nach isspace lesen.

[Werner Salomon]

cooky451 schrieb:

.. die Grundidee ist, dass der Parser nur zwei Pointer hat (begin, end) und darauf wird dann die Gleichheit verglichen. Das spart jegliche Kopie.

nicht ganz. Da ist mindestens eine Kopie, und die ist 100MByte groß. Und genau das ist das Problem. Um die von Dir anvisierten 0,1s zu schaffen, müsste allein Deine Festplatte eine Lesefrequenz von >1000MB/s haben. Mir ist nicht bekannt, dass es so was gibt. Zumindest nicht als handelsüblicher PC.

Ich benötige zum Parsen mit meiner Variante 1,6s auf einem schnellen PC mit schneller Festplatte. Nur zum Laden der identischen Datei in den Speicher (egal ob std::string, vector<char> oder char*) benötige ich auf dem selben System ebenfalls 1,6s. D.h. das eigentliche Parsen geht im Lesen unter. Wenn Dein Parser anfängt, ist meiner schon fertig.

Gruß
Werner