H_ANARXIA_EINAI_PSEMA Δημοσ. 4 Ιουνίου 2014 Δημοσ. 4 Ιουνίου 2014 @defacer: int sgn = '-'; // ... return (sgn=='-')[(int[]){1,-1}]*ret; // alliws: return ret * (1 - 2*(sgn=='-')); Ορίστε!
albNik Δημοσ. 4 Ιουνίου 2014 Δημοσ. 4 Ιουνίου 2014 #define PI 3.14159265 ... return ((int)cos(PI * (sgm == '-'))) * ret; 1
παπι Δημοσ. 4 Ιουνίου 2014 Μέλος Δημοσ. 4 Ιουνίου 2014 Εκανα update ( search ref ) Καμια υλοποιηση εκτος απο dx & mig θα δουμε ή μπα;
H_ANARXIA_EINAI_PSEMA Δημοσ. 4 Ιουνίου 2014 Δημοσ. 4 Ιουνίου 2014 Θα βάλω και εγώ μια να χαρείς ρε μάγκα! Έγραψα τα πρώτα δύο, το τρίτο θέλει σκέψη... Ελπίζω να μην σε χαλάει που χρησιμοποιώ την scanf... int TestAlg_Sum(const char* filename) { FILE *fp; int x, sum = 0; if(fp = fopen(filename, "r")) { while(fscanf(fp, "%d %*c", &x) > 0) sum += x; fclose(fp); } return sum; } int TestAlg_Sum_1(const char* filename) { FILE *fp; char name[128], sex[128]; int age, sum_male = 0, sum_kiki = 0; if(fp = fopen(filename, "r")) { while(fscanf(fp, "%s %*c%s %*c%d", name, sex, age) > 0) if(!strcmp(sex, "male")) sum_male += age; else if(!strcmp(name, "kiki")) sum_kiki += age; fclose(fp); } return sum_male - sum_kiki; }
παπι Δημοσ. 4 Ιουνίου 2014 Μέλος Δημοσ. 4 Ιουνίου 2014 Που ειναι ο "parser"; (mig, αυτο λεω hardcoded) Να και τα δικα μου output Test 1 Generating file test.csv... Done. Creating reference... Done. (opt killer 957213351) Executing algorith... Done. Check:OK 718.750000% Slower. Test 2 Generating file test1.csv... Done. Creating reference... Done. (opt killer 861114839) Executing algorith... Done. Check:OK 615.463918% Slower. Test 3 Generating file test2.csv... Done. Creating reference... Done. (opt killer 652002011) Executing algorith... Done. Check:OK 900.000000% Slower. "parser" class CSVVal { const char* in; public: CSVVal(const char* s) : in(s){} int asInt() const { return atoi(this->in); } double asDouble() const { return atof(this->in); } std::string asString() const { return std::string(this->in); } operator int() const { return this->asInt(); } }; void CSVPareser1(const std::string& fileName, std::function<int (std::vector<CSVVal>&)> callback) { FILE *file = fopen(fileName.c_str(),"rb"); int status = 0; if(!file) return; const int buf_size = 1024 * 1024 * 5 ; char *buffer = new char[buf_size]; for(; { //trava arketa dedomena const size_t readed = fread(buffer,1,buf_size,file); if(!readed)//pipes dedomena break; //piase to teleytaio char* last = buffer + readed - 1; //vres to teleytaio newline for(; last > buffer && *last != '\n'; last--) ;//twra to [buf,last] einai parsable csv //afinoyme to file sto teleytaio newline const long rewind = long(readed) - long(last - buffer); fseek(file, -rewind + 1 , SEEK_CUR); ///////////////////////////////////////////////// // paei to diavasma ///////////////////////////////////////////////// std::vector<CSVVal> row; char* first = buffer -1; char* it = buffer; while(it < last) { //vres to koma for(; *it != ',' && *it != '\n' && it != last ; it++) ; //vale to field sto row row.push_back(CSVVal(first+1)); //trava sto epomeno first = it; //opa telos to row if(*it == '\n') { *it = 0; //pes toy na kanei to parse status = callback(row); row.clear(); } *it = 0; if(status) break; } //exit if(status) break; } delete[] buffer; fclose(file); } reuse int TestAlg_Sum(const char* filename) { //TODO //vgale to seiriako sum apo ola ta items toy csv, me to mini csv parser sou //h domh toy arxeioy einai matrix apo ints int sum = 0; CSVPareser1(filename,[&sum](std::vector<CSVVal>& row) { sum = std::accumulate(row.begin(), row.end(), sum ,std::plus<int>()); return 0; }); return sum; } int TestAlg_Sum_1(const char* filename) { //TODO // to arxeio einai kapws etsi // |Name| Sex| Age| (* sto sex exoyme female kai male) // 8a pareis to sum twn ages aytwn poy einai male // 8a pareis to sum twn ages aytwn poy exoyn onoma "kiki" // kai 8a epistrepseis thn diafora int sumKiki = 0; int sumMale = 0; CSVPareser1(filename,[&](std::vector<CSVVal>& row) { if(row[0].asString() == "kiki") sumKiki+= row[2].asInt(); if(row[1].asString() == "male") sumMale+= row[2].asInt(); return 0; }); return sumMale - sumKiki; } int TestAlg_SearchRef(const char* filename) { /* TODO to arxeio |number | action ean to acrion einai "stop" tote epistrefeis to "number" ean to action einai "go" tote to "number" einai h grammh toy epomenoy row (zero besed index) h arxh einai sto prwto row. */ int nextCheckLine = 0; for(; { int done = 0; int linecount = 0; CSVPareser1(filename,[&](std::vector<CSVVal>& row) { if(nextCheckLine == linecount) { nextCheckLine = row[0].asInt(); if(row[1].asString() == "stop") done = 1; return 1; } linecount++; return 0; }); if(done) return nextCheckLine; } }
iceblade Δημοσ. 4 Ιουνίου 2014 Δημοσ. 4 Ιουνίου 2014 import pandas print(sum(pandas.read_csv("data.csv", header=None).sum()))
H_ANARXIA_EINAI_PSEMA Δημοσ. 4 Ιουνίου 2014 Δημοσ. 4 Ιουνίου 2014 Α τώρα το κατάλαβα! και μ'αρέσει η λύση σου. Νομίζω το this-> δεν χρειάζεται. Μπορείς απλά να βάλεις atoi(in) κτλ. Το int() operator το έβαλες για την accumulate;
παπι Δημοσ. 4 Ιουνίου 2014 Μέλος Δημοσ. 4 Ιουνίου 2014 Το this, απλα μ'αρεσει. το int() για αυτο που ειπες. 1
imitheos Δημοσ. 4 Ιουνίου 2014 Δημοσ. 4 Ιουνίου 2014 Χωρίς O2 παίρνω 98% Slower. Με O2 παίρνω 6.5 χειρότερο αποτέλεσμα από την reference. % ./a.out Test 1 Generating file test.csv... Done. Creating reference... Done. (opt killer 957144455) Executing algorith... Done. Check:OK 664.537596% Slower. int TestAlg_Sum(const char* filename) { FILE *f; char buf[BUFSIZ]; char *p; int sum = 0; size_t l; f = fopen(filename, "rb"); while (fgets(buf, BUFSIZ, f) != NULL) { p = buf; while ((l = strcspn(p, ",\n" )) > 0) { *(p + l) = '\0'; sum += atoi(p); p += l + 1; } } fclose(f); return sum; } Αν δεν χρησιμοποιήσω την atoi αλλά την παρακάτω, τότε παίρνω 4x πιο αργό αποτέλεσμα από την reference. int myatoi(const char *s) { int val = 0; const char *p = s; if (*p == '-') p++; while (*p) { val += *p++ - '0'; val *= 10; } val /= 10; return (*s == '-') ? -val : val; } % ./a.out Test 1 Generating file test.csv... Done. Creating reference... Done. (opt killer 957144455) Executing algorith... Done. Check:OK 413.103472% Slower. Τα άλλα δεν τα έκανα ακόμη Άσχετο αλλά η reference δεν προσθέτει ένα-ένα χαρακτήρα άρα κάνει πολύ λιγότερη δουλειά ?
migf1 Δημοσ. 4 Ιουνίου 2014 Δημοσ. 4 Ιουνίου 2014 Εκανα update ( search ref ) Καμια υλοποιηση εκτος απο dx & mig θα δουμε ή μπα; Σε μένα πάντως δεν είναι σαφές ούτε τι δεν θεωρείς reusable, ούτε τελικά ποιος είναι ο στόχος αυτού του code challenge. Είναι η μικρότερη ταχύτητα εκτέλεσης; η μικρότερη κατανάλωση πόρων; ο πιο readable κώδικας; ο πιο σύντομος κώδικας; είναι πιο καμουφλαρισμένος κώδικας; κλπ, κλπ. Πολλά από αυτά αυτοαναιρούνται, οπότε έτσι όπως είναι τώρα στο φλου ο καθένας γράφει ότι θέλει. Επίσης με χάλασε που στο άσχετο κι ενώ υποτίθεται πως ακόμα έτρεχε το challenge που έθεσες, το πέταξες στα σκουπίδια χωρίς καν να έχεις δώσεις κώδικα εσύ ο ίδιος. Αν θέλεις μεγαλύτερη συμμετοχή, ίσως είναι καλή ιδέα να γράψεις ξεκάθαρα με λόγια (και όχι με σχόλια μέσα σε κώδικα) το τι θέλεις να κάνει το challenge, ποιο είναι το κυρίαρχο κριτήριο αξιολόγησης των υλοποιήσεων και (αν υπάρχουν) ποιοι κανόνες πρέπει να τηρηθούν. ΥΓ. Εγώ πάντως θεώρησα πως είναι η μικρότερη ταχύτητα εκτέλεσης -λόγω της reference function- και πάνω σε αυτό κινήθηκε ο κώδικας που έδωσα για το πεταμένο challenge. 1
παπι Δημοσ. 5 Ιουνίου 2014 Μέλος Δημοσ. 5 Ιουνίου 2014 @mig Μα ειμαι ξεκαθαρος. (ετσι πιστευω) Φτιαξε ενα mini csv parser toolkit/framework , οχι hardcoded οχι one case parser πως αλλιως να το πω; Οι συναρτησεις TestAlg_Sum TestAlg_Sum_1 TestAlg_Search_Ref Ειναι απλα testers για διαφορες περιπτωσεις, ετσι ωστε να μην κανεις focus σε κατι συγκεκριμενο. Το challnge ειναι η ταχυτητα, αλλα υπαρχει και το "ΟΧΙ HARDCODED", δεν θα φτιαξεις εναν parser να κανει sum, θα φτιαξεις απλα εναν γρηγορο parser. Βεβαια, φταιω που επελεξα csv και οχι json ή xml που θα ηταν ξεκαθαρα οτι θες parser. @imitheos το testreference ειναι απλα για να υπαρχει καποια αναφορα στο συστημα. Για να μην πεις οτι "εγω το εκανα σε 1 δευτερολεπτο, ενω εσυ στη μια ωρα" γιατι εσυ μπορει να εχεις SSD ενω εγω δικετα
migf1 Δημοσ. 5 Ιουνίου 2014 Δημοσ. 5 Ιουνίου 2014 @mig Μα ειμαι ξεκαθαρος. (ετσι πιστευω) Φτιαξε ενα mini csv parser toolkit/framework , οχι hardcoded οχι one case parser πως αλλιως να το πω; Οι συναρτησεις TestAlg_Sum TestAlg_Sum_1 TestAlg_Search_Ref Ειναι απλα testers για διαφορες περιπτωσεις, ετσι ωστε να μην κανεις focus σε κατι συγκεκριμενο. Το challnge ειναι η ταχυτητα, αλλα υπαρχει και το "ΟΧΙ HARDCODED", δεν θα φτιαξεις εναν parser να κανει sum, θα φτιαξεις απλα εναν γρηγορο parser. Βεβαια, φταιω που επελεξα csv και οχι json ή xml που θα ηταν ξεκαθαρα οτι θες parser. Αν και στις επόμενες 3-4 μέρες εγώ είναι πολύ χλωμό να ασχοληθώ, εξακολουθώ να μην το πιάνω αυτό το "one case" που λες. Για παράδειγμα, ας μείνουμε στο csv (καλά αν έβαζες xml σιγά μην καθόμουν να φτιάξω parser εγώ ) ποιο είναι αυτό το "one case"; To csv δεν είναι well-defined format. Μπορεί να έχεις 1002 παραλλαγές, π.χ. μπορεί να έχει quoted ή unquoted fields, το delimiter να μην είναι υποχρεωτικά το κόμμα (μπορεί να είναι το tab ή το semicolon), μπορεί να έχει ή όχι blanks μεταξύ των fields, τα fields δεν είναι υποχρεωτικό να είναι ομοιογενή, κλπ, κλπ. Οπότε, τι μας ζητάς εδώ πέρα με εκείνο το να μην είναι "one case"? Να φτιάξουμε parser που θα μπορεί να κάνει handle όλες τις πιθανές παραλλαγές. Γιατί αν ζητάς τέτοιο πράγμα, εγώ τουλάχιστον δεν κάθομαι να φτιάξω και μάλιστα να θέλω να το κάνω και γρήγορο (υπάρχουν χιλιάδες έτοιμα ). Αν δεν ζητάς να κάνουμε handle όλες τις πιθανές παραλλαγές, πες μας ακριβώς ποιες περιπτώσεις θέλεις να κάνουμε handle. Πες μας π.χ. πως τα fields δεν πρόκειται ποτέ να είναι quoted, δεν πρόκειται να υπάρχει τίποτε άλλο μεταξύ των fields παρά μόνο ο delimeter, που θα είναι π.χ. πάντα κόμμα, και πως π.χ. δεν πρόκειται να υπάρχουν κενά fields πουθενά. Έτσι όπως μας το έχεις τώρα στο φλου, άλλος μπορεί να κάνει skip τα spaces, άλλος να μην τα κάνει. Άλλος να κάνει handle και quoted fields κι άλλος μόνο unquoted, και πάει λέγοντας. ΥΓ. Όσο πιο απλό το κρατήσεις τόσο πιο πολύ κόσμο θα μαζέψει κατά τη γνώμη. Συγκεκριμενοποίησέ το όμως!
migf1 Δημοσ. 6 Ιουνίου 2014 Δημοσ. 6 Ιουνίου 2014 Λοιπόν, στα πεταχτά που ασχολήθηκα στο 1ο test-case μάλλον τα πήγα μια χαρά, αλλά με τους mingw32 v4.8.1 gcc και lcc-win32 v3.8 είχα θέμα στο 2ο test-case. Όταν ευκαιρήσω ξανά, θα δω μήπως μπορέσω να το βελτιώσω το 2ο test-case. /* ----- pelles-C 7.0 ----- */ Test 1 Generating file papi_sum.csv... Done. Creating reference... Done. (opt killer 957213351) Executing algorithm... Done. Check:OK 219.837692% Slower. Test 2 Generating file papi_sum1.csv... Done. Creating reference... Done. (opt killer 861114839) Executing algorithm... Done. Check:OK 375.240128% Slower. /* ----- mingw32 4.8.1 ----- */ Test 1 Generating file papi_sum.csv... Done. Creating reference... Done. (opt killer 957213351) Executing algorithm... Done. Check:OK 339.600000% Slower. Test 2 Generating file papi_sum1.csv... Done. Creating reference... Done. (opt killer 861114839) Executing algorithm... Done. Check:OK 754.880000% Slower. /* ----- lcc-win32 3.8 ----- */ Test 1 Generating file papi_sum.csv... Done. Creating reference... Done. (opt killer 957213351) Executing algorithm... Done. Check:OK 385.901163% Slower. Test 2 Generating file papi_sum1.csv... Done. Creating reference... Done. (opt killer 861114839) Executing algorithm... Done. Check:OK 801.180438% Slower. Στο μεταξύ εξηγήστε μου τι ακριβώς κάνει το 3o test-case γιατί από τα σχόλια του παπι μέσα στον κώδικα δεν καταλαβαίνω γρι. Οπότε κάντε το μου λιγάκι λιανά, να το φτιάξω κι αυτό και να ποστάρω και κώδικα άμα είναι.
migf1 Δημοσ. 6 Ιουνίου 2014 Δημοσ. 6 Ιουνίου 2014 Λοιπόν, θα μου εξηγήσει κανείς τι ακριβώς θέλει το 3ο test-case, τώρα που έχω λίγο κενό και όρεξη να ασχοληθώ; (στο μεταξύ πάω να βάλω τον parser σε δικό του module, για να ταιριάζει κάπως με την κλάση που έχει κάνει ο παπι... θα μου γίνει λιγάκι πιο αργός, αλλά δεν βαριέσαι)
imitheos Δημοσ. 7 Ιουνίου 2014 Δημοσ. 7 Ιουνίου 2014 Λοιπόν, στα πεταχτά που ασχολήθηκα στο 1ο test-case μάλλον τα πήγα μια χαρά, αλλά με τους mingw32 v4.8.1 gcc και lcc-win32 v3.8 είχα θέμα στο 2ο test-case. Όταν ευκαιρήσω ξανά, θα δω μήπως μπορέσω να το βελτιώσω το 2ο test-case. /* ----- pelles-C 7.0 ----- */ Test 1 219.837692% Slower. Test 2 375.240128% Slower. /* ----- mingw32 4.8.1 ----- */ Test 1 339.600000% Slower. Test 2 754.880000% Slower. /* ----- lcc-win32 3.8 ----- */ Test 1 385.901163% Slower. Test 2 801.180438% Slower. Όπως γράψαμε σε προηγούμενα μηνύματα και εσύ και εγώ, με O2 παίρνουμε χειρότερο αποτέλεσμα. Η reference είναι πιο optimizable από τον αλγόριθμο που γράφουμε εμείς οπότε όσο πιο καλό optimization έχει ο compiler, τόσο πιο αργός θα πρέπει να βγαίνει ο δικός μας. Άρα μήπως το θέμα το έχει ο pelles-c αντί για τους άλλους ? [offtopic] Έκανα χτες κάτι αλλαγές για να μειώσω τον χρόνο και συμπτωματικά είπα να τρέξω τον clang να δω τι βγάζει. Το αποτέλεσμα πήγε από 400 που είχα σε 250. Μες τη χαρά εγώ που η αλλαγή μου ήταν τόσο καλή, πάω να δω την assembly και βλέπω ότι αυτή του clang ήταν 10 φορές χειρότερη από του gcc και στη δική μου συνάρτηση και στη reference. Η μείωση της διαφοράς δεν ήταν λόγω του κώδικά μου (ήταν και για αυτό αλλά σε πολύ μικρότερο ποσοστό) αλλά γιατί ο clang έβγαζε πιο αργή reference Δοκιμάζοντας τα διάφορα στάδια βελτιστοποίησης παίρνω το εξής: -------------------- | | GCC | CLANG | | O0 | 112 | 121 | | O1 | 431 | 497 | | O2 | 375 | 287 | | O3 | 863 | 286 | -------------------- [/offtopic]
Προτεινόμενες αναρτήσεις
Δημιουργήστε ένα λογαριασμό ή συνδεθείτε για να σχολιάσετε
Πρέπει να είστε μέλος για να αφήσετε σχόλιο
Δημιουργία λογαριασμού
Εγγραφείτε με νέο λογαριασμό στην κοινότητα μας. Είναι πανεύκολο!
Δημιουργία νέου λογαριασμούΣύνδεση
Έχετε ήδη λογαριασμό; Συνδεθείτε εδώ.
Συνδεθείτε τώρα