Page 2 of 4 FirstFirst 1234 LastLast
Results 11 to 20 of 39

Thread: C/C++ Test - Category Looping & Optimising - Level Medium

  1. #11
    Join Date
    Apr 2004
    Posts
    554
    Rep Power
    0

    Default

    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

  2. #12
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Default

    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
    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;
        }
    }
    It is situated in two for loops and gives a time of .540 second with VC6++ release execution

    Now the code
    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;
        }
    }
    with the for loop not commented out, it gives a time of 0.230 after more than one test.

    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

  3. #13
    Join Date
    Apr 2004
    Posts
    554
    Rep Power
    0

    Default

    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

  4. #14
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Default

    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

  5. #15
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Default

    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

  6. #16
    Join Date
    Apr 2004
    Posts
    554
    Rep Power
    0

    Default

    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

  7. #17
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Default

    Hmmm when you have the time try the release build

    This is the inexplicable optimisation I came across


    Without line 90 commented

    Debug run
    Code:
    selcount = 2403193
    Program takes 1.201 seconds.
    Press any key to continue . . .
    Release run
    Code:
    selcount = 2403193
    Program takes 0.390 seconds.
    Press any key to continue . . .
    With line 90 commented (modified code below)

    Debug run
    Code:
    selcount = 2403193
    Program takes 1.822 seconds.
    Press any key to continue . . .
    Release run
    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

  8. #18
    Join Date
    Apr 2004
    Posts
    554
    Rep Power
    0

    Default

    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

  9. #19
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Default

    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

  10. #20
    Join Date
    Sep 2004
    Posts
    1,905
    Rep Power
    21

    Default

    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

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •