coding challenge

παπι · 3 Ιουνίου 2014

Δεν νομιζω να εχει ανοιξει παρομοιο θεμα.

Φτιαξε ενα reusable mini csv parser.

μετα απο τα (ελαχιστα feedback ) το κανω update
αυτο στα σκουπιδια

Το τεστ ειναι απλο, parse ενα απλο csv αρχειο που εχει μονο int, κανε sum ολα τα ints. Αυτα.

Εδω ο σκελετος. Επειδη τα συστηματα που εχομε, διαφερουν μεταξυ τους. Η συγκριση θα γινει με την συναρτηση TestReference.

void TestReference(const char* filename)
{
	const size_t buf_size = 1024 * 1024;
	size_t readed;
	int sum = 0;
	FILE *file = fopen(filename,"rb");
	char* buf = new char[buf_size];
	while((readed = fread(buf,1,buf_size,file)) > 0)
	{
		for(size_t i = 0; i < readed; i++)
			sum += buf[i];
	}
	delete[] buf;
	fclose(file);
	printf("TestReference Sum:%d\n",sum);
}



//apo internet
static long int next = 1;
int rand0(void) // RAND_MAX assumed to be 32767
{
    next = next * 1103515245 + 12345;
    return ( int)(next/65536) % 32768;
}

void GenerateCSV(const char* fileName,size_t lines, size_t cols)
{
	FILE *file = fopen(fileName,"wb");
	int sum = 0;
	int r;
	//lines
	for(size_t line = 0; line < lines ; line++)
	{
		//row
		for(size_t i = 0; i < cols; i++)
		{
			r = rand0();
			sum += r;
			fprintf(file,"%d,",r);
		}
		r = rand0();
		sum+= r;
		fprintf(file,"%d\n",r);
	}
	fclose(file);
	printf("Sum:%d\n",sum);
}

int main() 
{
	GenerateCSV("test.csv",1000 * 1000,20);
	for(int i =0; i <2; i++)
	{
		//CODE_TIMER_START(0);
		TestReference("test.csv");
		//CODE_TIMER_END(0,L"Reference");
	}
	for(int i = 0; i < 2; i++)
	{
		//CODE_TIMER_START(1);
		TestAlg("test.csv");
		//CODE_TIMER_END(1,L"Alg");
	}


	return 0;
}

εδω το νεο, πιο απλο. (pure c... νομιζω)

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
	return 0;
}

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
	return 0
}
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.


	*/

	return 0;
}




/////////////////////////////////////////////
typedef int(*func_type)(const char* filename);
void Tester(
	func_type generator,
	func_type reference,
	func_type algorithm,
	const char* fileName);

int GenerateCSV_Sum(const char* fileName);
int GenerateCSV_Sum_1(const char* fileName);
int GenerateCSV_SearchRef(const char* fileName);
int TestReference(const char* filename);
int rand0();
double Gain(double from, double to);
//////////////////////////////////////////////
//////////////////////////////////////////////
int main() 
{
	
	printf("Test 1\n\n");
	Tester(
		GenerateCSV_Sum,
		TestReference,
		TestAlg_Sum,
		"test.csv");
		

	printf("Test 2\n\n");
	Tester(
		GenerateCSV_Sum_1,
		TestReference,
		TestAlg_Sum_1,
		"test1.csv");

	getchar();
	return 0;
}
/////////////////////////////////////////////////////
/////////////////////////////////////////////////////
/////////////////////////////////////////////////////
void Tester(
	func_type generator,
	func_type reference,
	func_type algorithm,
	const char* fileName)
{
	clock_t start;
	clock_t refTime;
	clock_t algTime;
	int genOutput;
	int refOutput;
	int algOutput;

	printf("Generating file %s...\n",fileName);
	genOutput = generator(fileName);
	printf("Done.\n");

	printf("Creating reference...\n");
	start = clock();
	refOutput = reference(fileName);
	refTime = clock() - start;
	printf("Done. (opt killer %d)\n",refOutput);

	printf("Executing algorith...\n");
	start = clock();
	algOutput = algorithm(fileName);
	algTime = clock() - start;
	printf("Done.\nCheck:%s\n%lf%% Slower.\n",
		algOutput == genOutput ? "OK" : "FAIL",
		Gain(refTime,algTime));

}


double Gain(double from, double to)
{
	return  ((to - from)/from) * 100.0;
}
int GenerateCSV_Sum(const char* fileName)
{
	const size_t lines = 1000 * 1000;
	const size_t cols = 30;
	FILE *file; 
	size_t line;
	size_t i;
	int sum = 0;
	int r;
	file = fopen(fileName,"wb");
	//lines
	for(line = 0; line < lines ; line++)
	{
		//row
		for(i = 0; i < cols; i++)
		{
			r = rand0();
			sum += r;
			fprintf(file,"%d,",r);
		}
		r = rand0();
		sum+= r;
		fprintf(file,"%d\n",r);
	}
	fclose(file);
	return sum;
}
int GenerateCSV_Sum_1(const char* fileName)
{
	FILE *file;
	size_t i;
	int age;
	int sex;
	int name;
	int maleSum;
	int kikiSum;
	maleSum = 0;
	kikiSum = 0;
	char* names[][5] = {
		{ "vagelas","gianhs","paaniwths","vasilhs","petros" },
		{ "kiki","vasia","xristina","maria","elena"}
	};
	

	file = fopen(fileName,"wb");
	
	for(i = 0; i < 1000 * 1000 * 10; i++)
	{
		age = abs(rand0() % 100);
		sex = rand0() % 1000 > 500;
		name = abs(rand0() % 5);
		if(sex == 0)
			maleSum += age;
		if(name == 0 && sex == 1)
			kikiSum += age;
		auto n = names[sex][name];
		fprintf(file,"%s,%s,%d\n",
			names[sex][name],
			sex == 0 ? "male" : "female",
			age);
	}
	
	fclose(file);
	return maleSum - kikiSum;
}
int GenerateCSV_SearchRef(const char* fileName)
{
	FILE *file;
	size_t i,j;
	int found;
	int line;

	int path[10][3] = 
	{
		//cur|ref|action
		{ 0,  4, 0 },
		{ 4,  3, 0 },
		{ 3,  100, 0 },
		{ 100,5000, 0 },
		{ 5000,600,0 },
		{ 600,987654, 0 },
		{ 987654,76,0},
		{ 76, 2321, 0 },
		{ 2321,2,0 },
		{ 2,13124,1    }
	};

	file = fopen(fileName,"wb");
	
	for(i = 0; i < 1000 * 1000; i++)
	{
		found = 0;
		//check path
		for(j = 0; j < 10; j++)
		{
			if(path[j][0] == i)
			{
				fprintf(file,
					"%d,%s\n",
					path[j][1],
					path[j][2] ? "stop" : "go");
				found = 1;
				break;
			}
		}
		//hardcoded?
		if(found)
			continue;
		//random
		fprintf(file,
			"%d,%s\n",
			rand0(),
			abs(rand0() % 1000) > 500 ? "stop" : "go");
	}
	fclose(file);
	return path[9][1];
}
int rand0(){
	static long int next = 1;
    next = next * 1103515245 + 12345;
    return ( int)(next/65536) % 32768;
}
int TestReference(const char* filename)
{
	const size_t buf_size = 1024 * 1024;
	size_t readed;
	size_t i;
	int sum = 0;
	FILE *file;
	char* buf;
	file = fopen(filename,"rb");
	buf = (char*)malloc(buf_size);
	while((readed = fread(buf,1,buf_size,file)) > 0)
	{
		for(i = 0; i < readed; i++)
			sum += buf[i];
	}
	free(buf);
	fclose(file);
	return sum;
}

Επεξ/σία 4 Ιουνίου 2014 από παπι

Kercyn · 3 Ιουνίου 2014

Στη GenerateCSV το

for(size_t i = 0; i < cols; i++)

δε θα έπρεπε να είναι

for(size_t i = 0; i < cols - 1; i++)

Ενδιαφέρον φαίνεται, ελπίζω να προλάβω ν' ασχοληθώ. Μπορούμε να χρησιμοποιήσουμε threads;

παπι · 3 Ιουνίου 2014

Οτι θες βαζεις. Απλα να ειναι reusable. Btw η δικη μου υλοποιηση ειναι χ10 αργοτερη απο το reference

migf1 · 3 Ιουνίου 2014

Το challenge είναι ο μικρότερος δυνατόν χρόνος εκτέλεσης;

H_ANARXIA_EINAI_PSEMA · 3 Ιουνίου 2014

Αν κατάλαβα καλά...

#include <stdio.h>
int main(void) {
  int x,sum = 0;
  while(scanf("%d %*c", &x) > 0) sum += x;
  printf("%d\n", sum);
  return 0;
}

migf1 · 3 Ιουνίου 2014

Οτι θες βαζεις. Απλα να ειναι reusable. Btw η δικη μου υλοποιηση ειναι χ10 αργοτερη απο το reference

Έφτασα περίπου στο x6 πιο αργός με optimization -Ο2 στον mingw gcc, και περίπου στο 3x πιο αργός χωρίς compiler optimization. Θέλω να κάνω κάτι δοκιμές ακόμα μήπως κατέβω κι άλλο, αλλά κατά το βραδάκι.

/* ----- mingw gcc -O2 ----- */
TestReference Sum: -2133414434
0.140000 secs
TestReference Sum: -2133414434
0.265000 secs
TestAlg Sum: -137930983
0.625000 secs
TestAlg Sum: -137930983
1.266000 secs

/* ----- mingw gcc ----- */
TestReference Sum: -2133414434
0.515000 secs
TestReference Sum: -2133414434
1.031000 secs
TestAlg Sum: -137930983
1.656000 secs
TestAlg Sum: -137930983
3.328000 secs

Directx · 3 Ιουνίου 2014

C++ Builder XE με τις βελτιστοποιήσεις ταχύτητας ενεργές:

TestReference Sum:-2133414434
secs: 0.42
TestReference Sum:-2133414434
secs: 0.39
TestAlg Sum: -137930983
secs: 1.78
TestAlg Sum: -137930983
secs: 1.77

Visual Studio 2010 με τις βελτιστοποίησεις ταχύτητας ενεργές:

TestReference Sum:-2133414434
secs: 0.34
TestReference Sum:-2133414434
secs: 0.32
TestAlg Sum: -137930983
secs: 1.36
TestAlg Sum: -137930983
secs: 1.35

Ακολουθεί ένα νέο πρόγραμμα το οποίο διαβάζει κατευθείαν τα περιεχόμενα του CSV δίχως πρωτύτερα να έχει επεξεργαστεί το αρχείο μέσω των συναρτήσεων αναφοράς ώστε να μην υπεισέρχεται στην διαδικασία των μετρήσεων το File System caching.

Η διαδικασία χωρίζεται σε μια σειρά από τεστ τα οποία διαβάζουν το αρχείο και υπολογίζουν την σούμα των αριθμών α) δίχως buffering, β) με buffering (βελτιστοποιημένο για συνεχόμενη ανάγνωση) και γ) τα α και β με μεταβλητό μέγεθος buffer ανάγνωσης από 32KB ως 1MB.

// Process large CSV files experiment, xdir.
//  C++ Builder XE or Visual Studio 2010

#include <windows.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>

#ifdef __BORLANDC__
	#define	MY_CLK_TCK	CLK_TCK
#else
	#define	MY_CLK_TCK	(double)CLOCKS_PER_SEC
#endif

#define	ITERATION 3

bool TestAlg(const char* fileName, const bool& noBuffering, const DWORD& dwBufferLen)
{
	bool s = false;

	// Open file for SEQUENTIAL scan
	const HANDLE hFile = CreateFileA(fileName, GENERIC_READ, FILE_SHARE_READ,
		NULL, OPEN_EXISTING, noBuffering ? FILE_FLAG_NO_BUFFERING: FILE_FLAG_SEQUENTIAL_SCAN, NULL);

	if(hFile == INVALID_HANDLE_VALUE)
		fprintf(stderr, "CreateFile error = %X\n", GetLastError());
	else
	{
		DWORD dwDataLen,
			  dwSum = 0;

		const HANDLE hProcHeap = GetProcessHeap();

		// HeapAlloc (just like C 'malloc' or C++ 'new')
		const LPBYTE pbBuff = (LPBYTE)HeapAlloc(hProcHeap, 0, dwBufferLen);

		if(!pbBuff)
			fprintf(stderr, "HeapAlloc error = %X", GetLastError());
		else
		{
			const DWORD dwHeapLen = HeapSize(hProcHeap, 0, pbBuff);

			// HeapSize failure?
			if(dwHeapLen == (DWORD)-1)
				fprintf(stderr, "HeapSize error = %X", GetLastError());
			else
			{
				bool neg = false;
				LONG lVal= 0;

				// Do file-input..
				for( ;; )
				{
					if(!ReadFile(hFile, pbBuff, dwHeapLen, &dwDataLen, NULL))
					{
						fprintf(stderr, "ReadFile error = %X\n", GetLastError());
						break;
					}

					// EOF?
					if(!dwDataLen)
						break;

					// 01. Read each number char by char, stop and sum it on first
					//  comma or new-line character (, or \n).
					//
					// 02. A leading minus char (-) suggests the begining of a negative
					//  value.
					//
					// 03. When block ends without \n or - assume number continues
					//  on to the next block!
					static LPBYTE ptrChr;
					ptrChr = pbBuff;

					while(ptrChr - pbBuff < dwDataLen)
					{
						const LPBYTE c = ptrChr;

						// modified atoi code..
						if(*c == '-')
							neg = true;
						else
							if(*c >= '0' && *c <= '9')
								lVal = 10 * lVal + (*c - '0');
							else
								if(*c == '\n' || *c == ',')
								{
									dwSum += (neg ? -lVal: lVal);
									lVal = neg = false;
								}

						ptrChr++;
					}
				}

				// Left over?
				if(lVal)
					dwSum += (neg ? -lVal: lVal);

				// End gracefully..
				FlushFileBuffers(hFile);
				CloseHandle(hFile);

				HeapFree(hProcHeap, 0, pbBuff);
				printf("TestAlg dwSum: %d\n", dwSum);

				s = true;
			}
		}
	}

	return s;
}

bool TestType(const char* fileName, const bool& noBuffering, const DWORD& dwBufferLen)
{
	clock_t tStart = 0;

	double tTotal = 0.0;

	bool s;

	puts(noBuffering ? " ** NO BUFFERING ** ": " ** WITH BUFFERING **");

	printf(" Buffer Length = %d bytes\n\n", dwBufferLen);

	for(int i = 0; i < ITERATION; i++)
	{
		static double tElapsed;

		tStart = clock();
		s = TestAlg(fileName, noBuffering, dwBufferLen);

		tElapsed = (clock() - tStart) / MY_CLK_TCK;
		printf("%d) secs: %.2f\n", i + 1, tElapsed);

		tTotal += tElapsed;
	}

	printf(" avg: %.2f\n\n", tTotal / ITERATION);

	return s;
}

int main(void)
{
	for(int iPow = 15; iPow <= 20; iPow++)
	{
    	const DWORD dwBufferLen = pow(2.f, iPow);

		if(TestType("test.csv", true, dwBufferLen))	// no buffering
			TestType("test.csv", false, dwBufferLen);// buffering / seq. read
	}

	puts("Press Enter to exit..");
	getchar();

	return 0;
}

Το πρόγραμμα μπορεί να περιέχει bugs ή άλλες αβλεψίες.

* Ο κώδικας δοκιμάστηκε σε ένα Intel Core Duo (T2050) 1.6GHz με 2GB RAM και Windows 7 (32-bit) με τον C++ Builder XE compiler (σε Release Mode) και την Visual Studio 2010 C++ (σε Release Mode επίσης). Αξίζει να σημειώσω πως ο C++ Builder XE είναι μια αρκετά παλιά έκδοση πλέον του C++ Builder, νεότερες εκδόσεις μπορεί να σημειώνουν καλύτερες επιδόσεις!

** Έχει γίνει προσπάθεια να εξαλειφθεί το File System caching των Windows, φυσικά όμως το HDD I/O Cache παραμένει (και υπεισέρχεται).

*** Καθώς το Λ.Σ. είναι multitask υπάρχουν περιπτώσεις όπου το I/O του προγράμματος μπορεί να διακόπτεται για μερικά ns οπότε οι μετρήσεις δεν είναι απόλυτες - αλλά στο περίπου..

**** Συμπερασματικά : Το caching του Λ.Σ. βοηθάει πολύ μετά την πρώτη ανάγνωση (ίσως αξίζει μια προσέγγιση με threads), ο χρόνος επεξεργασίας των στοιχείων είναι άρρηκτα συνδεδεμένος και με την ικανότητα του compiler να βελτιστοποιεί τον παραγόμενο κώδικα, το μέγεθος του αναγνωσμένου μπλοκ φαίνεται να λαμβάνει σημασία κατά την ανάγνωση δίχως I/O cache.

--

Αποτελέσματα.

C++ Builder XE
==============

 ** NO BUFFERING **
 Buffer Length = 32768 bytes

TestAlg dwSum: -137930983
1) secs: 6.78
TestAlg dwSum: -137930983
2) secs: 6.61
TestAlg dwSum: -137930983
3) secs: 5.89
 avg: 6.43

 ** WITH BUFFERING **
 Buffer Length = 32768 bytes

TestAlg dwSum: -137930983
1) secs: 5.80
TestAlg dwSum: -137930983
2) secs: 1.61
TestAlg dwSum: -137930983
3) secs: 1.61
 avg: 3.01

 ** NO BUFFERING **
 Buffer Length = 65536 bytes

TestAlg dwSum: -137930983
1) secs: 6.56
TestAlg dwSum: -137930983
2) secs: 5.88
TestAlg dwSum: -137930983
3) secs: 5.80
 avg: 6.08

 ** WITH BUFFERING **
 Buffer Length = 65536 bytes

TestAlg dwSum: -137930983
1) secs: 5.83
TestAlg dwSum: -137930983
2) secs: 1.59
TestAlg dwSum: -137930983
3) secs: 1.59
 avg: 3.01

 ** NO BUFFERING **
 Buffer Length = 131072 bytes

TestAlg dwSum: -137930983
1) secs: 5.84
TestAlg dwSum: -137930983
2) secs: 6.05
TestAlg dwSum: -137930983
3) secs: 5.97
 avg: 5.95

 ** WITH BUFFERING **
 Buffer Length = 131072 bytes

TestAlg dwSum: -137930983
1) secs: 5.81
TestAlg dwSum: -137930983
2) secs: 1.58
TestAlg dwSum: -137930983
3) secs: 1.58
 avg: 2.99

 ** NO BUFFERING **
 Buffer Length = 262144 bytes

TestAlg dwSum: -137930983
1) secs: 6.16
TestAlg dwSum: -137930983
2) secs: 5.84
TestAlg dwSum: -137930983
3) secs: 5.80
 avg: 5.93

 ** WITH BUFFERING **
 Buffer Length = 262144 bytes

TestAlg dwSum: -137930983
1) secs: 5.83
TestAlg dwSum: -137930983
2) secs: 1.59
TestAlg dwSum: -137930983
3) secs: 1.59
 avg: 3.01

 ** NO BUFFERING **
 Buffer Length = 524288 bytes

TestAlg dwSum: -137930983
1) secs: 6.28
TestAlg dwSum: -137930983
2) secs: 6.41
TestAlg dwSum: -137930983
3) secs: 6.50
 avg: 6.40

 ** WITH BUFFERING **
 Buffer Length = 524288 bytes

TestAlg dwSum: -137930983
1) secs: 5.83
TestAlg dwSum: -137930983
2) secs: 1.61
TestAlg dwSum: -137930983
3) secs: 1.61
 avg: 3.02

 ** NO BUFFERING **
 Buffer Length = 1048576 bytes

TestAlg dwSum: -137930983
1) secs: 7.22
TestAlg dwSum: -137930983
2) secs: 7.55
TestAlg dwSum: -137930983
3) secs: 7.25
 avg: 7.34

 ** WITH BUFFERING **
 Buffer Length = 1048576 bytes

TestAlg dwSum: -137930983
1) secs: 5.81
TestAlg dwSum: -137930983
2) secs: 1.62
TestAlg dwSum: -137930983
3) secs: 1.64
 avg: 3.03

Press Enter to exit..

Visual Studio 2010
==================

 ** NO BUFFERING **
 Buffer Length = 32768 bytes

TestAlg dwSum: -137930983
1) secs: 6.91
TestAlg dwSum: -137930983
2) secs: 7.03
TestAlg dwSum: -137930983
3) secs: 6.45
 avg: 6.80

 ** WITH BUFFERING **
 Buffer Length = 32768 bytes

TestAlg dwSum: -137930983
1) secs: 6.36
TestAlg dwSum: -137930983
2) secs: 1.16
TestAlg dwSum: -137930983
3) secs: 1.16
 avg: 2.89

 ** NO BUFFERING **
 Buffer Length = 65536 bytes

TestAlg dwSum: -137930983
1) secs: 6.41
TestAlg dwSum: -137930983
2) secs: 6.36
TestAlg dwSum: -137930983
3) secs: 6.36
 avg: 6.38

 ** WITH BUFFERING **
 Buffer Length = 65536 bytes

TestAlg dwSum: -137930983
1) secs: 6.39
TestAlg dwSum: -137930983
2) secs: 1.14
TestAlg dwSum: -137930983
3) secs: 1.16
 avg: 2.90

 ** NO BUFFERING **
 Buffer Length = 131072 bytes

TestAlg dwSum: -137930983
1) secs: 6.41
TestAlg dwSum: -137930983
2) secs: 6.39
TestAlg dwSum: -137930983
3) secs: 10.03
 avg: 7.61

 ** WITH BUFFERING **
 Buffer Length = 131072 bytes

TestAlg dwSum: -137930983
1) secs: 7.41
TestAlg dwSum: -137930983
2) secs: 1.14
TestAlg dwSum: -137930983
3) secs: 1.14
 avg: 3.23

 ** NO BUFFERING **
 Buffer Length = 262144 bytes

TestAlg dwSum: -137930983
1) secs: 6.41
TestAlg dwSum: -137930983
2) secs: 6.34
TestAlg dwSum: -137930983
3) secs: 6.36
 avg: 6.37

 ** WITH BUFFERING **
 Buffer Length = 262144 bytes

TestAlg dwSum: -137930983
1) secs: 6.38
TestAlg dwSum: -137930983
2) secs: 1.14
TestAlg dwSum: -137930983
3) secs: 1.14
 avg: 2.89

 ** NO BUFFERING **
 Buffer Length = 524288 bytes

TestAlg dwSum: -137930983
1) secs: 6.41
TestAlg dwSum: -137930983
2) secs: 6.67
TestAlg dwSum: -137930983
3) secs: 6.36
 avg: 6.48

 ** WITH BUFFERING **
 Buffer Length = 524288 bytes

TestAlg dwSum: -137930983
1) secs: 6.39
TestAlg dwSum: -137930983
2) secs: 1.28
TestAlg dwSum: -137930983
3) secs: 1.20
 avg: 2.96

 ** NO BUFFERING **
 Buffer Length = 1048576 bytes

TestAlg dwSum: -137930983
1) secs: 6.97
TestAlg dwSum: -137930983
2) secs: 8.00
TestAlg dwSum: -137930983
3) secs: 7.75
 avg: 7.57

 ** WITH BUFFERING **
 Buffer Length = 1048576 bytes

TestAlg dwSum: -137930983
1) secs: 6.34
TestAlg dwSum: -137930983
2) secs: 1.19
TestAlg dwSum: -137930983
3) secs: 1.19
 avg: 2.91

Press Enter to exit..

Καλή συνέχεια.

Επεξ/σία 4 Ιουνίου 2014 από Directx

defacer · 3 Ιουνίου 2014

Παπί έτσι που τα λες τα αποτελέσματα θα είναι κάθε άλλο παρά reusable.

Πάντως αν έπρεπε να κάνω αυτό που λες θα το έκανα έτσι

<?php
$sum = array_sum(array_map('array_sum', array_map('str_getcsv', file('data.csv'))));

και μετά θα πήγαινα για καφέ

παπι · 3 Ιουνίου 2014

Reusable εννοω "οχι hardcoded". Πχ

void TestAlg(const char* filename)
{
	int sum = 0;
	CSVPareser(filename,[&sum](std::vector<char*>& row)
	{
		const size_t count = row.size();
		for(size_t i = 0; i < count ; i++)
			sum += atoi(row[i]);
		
	});
	std::cout<<"Sum:"<<sum<<std::endl;
}

ChRis6 · 3 Ιουνίου 2014

Threads επιτρέπονται ;

defacer · 3 Ιουνίου 2014

		const size_t count = row.size();
		for(size_t i = 0; i < count ; i++)
			sum += atoi(row[i]);

Better θα ήταν range-based for. Even better θα ήταν:

sum = std::accumulate(row.begin(), row.end(), 0, std::plus<int>());

Edit: μόλις συνειδητοποίησα ότι είναι strings οπότε κατευθείαν std::plus δε γίνεται. Αλλά you get the picture.

παπι · 3 Ιουνίου 2014

Οτι να΄ναι. Ειμαι σιγουρος οτι τα iterators ειναι πιο αργα, αλλα αυτο ειναι πιο γρηγορο χαχαχα

void TestAlg2(const char* filename)
{
	int sum = 0;
	CSVPareser1(filename,[&sum](std::vector<CSVVal>& row)
	{
		sum = std::accumulate(row.begin(), row.end(), sum ,std::plus<int>());
		
	});
	std::cout<<"Sum:"<<sum<<std::endl;
}

Threads επιτρέπονται ;

Εαν μπορεις να βαλεις...

migf1 · 3 Ιουνίου 2014

Reusable εννοω "οχι hardcoded". Πχ

void TestAlg(const char* filename)
{
	int sum = 0;
	CSVPareser(filename,[&sum](std::vector<char*>& row)
	{
		const size_t count = row.size();
		for(size_t i = 0; i < count ; i++)
			sum += atoi(row[i]);
		
	});
	std::cout<<"Sum:"<<sum<<std::endl;
}

Με μπέρδεψες, τον παραπάνω κώδικα τον θεωρείς reusable ή "hardcoded"?

Βασικά τι ακριβώς εννοείς λέγοντας "reusable", γιατί εγώ όχι μόνο το έχω κάνει με atoi, αλλά έχω γράψει και δικιά μου myatoi() η οποία είναι προσαρμοσμένη πάνω στα data που δημιουργεί η generateSCV()... π.χ. θεωρώ πως είναι πάντα νούμερα, δεν υπάρχουν leading/trailing spaces, δεν ελέγχω για overflows, κλπ.

EDIT:

Btw, στα νούμερα που έχω δώσει, τα δεύτερα είναι το άθροισμα των 2 iterations.

migf1 · 3 Ιουνίου 2014

Παπι πλάκα μας κάνεις ρε;

Προς το παρόν εγώ βαριέμαι να ασχοληθώ με τις αλλαγές που εκανες, οπότε ποστάρω ότι είχα κάνει για το παλιό. Στα 10 iterations (αντί για 2 που είχε το δείγμα) σε WinXP Pro SP3 32bit με ming32 v4.8.1 παίρνω τα παρακάτω:

/* ---- gcc -O2 --- */
ref: | total:   1.297000 --- avg:   0.129700
alg: | total:   6.062000 --- avg:   0.606200

ref:alg = 1:4.673863

/* ---- gcc --- */
ref: | total:   5.125000 --- avg:   0.512500
alg: | total:  15.203000 --- avg:   1.520300

ref:alg = 1:2.966439

Επίσης, εφόσον δεν μας έχεις διευκρινήσει τι εννοείς "resuable" και τι "hardcoded" εγώ το έκανα με μια χαρά resuable συναρτήσεις

Κώδικας:

extern int64_t f_size( const char *fname ); // http://ideone.com/eCXzVn

/*********************************************************//**
 * 
 *************************************************************
 */
#include <time.h>
static double clock_it( void *userdata, int (*callback)(void *userdata) )
{
	clock_t tstart = clock();

	/* Code we want timed here */
	if ( 0 == (*callback)(userdata) ) {
		return -1.0;
	}

	return ((double) (clock() - tstart)) / CLOCKS_PER_SEC;
}

/*********************************************************//**
 * 
 *************************************************************
 */
static inline int myatoi( const char *str )
{
	int ret  = 0;
	int sign = 1;
	switch (*str) {
		case '-':
			++str;
			sign = -1;
			break;
	}

	char c;
	while ( (c = *str++) ) {
		ret *= 10;
		ret += c - '0';
	}
	if ( ret < 0 )
		return 0;
	switch (sign) {case -1: ret = -ret; break;}
	return ret;
}

/*********************************************************//**
 * 
 *************************************************************
 */
static int TestAlg( void *filename )
{
	char *fname = (char *) filename;
	const size_t BUFSIZE = f_size(fname);
	int sum = 0;
	FILE *fp = fopen( fname,"rb" );
	char *buf = calloc( 1, 1+BUFSIZE );

	fread( buf, 1, BUFSIZE, fp );
	for (char *cp=buf, *pre=buf; *cp; cp++) {
		switch (*cp) {
			case ',':
			case '\n':
				*cp = '\0';
				sum += myatoi(pre);
				pre = 1+cp;
				break;
		}
	}
	free( buf );
	fclose( fp );
	printf( "TestAlg Sum: %d\n", sum );

	return 1;
}

/*********************************************************//**
 * 
 *************************************************************
 */
int TestReference( void *filename )
{
	char *fname = (char *) filename;
	const size_t buf_size = 1024 * 1024;
	size_t readed;
	int sum = 0;
	FILE *file = fopen( fname,"rb" );
	char *buf = malloc( buf_size );
	while( (readed = fread(buf, 1, buf_size, file)) > 0 )
	{
		for (size_t i = 0; i < readed; i++)
			sum += buf[i];
	}
	free( buf );
	fclose(file);
	printf( "TestReference Sum: %d\n", sum );

	return 1;
}

/*********************************************************//**
 * 
 *************************************************************
 */
int main( void )
{
	const char *FNAME = "test.csv";
	const int ITERATIONS = 10;

	//GenerateCSV( FNAME, 1000 * 1000, 20 );

	double elapsed1 = 0.0, total1 = 0.0;
	for (int i=0; i < ITERATIONS; i++)
	{
		elapsed1 = clock_it( (void *)FNAME, TestReference );
		//printf( "ref: %f secs\n", elapsed1 );
		total1 += elapsed1; 
	}
	printf( "ref: | total: %10.6f --- avg: %10.6f\n", total1, total1 / ITERATIONS );

	double elapsed2 = 0.0, total2 = 0.0;
	for (int i=0; i < ITERATIONS; i++)
	{
		elapsed2 = clock_it( (void *)FNAME, TestAlg );
		//printf( "alg: %f secs\n", elapsed2 );
		total2 += elapsed2; 
	}
	printf( "alg: | total: %10.6f --- avg: %10.6f\n", total2, total2 / ITERATIONS );

	printf( "\nref:alg = 1:%f\n\n", total2/total1 );

	return 0;
}

defacer · 4 Ιουνίου 2014

switch (sign) {case -1: ret = -ret; break;}

"Ενδιαφέρον"...

Σύνδεση

coding challenge

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

παπι

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

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

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

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

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

παπι

Directx

Kercyn

Kercyn

παπι

migf1

H_ANARXIA_EINAI_PSEMA

migf1

Directx

defacer

παπι

ChRis6

defacer

παπι

migf1

migf1

defacer

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

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

Σύνδεση

παπι

Directx

Kercyn

Σύνδεση