[C++] - Γρήγορη ανάγνωση μεγάλων .csv

παπι · 22 Μαΐου 2014

Βασικα, γιατι δεν δοκιμαζεις κανενα csv parser;

ΥΓ: Απορω πως δεν το σκεφτικα πιο πριν.... Απορω..

migf1 · 22 Μαΐου 2014

...

Χρόνοι:

Χωρίς add στην βάση - 1.7secs

Με add στην βάση - 5.7secs

Νομίζω είναι μια χαρά. Παρ'όλα αυτά, αν βλέπετε χώρο για βελτιώση πείτε.

Η βάση είναι κάποιο map, θα δοκιμασω αυριο να δω αν μπορω να κανω καποιου ειδους reserve μηπως βελτιωθεί λιγο ακόμη.

Ευχαριστώ.

Βασικά το 1.7 για 100Mb μου φαίνεται μεγάλο εμένα, εκτός αν είναι uncached. Σε μένα cached μου το διαβάζει σε 0.35 κι είναι πανάρχαιο το test bed μηχανάκι μου (btw, δες και διαφορά μεταξύ ifstream.read() και stringstrem << file.rdbuf()... μισός χρόνος... το rdbuf() διαβάζει έναν-έναν χαρακτήρα, ενώ το ifstream.read() αν το θυμάμαι καλά καλεί την fread() εσωτερικά, άρα όταν μπορεί διαβάζει μονοκόμματα)

load file using stringstream << f.rdbuf(): 0.78125 secs (110767105 bytes)
load file using ifstream.read(): 0.375 secs (110767105 bytes)

Κώδικας:

#include <iostream>
#include <fstream>
#include <sstream>
#include <chrono>

using namespace std::chrono;

int main()
{
	std::string fname( "test1.csv" );
	std::ifstream f;
	int fsize;
	char* buf;
	steady_clock::time_point tstart;
	duration<double> elapsed;

	std::cout << "load file using stringstream << f.rdbuf(): ";
	std::stringstream buffer;
	tstart = steady_clock::now();
	f.open( fname, std::ios::in | std::ios::ate );
	if ( f.is_open() ) {
		fsize = f.tellg();
		f.seekg(0, std::ios::beg);
		buffer << f.rdbuf();
		f.close();
	}
	elapsed = steady_clock::now() - tstart;
	std::cout << elapsed.count() << " secs (" << fsize << " bytes)\n";

	std::cout << "load file using ifstream.read(): ";
	tstart = steady_clock::now();
	f.open( fname, std::ios::in | std::ios::ate );
	if ( f.is_open() )
	{
		buf = new char[fsize];
		fsize = f.tellg();
		f.seekg(0, std::ios::beg);
		f.read(buf, fsize);
		f.close();
	}
	elapsed = steady_clock::now() - tstart;
	std::cout << elapsed.count() << " secs (" << fsize << " bytes)\n";

	std::cin.get();

	return 0;
}

Επίσης, κοντεύει να ξημερώσει και δεν τραβάω άλλο, οπότε να μη βλέπω το προφανές, αλλά στο loop γιατί έχεις if και ισότητας και ανισότητας με το ','... και γενικώς γιατί τα έχεις χωρίς έχεις else τα conditions?

bnvdarklord · 22 Μαΐου 2014

το rdbuf() διαβάζει έναν-έναν χαρακτήρα, ενώ το ifstream.read() αν το θυμάμαι καλά καλεί την fread() εσωτερικά, άρα όταν μπορεί διαβάζει μονοκόμματα)

f.read κάνω όλο το αρχείο σε ενα char*, και μετά το διαβάζω.

Επίσης, κοντεύει να ξημερώσει και δεν τραβάω άλλο, οπότε να μη βλέπω το προφανές, αλλά στο loop γιατί έχεις if και ισότητας και ανισότητας με το ','... και γενικώς γιατί τα έχεις χωρίς έχεις else τα conditions?

Nαι, γιατι ήταν αργά και επειδη στην αρχή το ειχα γραψει πιο πολυπλοκα. Τα εχω με else κανονικα τωρα.

Οι χρονοι σημερα περιέργως ειναι λιγο διαφορετικοι(ε δεν νομιζω να φταινε τα else που εφτιαξα!)

0.91 χωρίς προσθήκη στην βάση, 0.5 χωρις καθολου parsing(μονο την μονοκομματη αναγνωση στο char*), αλλά περιέργως 5.7 οπως και χθες με την εισαγωγή στην βάση. Δεν εχω ιδεα πως αλλαξε.

Εβαλα και το ios::ate αντι για να κανω seek στο τελος, αλλα δεν βελτιώθηκε ιδιαιτερα. Αλλες διαφορές με το δικό σου δεν βλέπω.

migf1 · 23 Μαΐου 2014

f.read κάνω όλο το αρχείο σε ενα char*, και μετά το διαβάζω.

Nαι, γιατι ήταν αργά και επειδη στην αρχή το ειχα γραψει πιο πολυπλοκα. Τα εχω με else κανονικα τωρα.

Οι χρονοι σημερα περιέργως ειναι λιγο διαφορετικοι(ε δεν νομιζω να φταινε τα else που εφτιαξα!)

0.91 χωρίς προσθήκη στην βάση, 0.5 χωρις καθολου parsing(μονο την μονοκομματη αναγνωση στο char*), αλλά περιέργως 5.7 οπως και χθες με την εισαγωγή στην βάση. Δεν εχω ιδεα πως αλλαξε.

Εβαλα και το ios::ate αντι για να κανω seek στο τελος, αλλα δεν βελτιώθηκε ιδιαιτερα. Αλλες διαφορές με το δικό σου δεν βλέπω.

Το ate δεν νομίζω να έχει κάποια ιδιαίτερη διαφορά συγκριτικά με το χειροκίνητο fseek(0, SEEK_END). Δεν το ΄χω ψάξει, αλλά λογικά την ίδια δουλειά πρέπει να κάνει (δηλαδή να καλεί την fseek() μόλις ανοίγει το αρχείο).

Γενικώς το i/o είναι πολύ δύσκολο να μετρηθεί με αξιοπιστία, ακόμα και στο ίδιο μηχάνημα (όπως διαπίστωσες ήδη). Τα ίδια συμβαίνουν και σε μένα, π.χ. σήμερα το ifstream.read() μου διαβάζει το cached αρχείο των 105Mb σε 0.125 secs, ενώ χτες έκανε πάνω από 0.350 secs.

Οπότε από τη στιγμή που κατά μέσο όρο έχεις ικανοποιητικό αποτέλεσμα, το αφήνεις. Αλλιώς θα πρέπει να χρησιμοποιήσεις το low-level Ι/Ο API της πλατφόρμας στην οποία δουλεύεις που σίγουρα θα είναι ταχύτερο, αλλά δεν θα είναι portable ο κώδικάς σου.

Τώρα, το parsing στη μνήμη μπορεί να μετρηθεί πιο αξιόπιστα, γιατί επηρεάζεται από λιγότερους εξωγενείς παράγοντες από ότι το I/O. Αυτό όμως που λες για τα 5.7 secs για το parsing και την εισαγωγή στη βάση, δεν μπορούμε εμείς από εδώ να πούμε κάτι, γιατί δεν έχουμε ιδέα για ποια βάση μιλάς, τι είδους API είναι αυτό που χρησιμοποιείς για να της περάσεις μέσα τα παρσαρισμένα data, κλπ (και να είχαμε δηλαδή, πάλι δεν θα μπορούσαμε να προσφέρουμε κάτι το αξιόπιστο).

Όσο πιο πολύ θες να το ψάξεις, τόσο πιο πολύ μεγαλώνει η ανάγκη να χρησιμοποιήσεις έναν κανονικό profiler (αντί για τα μπακαλίστικα που κάνουμε εδώ με το cpu clock).

Όμως, δες κάτι άλλο. Έχεις τσεκάρει αν τα data που παρσάρεις στη μνήμη είναι εντάξει; Ειδικά προς το τέλος τους; Ρωτάω, γιατί στον C++ κώδικα που πόσταρα χτες, εχω ΞΕΧΑΣΕΙ να μηδενίσω το τελευταίο byte του buffer μετά την ανάγνωσή του από το αρχείο. H f.read() δεν το κάνει αυτόματα. Στον C κώδικα που έχω δώσει, το κάνω όμως (απλά στον C++ κώδικα το ξέχασα).

Χωρίς να είναι μηδενισμένο το τελευταίο byte του buffer, δεν έχουμε την παραμικρή ιδέα που σταματάει το loop που κάνει το parsing... αν το πρόσεξες, το conditional που έχω βάλει είναι μέχρι το *cp να γίνει '\0'. Σε μένα συμπτωματικά σταματάει σωστά, αλλά σε σένα μπορεί και όχι.

Τώρα, πέρα από την εισαγωγή των data που κάνεις στη βάση, αν το υπόλοιπο loop το έχεις όπως στον κώδικά μου, δεν νομίζω πως αξίζει να ασχοληθείς περισσότερο.

Εγώ πάντως, πάλι από περιέργεια, έγραψα C++ κώδικα που χρησιμοποιεί vector of vectors για τις γραμμές και τα fields. Σε δυο παραλλαγές: μια που είναι τελείως unbounded, οπότε κοπιάρουν πράμα από το buffer τελείως δυναμικά μέσα στα vectors, και μια που παρσάρω το buffer στη μνήμη 2 φορές: μια μόνο και μόνο για να μετρήσω πόσες γραμμές έχει, ώστε να κάνω pre-resize το vector των γραμμών, και μια 2η για να βάλω μέσα στις γραμμές τα fields. Αυτό δηλαδή που σου έγραφα σε ένα προηγούμενο post, ότι συνήθως σε συμφέρει να το κάνεις έτσι.

Η διαφορά τους στο δικό μου μηχανάκι (σήμερα ) κυμαίνεται από 3.5 έως 4.0 secs περίπου (πολύ μεγάλη δηλαδή)...

* ---- 2 MEM PASSES ------- */

loading file test1.csv...
(110767105/110767105 bytes): 0.125 secs

parsing loaded data...
(891072 lines): 5.34375 secs

press ENTER...

/* ------- 1 MEM PASS ------- */

loading file test1.csv...
(110767105/110767105 bytes): 0.125 secs

parsing loaded data...
(891072 lines): 8.89063 secs

press ENTER...

Παραμένουν πολύ πιο αργά από τον C κώδικα που έδωσα, εκείνον που κάνει δυναμικά allocate τα fields και τα κοπιάρει μετά στις γραμμές με την strdup(). Αυτό παρσάρει και κοπιάρει σε λιγότερα από 3 secs (αλλά δεν ξέρω γιατί, σήμερα διαβάζει το αρχείο σε υπερδιπλάσιο χρόνο από ότι η f.read() της C++... δλδ ... 0.125 vs 0.375... προχτες διαβάζανε και οι 2 κώδικες στον ίδιο χρόνο, στα 0.375... άλλο ένα δείγμα υποθέτω της "αξιοπιστίας" τωνμετρήσεων σε i/o

)

/* ------ cached with COPY ------- */

loading test1.csv...
109876033 bytes read from file in: 0.359 secs

parsing loaded data...
178214400 bytes (for 891072 lines) created & filled on mem in: 2.875 secs
(97368385 additional bytes copied in all line fields)

cleaning up, please wait... Press ENTER...

Σημείωση: δεν έχει να κάνει με το ότι είναι γραμμένο σε C, θα μπορούσε κάλλιστα να ήταν γραμμένο και σε C++). Έχει να κάνει με το ότι χρησιμοποιεί custom δομές αντί για generic έτοιμες, όπως είναι τα vectors (μπορεί όμως να έχω κάνει καμιά πατατιά στον C++ κώδικα -τον δίνω παρακάτω σε spoiler- γιατί τα C++ skills μου σε καμία περίπτωση δεν είναι εφάμιλλα των C skills μου, οπότε έχε το κι αυτό στο νου σου).

Παραθέτω και τον φρέσκο C++ κώδικα (με το PARSE_TWICE μπορεί να καθορίσεις αν το buffer θα διαβάζεται 2 φορές ή 1... επίσης η f.gcount() επιστρέφει πόσα bytes διαβάστηκαν από το file)...

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <chrono>

using namespace std;
using namespace chrono;

#define PARSE_TWICE    1        // set to 0 to enable totally dynamic insertions

const char* FNAME = (const char*) "test1.csv";

/* -----------------------------------------------------
 * 
 * -----------------------------------------------------
 */
void press_enter( void )
{
	int c;

	cout << "press ENTER... ";
	cout.flush();
	cin.clear();
	while ( '\n' != (c=cin.get()) && EOF != c )
		;
}

/* -----------------------------------------------------
 * 
 * -----------------------------------------------------
 */
int main()
{
	ifstream f;
	size_t fsize = 0;
	char* buf = NULL;
	steady_clock::time_point tstart;
	duration<double> elapsed;

	// read file into buf
	cout << "loading file " << FNAME << "..."; cout.flush();
	tstart = steady_clock::now();
	f.open( FNAME, ios::in | ios::binary | ios::ate );
	size_t sz = 0;
	if ( f.is_open() )
	{
		fsize = f.tellg();
		buf = new char[1+fsize];
		f.seekg(0, ios::beg);
		f.read(buf, fsize);
		sz = f.gcount();       // actual bytes read
		f.close();
	}
	elapsed = steady_clock::now() - tstart;
	buf[sz] = buf[fsize] = '\0';   // NUL terminte buf
	cout << endl << "(" << fsize << "/" <<  sz << " bytes): " << elapsed.count() << " secs\n\n";

#if PARSE_TWICE

	// 1st pass: count lines in buffer
	size_t l = 0;
	for (char* cp = buf; *cp; cp++) {
		if ( '\n' == *cp )
			l++;
	}

	// 2nd pass: parse buf into lines & fields

	cout << "parsing loaded data..."; cout.flush();

	vector< vector<string> > lines;
	lines.resize(l);

	l = 0;
	char *cp  = buf;
	char*  pre = buf;

	tstart = steady_clock::now();
	while ( *cp )
	{
		if ( ',' == *cp ) {
			*cp = '\0';
			lines[l].push_back( pre );
			pre = cp + 1;
		}
		else if ( '\n' == *cp ) {
			*cp = '\0';
			lines[l].push_back( pre );
			pre = cp + 1;
			l++;
		}
		cp++;
	}
	elapsed = steady_clock::now() - tstart;
	cout << endl << "(" << l << " lines): " << elapsed.count() << " secs\n\n";
#else
	// parse buf into lines & fields
	cout << "parsing loaded data..."; cout.flush();
	size_t l = 0;
	char* cp  = buf;
	char* pre = buf;
	vector< vector<string> > lines;
	vector<string> field;

	tstart = steady_clock::now();
	while ( *cp )
	{
		if ( ',' == *cp ) {
			*cp = '\0';
			field.push_back( pre );
			lines.push_back( field );
			pre = cp + 1;
		}
		else if ( '\n' == *cp ) {
			*cp = '\0';
			field.push_back( pre );
			lines.push_back( field );
			pre = cp + 1;
			l++;
		}
		field.clear();
		cp++;
	}
	elapsed = steady_clock::now() - tstart;
	cout << endl << "(" << l << " lines): " << elapsed.count() << " secs\n\n";
#endif

	delete[] buf;

	press_enter();
	return 0;
}

EDIT:

Μόλις είδα γιατί ο C++ κώδικας διαβάζει το αρχείο σε 0.125 secs ενώ ο C σε 0.375 secs. Επειδή, στον C++ το ανοίγω σε binary mode, ενώ στον C το ανοίγω σε text-mode. Το σωστό είναι αυτό που κάνω στον C κώδικα. Δηλαδή, μετράω το size του αρχείου σε binary-mode, μετά το κλείνω και για να το διαβάσω στο buf το ξανανοίγω σε text-mode. Η fseek() δίνει αξιόπιστα αποτελέσματα για το size μόνο όταν ανοίγουμε το αρχείο σε binary-mode (ακόμα κι αυτό όμως έχω την εντύπωση πως είναι compiler dependent).

Αντίθετα επειδή τα .csv είναι text αρχεία, θέλουμε να τα ανοίξουμε σε text-mode, ώστε η fread() να κανονικοποιήσει αυτόματα τα bytes (π.χ. να μετατρέψει σε '\n' τα EOL ανεξάρτητα από το σε ποια πλατφόρμα έχει αποθηκευτεί το αρχείο). Προφανώς αυτό παίρνει παραπάνω χρόνο. Επίσης, θα πρέπει να το κάνουμε και στον C++ κώδικα έτσι (δεν νομίζω δηλαδή πως h f.read() της C++ συμπεριφέρεται διαφορετικά από την fread() της C σε αυτό το συγκεκριμένο... αντίθετα νομίζω πως η f.read() κάνει εσωτερικά call στην fread() ).

Οπότε η fread() (άρα λογικά και η f.gcount() ) επιστρέφουν διαφορετικό πλήθος bytes του αρχείου, ανάλογα με το αν το έχουμε ανοίξει σε binary ή σε text mode.

migf1 · 24 Μαΐου 2014

Ήθελα από χτες να επανέλθω, για να διορθώσω τον C++ κώδικα, μετά το edit που είχα κάνει, αλλά τώρα ευκαίρησα.

Παρατήρησα επίσης πως όντως είχα κάνει πατατιά στο loop με τα πλήρως δυναμικά insertions (1-pass) η οποία τελικά το αδικεί έναντι του 2-passes. Η διαφορά τους είναι της τάξης του 1 μόλις δευτερολέπτου (και όχι των 3.5-4.0 που γράφω παραπάνω) στις 900.000 γραμμές. Εξαρτάται κι από τα data.

Πριν, και έκανα ένα περιττό field.clear() σε κάθε iteration, και δεν ταξινομούσα τα fields ανά γραμμές.

Οπότε ξαναβάζω τον κώδικα, με την ελπίδα πως αυτή τη φορά δεν έχει καμιά χοντράδα μέσα. Σου έβαλα και μια συνάρτηση για να τυπώνει τα παρσαρισμένα data (χρησιμοποιήσέ την μονάχα με μικρά .csv αρχεία, π.χ. των 5-10 γραμμών, αλλιώς θα περιμένεις τον αιώνα τον άπαντα στο τύπωμα ).

Σου έβαλα και σε comments ποια features είναι C++11, όπως είναι π.χ. το chrono (νομίζω, δηλαδή, δεν είμαι και 100% σίγουρος και βαριέμαι τώρα να το κοιτάξω ). Τέλος, το streampos το χρησιμοποιώ ως size_t για τα fsize & sz, αλλά νομίζω πως naturally είναι signed.

Κώδικας:

#include <iostream>
#include <fstream>
#include <vector>
#include <chrono>

using namespace std;
using namespace chrono;		// C++11

#define PARSE_TWICE    0        // set to 0 to enable totally dynamic insertions

const char* FNAME = (const char*) "test1.csv";

/* -----------------------------------------------------
 * 
 * -----------------------------------------------------
 */
void press_enter( void )
{
	int c;

	cout << "press ENTER... ";
	cout.flush();
	cin.clear();
	while ( '\n' != (c=cin.get()) && EOF != c )
		;
}

/* -----------------------------------------------------
 * 
 * -----------------------------------------------------
 */
std::streampos f_size( const char* fname )
{
	std::streampos fsize = 0;
	std::ifstream f( fname, std::ios::binary | std::ios::ate );  // binary-mode
	if ( f.is_open() ) {
		fsize = f.tellg();
		f.close();
	}

	return fsize;
}

/* -----------------------------------------------------
 * 
 * -----------------------------------------------------
 */
void lines_print( const vector< vector<string> >& lines )
{
	cout << "lines: " << lines.size() << endl;
	for (size_t l=0; l < lines.size(); l++) {
		cout << "--- line: " << l+1 << " (" << lines[l].size() << " fields) ----\n";
		for (size_t f=0; f < lines[l].size(); f++) {
			cout << lines[l][f] << endl;
		}
		//cout << endl;
	}
	/*
	// or in C++11

	size_t ln=0;
	cout << "lines: " << lines.size() << endl;
	for ( auto& l: lines ) {
		cout << "--- line: " << ++ln << " (" << l.size() << " fields) ----\n";
		for ( auto& f: l ) {
			cout << f << endl;
		}
	}
	*/
}

/* -----------------------------------------------------
 * 
 * -----------------------------------------------------
 */
int main()
{
	ifstream f;
	size_t fsize = 0, sz = 0;
	char* buf = NULL;
	steady_clock::time_point tstart;
	duration<double> elapsed1, elapsed2;

	// get filesize
	fsize = f_size( FNAME );

	// read file into buf
	cout << "loading file " << FNAME << "..."; cout.flush();
	tstart = steady_clock::now();
	f.open( FNAME );               // text-mode
	if ( f.is_open() )
	{
		buf = new char[ 1+fsize ];
		f.read( buf, fsize );
		sz = f.gcount();       // actual bytes read
		f.close();
	}
	elapsed1 = steady_clock::now() - tstart;
	buf[sz] = buf[fsize] = '\0';   // NUL terminte buf
	cout << endl << "(" << fsize << "/" <<  sz << " bytes): " << elapsed1.count() << " secs\n\n";

	cout << "parsing loaded data..."; cout.flush();

#if PARSE_TWICE

	// 1st pass: count lines in buffer

	cout << "\n1st pass... "; cout.flush();
	tstart = steady_clock::now();

	size_t l = 0;
	for (char* cp = buf; *cp; cp++) {
		if ( '\n' == *cp )
			l++;
	}

	elapsed1 = steady_clock::now() - tstart;
	cout << elapsed1.count() << " secs";

	// 2nd pass: parse buf into lines & fields

	vector< vector<string> > lines;
	lines.resize(l);

	l = 0;
	char* cp  = buf;
	char* pre = buf;

	cout << "\n2nd pass... "; cout.flush();
	tstart = steady_clock::now();

	while ( *cp )
	{
		if ( ',' == *cp ) {
			*cp = '\0';
			lines[l].push_back( pre );
			pre = cp + 1;
		}
		else if ( '\n' == *cp ) {
			*cp = '\0';
			lines[l].push_back( pre );
			pre = cp + 1;
			l++;
		}
		cp++;
	}
	elapsed2 = steady_clock::now() - tstart;
	cout << elapsed2.count() << " secs\n";
	cout << "Total time: " << elapsed1.count() + elapsed2.count() << " secs (" << l << " lines)\n\n";

#else  // PARSE_ONCE

	// parse buf into lines & fields

	size_t l = 0;
	char* cp  = buf;
	char* pre = buf;
	vector< vector<string> > lines;
	vector<string> field;

	tstart = steady_clock::now();
	while ( *cp )
	{
		if ( ',' == *cp ) {
			*cp = '\0';
			field.push_back( pre );
			// lines.push_back( field );
			pre = cp + 1;
		}
		else if ( '\n' == *cp ) {
			*cp = '\0';
			field.push_back( pre );
			lines.push_back( field );
			field.clear();
			pre = cp + 1;
			l++;
		}
		// field.clear();
		cp++;
	}
	elapsed1 = steady_clock::now() - tstart;
	cout << endl << "(" << l << " lines): " << elapsed1.count() << " secs\n\n";
#endif

	delete[] buf;

	// lines_print( lines );

	press_enter();
	cout << "(cleaning up, please wait...)\n";

	return 0;
}

EDIT

Διόρθωση στη διόρθωση Δεν μέτραγα το χρόνο του 1ου pass (όχι ότι κάνει μεγάλη διαφορά, 0.125 δείχνει σε μένα, αλλά πρέπει να μετριέται κι αυτό).

Επεξ/σία 24 Μαΐου 2014 από migf1

migf1 · 27 Μαΐου 2014

Δέησα επιτέλους να φτιάξω και τον κώδικα της C με πλήρως δυναμική δέσμευση μνήμης στην custom δομή. Τρέχει ~2.3 secs ταχύτερα από την ταχύτερη παραλλαγή του κώδικα της C++ με τα vectors (εκείνη δηλαδή που κάνει 2 passes στο buffer για να κάνει pre-allocate τα line vectors).

Ουσιαστικά υλοποίησα την πρόταση που σου είχα κάνει σε κάποιο από τα αρχικά ποστς, περί 2 buf passes: μια για μέτρημα των γραμμών και allocation τους, και μια για progressive allocation των fields με ALLOC-AHEAD buffer (το έχω βάλει με define στα 16 fields).

------- (C++) MinGW32 v4.8.1 g++ -O2 -------

*** test1.csv ***

Loading... 0.35938 secs
(109876033 text-bytes | 110767105 binary-bytes)

Parsing... 
pass-1...  0.09375 secs
pass-2...  5.29688 secs
Parsed in: 5.39063 secs (891072 lines)

Total:     5.75000 secs (loading + parsing)

------- (C) MinGW32 v4.8.1 gcc -O2 -------

*** test1.csv ****

Loading... 0.35938 secs
(109876033 text-bytes | 110767105 binary-bytes)

Parsing...
pass-1...  0.09375 secs
pass-2...  2.93750 secs
Parsed in: 3.03125 secs (891072 lines)

Total:     3.39062 secs (loading + parsing)

Η διαφορά του με την προηγούμενη έκδοση που έκανε allocate δυναμικά μονάχα τα strings που κόπιαρε, δείχνει να είναι αμελητέα (της τάξης του 0.250 με 0.350 sec στις 891.000 γραμμές).

Επίσης αυτή τη φορά, έφτιαξα και τον C++ κώδικα να μοιάζει σε όλα με τον κώδικα της C, με κύρια διαφορά πως στον C++ έχουμε vectors ενώ στον C custom δομή. Κατάργησα και την clock() για τις μετρήσεις και στη θέση της έβαλα την gettimeofday() γιατί στα Windows η clock() συνήθως μετράει κι αυτή wall-clock time (αντί για cpu-time).

Τέλος, έγραψα (και χρησιμοποιώ και στους 2 κώδικες) μια πρόχειρη x-platform f_size() που κάνει και για πολύ μεγάλα αρχεία (στα Windows χρησιμοποιεί το win32 api, ενώ στα unix/linux/osx χρησιμοποιεί την stat64()). Έχω αφήσει όμως και στους 2 κώδικες και τις αρχικές LONG_MAX limited παραλλαγές. Αυτή είναι άσχετη από τους χρόνους (απλά από τάβλα την έγραψα για να την έχω γενικώς)

f_size.h & f_size.c : http://ideone.com/eCXzVn

parse_csv.c : http://ideone.com/rbOViF

parse_csv.cc : http://ideone.com/RNw1wD

Για portable κώδικα, νομίζω δεν πρέπει να απέχουμε και πάρα πολύ από το "as good as it can get".

H_ANARXIA_EINAI_PSEMA · 27 Μαΐου 2014

Για unportable κώδικα:

Για POSIX, δοκίμασε τις συναρτήσεις mmap και posix_madvice:

fd = open(..)
ptr = mmap(... fd)
posix_madvice(ptr, POSIX_MADV_SEQUENTIAL)

Το αντίστοιχο για Windows είναι η CreateFile με FILE_FLAG_SEQUENTIAL_SCAN. Θα είσαι καλυμμένος όσον αφορά το διάβασμα του αρχείου. Το parsing είναι ξεχωριστό.

migf1: Ο κώδικας σου είναι πολύ καλός, αλλά δεν μου αρέσει όταν βλέπω κάποιον να αλλάζει τους pointers σε NULL όταν κάτι αποτυγχάνει!!! Δοκίμασε και

scanf("%*[^\n]");

για εναλλακτικό pause()...

migf1 · 27 Μαΐου 2014

migf1: Ο κώδικας σου είναι πολύ καλός, αλλά δεν μου αρέσει όταν βλέπω κάποιον να αλλάζει τους pointers σε NULL όταν κάτι αποτυγχάνει!!!

Thanks για τα καλά λόγια!

Σίγουρα θα υπάρχουν αβλεψίες στον κώδικα... π.χ. διόρθωσα ήδη μια, όπου στο validation της f_size() στον caller, συνέκρινα με το 0 αντί για το -1... απομεινάρι από την portable flie_size() που αρχικά την είχα να επιστρέφει 0 (αντί για -1) on error.

Σχετικά με το NULL υπάρχουν πάνω-κατω 2 προσεγγίσεις: μια όπου λέει immediate crash is good, και μια άλλη που λέει immediate error reporting is good (με ή χωρίς termination).

Εγώ είμαι κυρίως fan της 2ης. Ειδικά όταν πρόκειται για pointers το "immediate crash" δεν είναι εγγυημένο (άσχετα που στο συγκεκριμένο πρόγραμμα δεν παίζει πολύ μεγάλο ρόλο, η συνήθεια είναι συνήθεια)! Περισσότερα μπορείς να διαβάσεις αν θέλεις εδώ: http://www.eskimo.com/~scs/cclass/int/sx7.html

Δοκίμασε και
scanf("%*[^\n]");
για εναλλακτικό pause()...

Και οι 2 προσεγγίσεις είναι προβληματικές αν δεν συνοδεύονται κι από προϋπάρχον stdin flushing. Θεωρώ πως χωρίς stdin flushing η δικά μου προσέγγιση είναι προβλέψιμη σε περισσότερες περιπτώσεις από ότι η δικιά σου.

Consider π.χ.:

#include <stdio.h>

#define USE_SCANF 1

/* ---------------------------------------- */
void press_enter( void )
{
	printf( "Press ENTER..." );
	fflush( stdout );

#if USE_SCANF
	scanf("%*[^\n]");
#else
	int c = '\0';
	while ( '\n' != (c=getchar()) && EOF != c )
		;
#endif
}

int main( void )
{
	char ch = '\0';

	press_enter();
	printf( "ch: " );
	fflush( stdout );
	scanf( "%c", &ch );
	putchar(ch);
	press_enter();

	return 0;
}

Παίξε με το USE_SCANF και δες πώς συμπεριφέρεται η μια και πως η άλλη. Κατά βάση, με τη δικιά σου το ch παίρνει ως τιμή το '\n' και πάει στην 2η κλήση της press_enter(). Με τη δικιά μου διαβάζει σωστά το ch, αλλά μετά κάνει feed το '\n' στην 2η κλήση της press_enter(). Πικρή ιστορία το interactive input, παλαιότερα είχα γράψει για τον χαβαλέ μια μικρή βιβλιοθήκη ειδικά για αυτό: http://x-karagiannis.gr/prg/c-prog/c-misc/prompt-for-library/

Για unportable κώδικα:

Για POSIX, δοκίμασε τις συναρτήσεις mmap και posix_madvice:
fd = open(..)
ptr = mmap(... fd)
posix_madvice(ptr, POSIX_MADV_SEQUENTIAL)
Το αντίστοιχο για Windows είναι η CreateFile με FILE_FLAG_SEQUENTIAL_SCAN. Θα είσαι καλυμμένος όσον αφορά το διάβασμα του αρχείου. Το parsing είναι ξεχωριστό.

Yeap! Νομίζω όμως πως ο ts δεν ενδιαφέρεται για τέτοιες υλοποιήσεις. Και την f_size() που έγραψα υπέρβαση ήταν για δικιά μου τάβλα. Όμως όταν βρω πάλι χρόνο και κυρίως κέφι, μπορεί να προσθέσω μερικές ακόμα f_xxxx συναρτήσεις στην f_size (π.χ. f_read, f_write, κλπ).

Επεξ/σία 27 Μαΐου 2014 από migf1

bnvdarklord · 27 Μαΐου 2014

migf1 ευχαριστώ που ασχολείσαι ακόμα, αλλά εχω καλυφθεί από την λύση που ειχα γράψει προχθες.

Μιας και αυτό δεν ειναι παρα ένα πολυ πολυ μικρό κομμάτι της εργασίας μου δεν νομιζω οτι χρειάζεται να χάσω χρονο να μελετήσω της λύσεις σου, δεν θα θελα να τις παρω απλά copy-paste εξαλλου.

Δεν το λεω για να σε αποτρέψω βέβαια, είναι πολύ πιθανό να βοηθήσουν άλλους χρήστες που θα βρούν το νήμα αυτό στο μελλον.

migf1 · 27 Μαΐου 2014

migf1 ευχαριστώ που ασχολείσαι ακόμα, αλλά εχω καλυφθεί από την λύση που ειχα γράψει προχθες.

Μιας και αυτό δεν ειναι παρα ένα πολυ πολυ μικρό κομμάτι της εργασίας μου δεν νομιζω οτι χρειάζεται να χάσω χρονο να μελετήσω της λύσεις σου, δεν θα θελα να τις παρω απλά copy-paste εξαλλου.

Δεν το λεω για να σε αποτρέψω βέβαια, είναι πολύ πιθανό να βοηθήσουν άλλους χρήστες που θα βρούν το νήμα αυτό στο μελλον.

Βασικά ασχολούμαι όποτε το θυμάμαι, και το κάνω κυρίως για αυτό που επεσήμανες. Για την (πιθανή πιστεύω) περίπτωση να φανούν χρήσιμα σε άλλα παιδιά που θα τύχει να διαβάσουν το νήμα.

Το έχω καταλάβει δηλαδή πως έχεις ήδη καλυφθεί Επίσης συμφωνώ πως εφόσον έχεις καλυφθεί, δεν υπάρχει λόγος τώρα που καίγεσαι να τελειώσεις την εργασία να κάτσεις να ασχοληθείς με τα μακρινάρια που ποστάρω (άσε που και να ήθελες να τα κάνεις copy & paste δεν νομίζω πως θα πέρναγες ευχάριστες στιγμές, έτσι όπως τα έχω wrapped σε callback functions ).

Από περιέργεια όμως, δεν μας έχεις πει αν σου είναι τελείως άγνωστα τα πλήθη των γραμμών και τα πλήθη των στηλών ανά γραμμή. Επίσης, το πλήθος των στηλών είναι μεταβαλλόμενο ανά γραμμή, ή σε ένα αρχείο όλες οι γραμμές έχουν πάντα το ίδιο πλήθος στηλών; Αν ισχύει το 2ο, τότε μετρώντας μαζί με τις γραμμές και το πλήθος στηλών μιας οποιασδήποτε γραμμής κατά το πρώτο pass, μπορείς μετά να κάνεις τα πάντα pre-allocate πριν ξεκινήσεις το copying στο 2ο pass, και να κερδίσεις πολύ χρόνο (όσο μεγαλύτερα τα αρχεία, τόσο μεγαλύτερο το κέρδος).

ΥΓ. Σχετικο-άσχετο: Αν... δεήσω να φτιάξω και τίποτα f_read(), f_write(), κλπ, θα τα ποστάρω κι αυτά εδώ, να είναι μαζεμένα.

bnvdarklord · 27 Μαΐου 2014

Από περιέργεια όμως, δεν μας έχεις πει αν σου είναι τελείως άγνωστα τα πλήθη των γραμμών και τα πλήθη των στηλών ανά γραμμή. Επίσης, το πλήθος των στηλών είναι μεταβαλλόμενο ανά γραμμή, ή σε ένα αρχείο όλες οι γραμμές έχουν πάντα το ίδιο πλήθος στηλών; Αν ισχύει το 2ο, τότε μετρώντας μαζί με τις γραμμές και το πλήθος στηλών μιας οποιασδήποτε γραμμής κατά το πρώτο pass, μπορείς μετά να κάνεις τα πάντα pre-allocate πριν ξεκινήσεις το copying στο 2ο pass, και να κερδίσεις πολύ χρόνο (όσο μεγαλύτερα τα αρχεία, τόσο μεγαλύτερο το κέρδος).

Νομίζω το είχα αναφέρει νωρίτερα, είναι στάνταρ ο αριθμός των στηλών. Όσο για το allocate δεν νομιζω να χρειάζεται γιατι κάνω απλά overwrite πάνω στα προηγούμενα - έχω ένα char "fields[13][64];", με χώρο 64 χαρακτήρες για το κάθε ένα column, και γράφω μόνο σε αυτό, και προστατεύω από τα σκουπίδια με \0.

(επίσης ανακάλυψα και τα lambdas και έτσι οι 3 συναρτήσεις που διαβάζανε 3 αρχεία με μικρή και μόνη διαφορά στον χειρισμό columns έστρωσαν αρκετά )

ParhsG · 28 Μαΐου 2014

μου αρεσει που σε θεματα c++ γίνεται τρελή ανάλυση ,τοσα σεντονια για ενα csv! Αν ηταν τιποτα λιγο πιο πολυπλοκο θα επρεπε να εφτανε 1000 σελιδες

imitheos · 28 Μαΐου 2014

μου αρεσει που σε θεματα c++ γίνεται τρελή ανάλυση ,τοσα σεντονια για ενα csv! Αν ηταν τιποτα λιγο πιο πολυπλοκο θα επρεπε να εφτανε 1000 σελιδες

Καμμιά 20αριά θα έφτανε και μετά θα κλειδωνόταν επειδή θα μαλώναμε μεταξύ μας

migf1 · 28 Μαΐου 2014

Νομίζω το είχα αναφέρει νωρίτερα, είναι στάνταρ ο αριθμός των στηλών. Όσο για το allocate δεν νομιζω να χρειάζεται γιατι κάνω απλά overwrite πάνω στα προηγούμενα - έχω ένα char "fields[13][64];", με χώρο 64 χαρακτήρες για το κάθε ένα column, και γράφω μόνο σε αυτό, και προστατεύω από τα σκουπίδια με \0.

(επίσης ανακάλυψα και τα lambdas και έτσι οι 3 συναρτήσεις που διαβάζανε 3 αρχεία με μικρή και μόνη διαφορά στον χειρισμό columns έστρωσαν αρκετά )

Δηλαδή, για να καταλάβω. Δεν σε ενδιαφέρει να ταξινομείς τα fields ανά lines, απλώς θέλεις να τα κοπιάρεις "χύμα" σε κάποια δομή; Έχεις ήδη γράψει νομίζω πως τα βάζεις σε κάποιο map, σωστά; Βασικά όταν βρεις χρόνο, γράψε λίγο πιο αναλυτικά τι ακριβώς κάνεις (π.χ. γιατί μετατρέπεις το κάθε string field σε int column = atoi(fields); ).

@ParhsG:

Το efficiency εκ φύσεως δεν είναι trivial. Η ερώτηση ήταν για βελτίωση του efficiency. Αν αφορούσε κάτι πολύ πιο πολύπλοκο από το απλοποιημένο csv parsing που θέτει το ερώτημα, τότε κατά πάσα πιθανότητα εγώ τουλάχιστον είτε δεν θα ασχολιόμουν καν είτε θα ήμουν πολύ πιο γενικός και φειδωλός στις απαντήσεις μου.

bnvdarklord · 28 Μαΐου 2014

Βασικά όταν βρεις χρόνο, γράψε λίγο πιο αναλυτικά τι ακριβώς κάνεις (π.χ. γιατί μετατρέπεις το κάθε string field σε int column = atoi(fields); ).

Ένα γράφημα αντιπροσωπεύουν ουσιαστικά(το δίκτυο του ΟΑΣΑ συγκεκριμένα). Εχω 3 αρχεία που διαβάζω - τα αλλα 2 ειναι αρκετά μικρότερα - το μεγάλο εχει τις ακμές ουσιαστικά.

Επίσης δεν τα κάνω όλα int, αναλόγως, τα ID των κόμβων τα κάνω int γιατι γινονται συχνά συγκρίσεις, και νομιζω ειναι πιο γρήγορο να γινονται αν ειναι int παρα string(ή οχι ; ). Μερικά τα κάνω floats, άλλα μένουν ως string κτλ.

Επεξ/σία 28 Μαΐου 2014 από bnvdarklord

Σύνδεση

[C++] - Γρήγορη ανάγνωση μεγάλων .csv

Προτεινόμενες αναρτήσεις

παπι

Συχνή συμμετοχή στο θέμα

Δημοφιλείς Ημέρες

Συχνή συμμετοχή στο θέμα

Δημοφιλείς Ημέρες

Δημοφιλή Μηνύματα

παπι

H_ANARXIA_EINAI_PSEMA

migf1

migf1

bnvdarklord

migf1

migf1

migf1

H_ANARXIA_EINAI_PSEMA

migf1

bnvdarklord

migf1

bnvdarklord

ParhsG

imitheos

migf1

bnvdarklord

Δημιουργήστε ένα λογαριασμό ή συνδεθείτε για να σχολιάσετε

Δημιουργία λογαριασμού

Σύνδεση

παπι

H_ANARXIA_EINAI_PSEMA

migf1

Σύνδεση