I don't think it was corny at all. Couple times well I was ready to mash up mi PC when the program wouldn't loop properly!! Looking forward to your optimised code.
I don't think it was corny at all. Couple times well I was ready to mash up mi PC when the program wouldn't loop properly!! Looking forward to your optimised code.
Nexus S - Android 2.3.3 CM7, Jame Bond kernel with BLN, ext4 & full voodoo
Bold 9700 - OS6.0.0.448
Have been working on the optimisation.
I came upon this unexplainable behaviour. There was a time increase from 230 to 540.
I have the code with on line commented out
It is situated in two for loops and gives a time of .540 second with VC6++ release executionCode:for(int i = 0; i < lengthneeded; i++) { if(digit[i] < max_digit_val) { digit[i]++; int temp = digit[i]; //for(i--; i >= 0; i--) { digit[i] = temp; } break; } }
Now the code
with the for loop not commented out, it gives a time of 0.230 after more than one test.Code:for(int i = 0; i < lengthneeded; i++) { if(digit[i] < max_digit_val) { digit[i]++; int temp = digit[i]; for(i--; i >= 0; i--) { digit[i] = temp; } break; } }
Why is this, I am just curious.
Last edited by crosswire; Apr 23, 2005 at 11:25 PM.
Let's act on what we agree on now, and argue later on what we don't.
Black men leave Barbeque alone if Barbeque don't trouble you
Hmmm...... I would have thought it would be the other way around.
Nexus S - Android 2.3.3 CM7, Jame Bond kernel with BLN, ext4 & full voodoo
Bold 9700 - OS6.0.0.448
That I thought too, because the overhead of the loop must be greater?!? I cannot explain it.
BTW digit is an int type so that should not be so slow
Let's act on what we agree on now, and argue later on what we don't.
Black men leave Barbeque alone if Barbeque don't trouble you
Here is the optimised code.
Run the release build to get the full effect of the optimization. This is because the functions are not inline in Debug mode, whereas such optimisations takes place in the Release builds. I got mine up to 0.370 secs
Code:// Compiler VC6.0++ #include <time.h> #include <string.h> #include <stdio.h> #include <stdlib.h> /* An xary number is a number which has the base x Eg Binary numbers, x = 2 xary numbers can have any base and any lenght */ typedef int digit_type; #include <memory.h> class xary_number { private: bool xary_number_is_zero; bool xary_number_is_max; bool xary_number_is_init; digit_type max_digit_val; //eg for decimal number, max digit val is 9 digit_type * digit; //All digits in the binary number, eg decimal 3457224024 int xary; //The base of the number eg binary, octal, etc for now only boolean int lengthneeded; //The number of digits in the number, eg 256 digit hexal, 11 digit hexal public: xary_number(int x = 2, int l = 256) { xary_number_is_init = false; init_xary_number(x, l); }; ~xary_number() { delete [] digit; }; void init_xary_number(int x = 2, int l = 256) { //Initialize number xary = x; lengthneeded = l; max_digit_val = x - 1;//1 for binary //create the space for our digits if(xary_number_is_init) delete [] digit; digit = new digit_type[lengthneeded]; //Zero the digits memset(digit, 0x00, lengthneeded*sizeof(digit_type)); //Initialize some miscellaneous states xary_number_is_zero = true; xary_number_is_max = false; xary_number_is_init = true; } void goto_next_selection() //follows the pattern 000, 001, 002, 003, 011, 012, 013, 022, 023, 033, 111, 112, 113, 122, 123, 133, 222, 223, 233, 333 for a 4ary number { for(int i = 0; i < lengthneeded; i++) { //Removed overflow build up /* if(digit[i] == max_digit_val) { //needed for miscelaneous is 0 digit[i] = 0; continue; } else */ if(digit[i] < max_digit_val) { digit[i]++; //all previous digit equal this digit digit_type temp = digit[i]; //digit_type * ptr_next_digit = &(digit[i-1]); for(i--; i >= 0; i--) { digit[i] = temp; //*ptr_next_digit-- = temp; } break; } } //Removed overflow check /* //Sets the miscellaneous state to zero if the number overflows to zero set_if_zero(); //Returns the miscellaneous state return is_zero(); */ } bool is_xary_the_same_as(const digit_type test_xary[]) const { //Testing from highest digit to lowest for(int i = lengthneeded - 1; i >= 0; i--) { if(digit[i] != test_xary[i]) { return false; } } return true; } }; int main() { //Time declarations clock_t start, finish; double elapsed_time; //Input declarations FILE * stream; stream = fopen( "input.txt", "r" ); if( stream == NULL ) { printf("Error opening file"); return 0; } //Getting the first number int N; fscanf(stream, "%d", &N); //Getting the test string char S[129]; fscanf(stream, "%s", &S); fclose(stream); start = clock(); //code start here //Convert S from a string ABC to an integer arr 123 #define MAX_STR_LEN 128 int Sxary[MAX_STR_LEN];//Assign enough storage space for String array counters for(int i = 0; i < N; i++) { //The first character in the string is the highest digit in the integer array //Sxary use the same amount of counters as the input string lenght Sxary[N - i - 1] = S[i] - 'A'; } const char display_chs[] = "ABCDE"; xary_number sel; int selcount = 0; sel.init_xary_number(strlen(display_chs), N); while(true) { //selcount is the position counter selcount++; //instead of strcmp, compare the integer arrays if(sel.is_xary_the_same_as(Sxary)) break; //go from AAA to AAB...AAE to ABB sel.goto_next_selection(); } printf("selcount = %d", selcount); //code end here finish = clock(); elapsed_time = (double)(finish - start) / CLOCKS_PER_SEC; printf( "\nProgram takes %0.3f seconds.\n", elapsed_time ); system("pause"); return 1; }
Let's act on what we agree on now, and argue later on what we don't.
Black men leave Barbeque alone if Barbeque don't trouble you
Showing 1.390 on my pc. A lot faster! I clocked mine at .001 using the clock() function you used rather than the difftime() i was using earlier which returns an int.
Last edited by nigelt; Apr 24, 2005 at 01:33 AM.
Nexus S - Android 2.3.3 CM7, Jame Bond kernel with BLN, ext4 & full voodoo
Bold 9700 - OS6.0.0.448
Hmmm when you have the time try the release build
This is the inexplicable optimisation I came across
Without line 90 commented
Debug runRelease runCode:selcount = 2403193 Program takes 1.201 seconds. Press any key to continue . . .With line 90 commented (modified code below)Code:selcount = 2403193 Program takes 0.390 seconds. Press any key to continue . . .
Debug runRelease runCode:selcount = 2403193 Program takes 1.822 seconds. Press any key to continue . . .Code:selcount = 2403193 Program takes 0.530 seconds. Press any key to continue . . .Code:// Compiler VC6.0++ #include <time.h> #include <string.h> #include <stdio.h> #include <stdlib.h> /* An xary number is a number which has the base x Eg Binary numbers, x = 2 xary numbers can have any base and any lenght */ typedef int digit_type; #include <memory.h> class xary_number { private: bool xary_number_is_zero; bool xary_number_is_max; bool xary_number_is_init; digit_type max_digit_val; //eg for decimal number, max digit val is 9 digit_type * digit; //All digits in the binary number, eg decimal 3457224024 int xary; //The base of the number eg binary, octal, etc for now only boolean int lengthneeded; //The number of digits in the number, eg 256 digit hexal, 11 digit hexal public: xary_number(int x = 2, int l = 256) { xary_number_is_init = false; init_xary_number(x, l); }; ~xary_number() { delete [] digit; }; void init_xary_number(int x = 2, int l = 256) { //Initialize number xary = x; lengthneeded = l; max_digit_val = x - 1;//1 for binary //create the space for our digits if(xary_number_is_init) delete [] digit; digit = new digit_type[lengthneeded]; //Zero the digits memset(digit, 0x00, lengthneeded*sizeof(digit_type)); //Initialize some miscellaneous states xary_number_is_zero = true; xary_number_is_max = false; xary_number_is_init = true; } void goto_next_selection() //follows the pattern 000, 001, 002, 003, 011, 012, 013, 022, 023, 033, 111, 112, 113, 122, 123, 133, 222, 223, 233, 333 for a 4ary number { for(int i = 0; i < lengthneeded; i++) { //Removed overflow build up /* if(digit[i] == max_digit_val) { //needed for miscelaneous is 0 digit[i] = 0; continue; } else */ if(digit[i] < max_digit_val) { digit[i]++; //all previous digit equal this digit digit_type temp = digit[i]; //digit_type * ptr_next_digit = &(digit[i-1]); //for(i--; i >= 0; i--) { digit[i] = temp; //*ptr_next_digit-- = temp; } break; } } //Removed overflow check /* //Sets the miscellaneous state to zero if the number overflows to zero set_if_zero(); //Returns the miscellaneous state return is_zero(); */ } bool is_xary_the_same_as(const digit_type test_xary[]) const { //Testing from highest digit to lowest for(int i = lengthneeded - 1; i >= 0; i--) { if(digit[i] != test_xary[i]) { return false; } } return true; } }; int main() { //Time declarations clock_t start, finish; double elapsed_time; //Input declarations FILE * stream; stream = fopen( "input.txt", "r" ); if( stream == NULL ) { printf("Error opening file"); return 0; } //Getting the first number int N; fscanf(stream, "%d", &N); //Getting the test string char S[129]; fscanf(stream, "%s", &S); fclose(stream); start = clock(); //code start here //Convert S from a string ABC to an integer arr 123 #define MAX_STR_LEN 128 int Sxary[MAX_STR_LEN];//Assign enough storage space for String array counters for(int i = 0; i < N; i++) { //The first character in the string is the highest digit in the integer array //Sxary use the same amount of counters as the input string lenght Sxary[N - i - 1] = S[i] - 'A'; } const char display_chs[] = "ABCDE"; xary_number sel; int selcount = 0; sel.init_xary_number(strlen(display_chs), N); /* Testing commented line 90 */ while(true) { selcount++; if(selcount == 2403193) { break; } //go from AAA to AAB...AAE to ABB sel.goto_next_selection(); } printf("selcount = %d", selcount); //code end here finish = clock(); elapsed_time = (double)(finish - start) / CLOCKS_PER_SEC; printf( "\nProgram takes %0.3f seconds.\n", elapsed_time ); system("pause"); return 1; }
Last edited by crosswire; Apr 24, 2005 at 01:57 AM.
Let's act on what we agree on now, and argue later on what we don't.
Black men leave Barbeque alone if Barbeque don't trouble you
Time I got on the release build for your code was 1.015. I'll try it on another PC on Monday. I'm still trying to figure out that difference in times. Weird.
Nexus S - Android 2.3.3 CM7, Jame Bond kernel with BLN, ext4 & full voodoo
Bold 9700 - OS6.0.0.448
The time I got on your code was about the same as mine.
0.4 secs
My machine is Celeron 1.7
Let's act on what we agree on now, and argue later on what we don't.
Black men leave Barbeque alone if Barbeque don't trouble you
OK on Monday.
The page is loaded
Let's act on what we agree on now, and argue later on what we don't.
Black men leave Barbeque alone if Barbeque don't trouble you