Προς το περιεχόμενο

coding challenge

παπι

Από τον παπι
στο Προγραμματισμός

 Share

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

migf1 Mentor

migf1

Δημοσ.
Δημοσ.

@imitheos:

 

Βασικά ότι επιχειρεί να "μετρήσει" file i/o είναι γτπ. Επίσης από ότι θυμάμαι, στα *nix η clock() μετράει cpu-time αλλά στα Windows μετράει wall-clock time (μύλος)!

 

Οι χρόνοι που έδωσα είναι χωρίς optimization. Με optimization, οι διαφορές στο 1o test-case είναι normal (π.χ. από 50% έως 100% αύξηση... μιλάω για τις δικές μας ρουτίνες). Στο 2ο test-case, συμβαίνει περίπου το ίδιο με Pelles C και lcc-win32, αλλά με mingw32 οι χρόνοι υπετριπλασιάζονται (π.χ. από 770% πάνε 2700%).

 

Πάντως ή αυτό που λες συμβαίνει ή η Pelles C βγάζει από την αρχή optimized εκτελέσιμο (οπότε ίσως έχει μικρά περιθώρια να το πάει παραπέρα).

 

Τέσπα, αφού μπήκα που μπήκα στο τριπάκι έφτιαξα ένα stand-alone, ready to use, C99 module για τον parser, κι έγραψα και σχόλια. Στο csv.h γράφω τα τι και πως (στα αγγλικά).

 

csv.h: http://ideone.com/V4Fv7z

csv.c: http://ideone.com/1bDwr1

 

Σε γενικές γραμμές, φορτώνει το αρχείο μονομιάς στη μνήμη (csv->buf) και αντικαθιστά τα κόμματα και τα '\n' με '\0' (με όλα τα + και τα - που έχει αυτή η προσέγγιση). Κατόπιν φτιάχνει και βάζει CsvString pointers πάνω στο csv->buf, ανάλογα με το parsing-model που έχει επιλέξει ο client κατά τη δημιουργία του Csv object του.

 

Το FLAT model, είναι ένα CsvString buffer, με char pointers που δείχνουν στα tokens μέσα στο csv->buf. Το CsvString είναι πλήρως exposed στο csv.h (περιέχει .cstr και .len members).

 

Το LINED model, είναι ένα CsvLine buffer, με το κάθε CsvLine να περιέχει ένα CsvString buffer (πάλι με απλούς char pointers στο csv->buf). Το CsvLine είναι opaque στους clients.

 

Και για τα 2 models παρέχονται ως έξτρα και εξειδικευμένοι _foreach() constructors, που δέχονται μια callback συνάρτηση (και userdata) με στόχο να την εφαρμόζουν στα parsing-units σε 1ο χρόνο, καθώς χτίζουν το model τους πάνω στο csv->buf. Αυτό μοιάζει με τις C++ lambda functions που χρησιμοποιεί ο papi στο ποστ που έχει κάνει, αλλά στη C έχουν πολύ μεγαλύτερο overhead (ίσως όμως φανεί χρήσιμη αν το complexity των υπολογισμών υπερβαίνει το overhead των callbacks και των void * dereferencing). Νομίζω επίσης πως δεν υπάρχει portable τρόπος να γίνουν inline οι callback συναρτήσεις.

 

Για το FLAT model, ως parsing-unit λογίζεται ένα CsvString (token), ενώ για το LINE model ως parsing-unit λογίζεται ένα CsvLine (line of tokens).

 

Τα tokens στον κώδικα τα λέω fields.

 

Άμα μου ξανάρθει όρεξη, ίσως βάλω και SERVE model, που να δουλεύει όπως του papi (δηλαδή με fixed buffer για το διάβασμα) και progressive serving, για να δουλεύει και με αρχεία μεγαλύτερα της διαθέσιμης μνήμης.

 

Πρέπει να φύγω τώρα, όταν επιστρέψω θα ποστάρω χρόνους με και χωρίς optimizations για τα 2 πρώτα test-cases. Το 3ο test-case θα μου εξηγήσει κανείς τι προσπαθεί να κάνει;

 

Οι ρουτίνες μου για τα 2 πρώτα test-cases είναι οι παρακάτω:

 

TestCase 1 (χωρίς callback)

 

 

int alg_sum( const char *fname )
{
	Csv *csv = make_csv( fname, CSVFLAT );
	if ( !csv ) {
		return 0;
	}

	int sum = 0;
	size_t nfields = csv_flat_nfields(csv);
	for (size_t i=0; i < nfields; i++ ) {
		sum += myatoi( csv_flat_field(csv,i)->cstr );
	}

	csv_free( csv );

	return sum;
}

 

TestCase 1 (με callback)

 

 

int callback_sum_foreach( CsvString *csvfield, void *sum )
{
	int *total = (int *)sum;
	*total += myatoi( csvfield->cstr );

	return 1;
}

int alg_sum_foreach( const char *fname )
{
	int sum = 0;

	Csv *csv = make_flat_csv_foreach( fname, callback_sum_foreach, (void *)&sum );
	if ( !csv ) {
		return 0;
	}
	csv_free( csv );

	return sum;
}

 

TestCase 2 (χωρίς callback):

 

 

int alg_sum1( const char *fname )
{
	Csv *csv = make_csv( fname, CSVLINED );
	if ( !csv ) {
		return 0;
	}

	CsvString *s;
	int mages = 0;                              // age sum of males
	int kages = 0;                              // age sum of kiki's
	size_t nlines = csv_lined_nlines(csv);
	for (size_t i=0; i < nlines; i++)
	{
		if ( 4 == (s=csv_lined_field(csv,i,1))->len && !memcmp("male", s->cstr, 4) ) {
			mages += myatoi( csv_lined_field(csv,i,2)->cstr );
			continue;
		}
		if ( 4 == (s=csv_lined_field(csv,i,0))->len && !memcmp("kiki", s->cstr, 4) ) {
			kages += myatoi( csv_lined_field(csv,i,2)->cstr );
			continue;
		}
	}
	csv_free( csv );

	return mages - kages;
}

 

TestCase 2 (me callback):

 

 

int callback_sum1_foreach( CsvLine *csvline, void *diff )
{
	int *dif = (int *)diff;
	CsvString *s;

	if ( 4 == (s=csvline_field(csvline,1))->len && !memcmp("male", s->cstr, 4) ) {
		*dif += myatoi( csvline_field(csvline,2)->cstr );
	}
	else if ( 4 == (s=csvline_field(csvline,0))->len && !memcmp("kiki", s->cstr,4) ){
		*dif -= myatoi( csvline_field(csvline,2)->cstr );
	}
	return 1;
}

int alg_sum1_foreach( const char *fname )
{
	int diff = 0;
	Csv *csv = make_lined_csv_foreach( fname, callback_sum1_foreach, (void *)&diff );
	if ( !csv ) {
		return 0;
	}
	csv_free( csv );
	return diff;
}

 

  • Like 1
  • Απαντ. 33
  • Δημ.
  • Τελ. απάντηση

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

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

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

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

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

παπι
παπι

Δεν νομιζω να εχει ανοιξει παρομοιο θεμα.   Φτιαξε ενα reusable mini csv parser.     μετα απο τα (ελαχιστα feedback ) το κανω update αυτο στα σκουπιδια εδω το νεο, πιο απλο. (pure c... νομιζω)

Directx
Directx

C++ Builder XE με τις βελτιστοποιήσεις ταχύτητας ενεργές:   TestReference Sum:-2133414434 secs: 0.42 TestReference Sum:-2133414434 secs: 0.39 TestAlg Sum: -137930983 secs: 1.78 TestAlg Sum: -13793

Kercyn
Kercyn

Στη GenerateCSV το for(size_t i = 0; i < cols; i++) δε θα έπρεπε να είναι for(size_t i = 0; i < cols - 1; i++) Ενδιαφέρον φαίνεται, ελπίζω να προλάβω ν' ασχοληθώ. Μπορούμε να χρησιμοποιήσου

imitheos Grand Master

imitheos

Δημοσ.
Δημοσ.

Τέσπα, αφού μπήκα που μπήκα στο τριπάκι έφτιαξα ένα stand-alone, ready to use, C99 module για τον parser, κι έγραψα και σχόλια. Στο csv.h γράφω τα τι και πως (στα αγγλικά).

Δεν το πολυ κοίταξα αλλά ωραία προσπάθεια.

 

#define _PREPARE_FLAT_MODEL_OR_DIE( csv, fname, f )\
do {\
38 γραμμές \
}while(0)
Εγώ κρατιέμαι αλλά κρύψε το αυτό πριν το δει κανείς άλλος :P
παπι Crazy Insomniac

παπι

Δημοσ.
  • Μέλος
Δημοσ.

Τωρα μαλιστα. Αυτο ειναι ενα mini parser.

 

To 3 case ειναι αρκετα απλο. 

Διαβαζεις την πρωτη γραμμη και εχεις, πρωτο field x, δευτερο y

 

εαν το y εχει την τιμη "stop" τοτε επιστρεφεις το x

 

εαν το y εχει την τιμη "go" τοτε πας στην γραμμη x και ξανακανεις τον ελεγχο.

migf1 Mentor

migf1

Δημοσ.
Δημοσ.

 

#define _PREPARE_FLAT_MODEL_OR_DIE( csv, fname, f )\
do {\
38 γραμμές \
}while(0)
Εγώ κρατιέμαι αλλά κρύψε το αυτό πριν το δει κανείς άλλος :P

 

Χε χε, γιατί να το κρύψω; Τα θέλω guaranteed inlined αυτά μέσα στους constructors αλλά δεν θέλω να τα διπλο-τριπλο γράφω (στην αρχή τα είχα σε 2 macros, ένα για κάθε model, αλλά μετά τα χώρισα σε 2 ανά model :P).

 

To 3 case ειναι αρκετα απλο.

Διαβαζεις την πρωτη γραμμη και εχεις, πρωτο field x, δευτερο y

 

εαν το y εχει την τιμη "stop" τοτε επιστρεφεις το x

 

εαν το y εχει την τιμη "go" τοτε πας στην γραμμη x και ξανακανεις τον ελεγχο.

Μα αφού έχεις κι αρνητικά νούμερα (x) στα go. Πώς θα πας σε αρνητική γραμμή;

 

Επίσης, εκείνο το 0-based που γράφεις που αναφέρεται, στο ότι τα γραμμένα νούμερα μέσα στο αρχείο είναι 0-based; Δηλαδή αν μια γραμμή με go γράφει 5 τότε πρέπει να πάμε στην γραμμή με index 4 στο buffer μας (και ξαναρωτώ, τα αρνητικά που κολλάνε; )

 

Μέχρι να μου ξεκαθαρίσεις τι ακριβώς παίζει με το 3ο case, ποστάρω και τους χρόνους που πήρα στα 2 πρώτα test-cases, με 5 διαφορετικούς compilers (με και χωρίς optimizations). Χρησιμοποίησα τις απλές εκδόσεις των ρουτίνων (δηλαδή χωρίς callback).

 

Pelles C v7.0:

 

/* ---- Pelles C v7.0 cc ---- */

Test 1

Generating file papi_sum.csv...
Done.
Creating reference...
Done. (opt killer 957213351)
Executing algorithm...
Done.
Check:OK
221.712803% Slower.

Test 2

Generating file papi_sum1.csv...
Done.
Creating reference...
Done. (opt killer 861114839)
Executing algorithm...
Done.
Check:OK
360.123967% Slower.

/* ---- Pelles C v7.0 cc -Ot -Ox ---- */

Test 1

Generating file papi_sum.csv...
Done.
Creating reference...
Done. (opt killer 957213351)
Executing algorithm...
Done.
Check:OK
305.312500% Slower.

Test 2

Generating file papi_sum1.csv...
Done.
Creating reference...
Done. (opt killer 861114839)
Executing algorithm...
Done.
Check:OK
639.853748% Slower.

 

lcc-win32 v3.8:

 

/* ---- lcc-win32 v3.8 lc ---- */

Test 1

Generating file papi_sum.csv...
Done.
Creating reference...
Done. (opt killer 957213351)
Executing algorithm...
Done.
Check:OK
377.951636% Slower.

Test 2

Generating file papi_sum1.csv...
Done.
Creating reference...
Done. (opt killer 861114839)
Executing algorithm...
Done.
Check:OK
762.008734% Slower.

/* --- lcc-win32 v3.8 lc -O --- */

Test 1

Generating file papi_sum.csv...
Done.
Creating reference...
Done. (opt killer 957213351)
Executing algorithm...
Done.
Check:OK
503.201507% Slower.

Test 2

Generating file papi_sum1.csv...
Done.
Creating reference...
Done. (opt killer 861114839)
Executing algorithm...
Done.
Check:OK
1048.565121% Slower.

 

mingw32 gcc v4.8.1:

 

/* ---- mingw32 v4.8.1 gcc ---- */

Test 1

Generating file papi_sum.csv...
Done.
Creating reference...
Done. (opt killer 957213351)
Executing algorithm...
Done.
Check:OK
356.919060% Slower.

Test 2

Generating file papi_sum1.csv...
Done.
Creating reference...
Done. (opt killer 861114839)
Executing algorithm...
Done.
Check:OK
757.440000% Slower.

/* ---- mingw32 v4.8.1 gcc -O2 ---- */

Test 1

Generating file papi_sum.csv...
Done.
Creating reference...
Done. (opt killer 957213351)
Executing algorithm...
Done.
Check:OK
765.196078% Slower.

Test 2

Generating file papi_sum1.csv...
Done.
Creating reference...
Done. (opt killer 861114839)
Executing algorithm...
Done.
Check:OK
2764.743590% Slower.

 

mingw64-win32 gcc v4.8.3:

 

/* ---- mingw64-win32 v4.8.3 gcc ---- */

Test 1

Generating file papi_sum.csv...
Done.
Creating reference...
Done. (opt killer 957213351)
Executing algorithm...
Done.
Check:OK
346.736292% Slower.

Test 2

Generating file papi_sum1.csv...
Done.
Creating reference...
Done. (opt killer 861114839)
Executing algorithm...
Done.
Check:OK
748.205928% Slower.

/* ---- mingw64-win32 v4.8.3 gcc -O2 ---- */

Test 1

Generating file papi_sum.csv...
Done.
Creating reference...
Done. (opt killer 957213351)
Executing algorithm...
Done.
Check:OK
777.540107% Slower.

Test 2

Generating file papi_sum1.csv...
Done.
Creating reference...
Done. (opt killer 861114839)
Executing algorithm...
Done.
Check:OK
2775.796178% Slower.

 

cygwin gcc v4.8.3

 

/* ---- cygwin gcc v4.8.3 ---- */

Test 1

Generating file papi_sum.csv...
Done.
Creating reference...
Done. (opt killer 957213351)
Executing algorithm...
Done.
Check:OK
346.222791% Slower.

Test 2

Generating file papi_sum1.csv...
Done.
Creating reference...
Done. (opt killer 861114839)
Executing algorithm...
Done.
Check:OK
792.043682% Slower.

/* --- cygwin gcc v4.8.3 -O2 --- */

Test 1

Generating file papi_sum.csv...
Done.
Creating reference...
Done. (opt killer 957213351)
Executing algorithm...
Done.
Check:OK
746.305419% Slower.

Test 2

Generating file papi_sum1.csv...
Done.
Creating reference...
Done. (opt killer 861114839)
Executing algorithm...
Done.
Check:OK
2734.883721% Slower.

 

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

Πρέπει να είστε μέλος για να αφήσετε σχόλιο

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

Εγγραφείτε με νέο λογαριασμό στην κοινότητα μας. Είναι πανεύκολο!

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

Σύνδεση

Έχετε ήδη λογαριασμό; Συνδεθείτε εδώ.

Συνδεθείτε τώρα
 Share
Προς την λίστα θεμάτων
  • Δημιουργία νέου...