Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #9868

Re: My latest magnum opus!

Show all headers | View raw

pete wrote:
> 
> pete wrote:
> >
> > Eric Sosman wrote:
> > >
> > > On 9/1/2011 7:24 PM, pete wrote:
> > > > /* BEGIN block_swap_test.c */
> > > > [...]
> > >
> > >      Jon Bentley tackled this problem in one of his "Programming
> > > Pearls" columns in CACM, years and years ago.  IIRC, he reported
> > > that he had seen manymanymany attempts to solve it "efficiently"
> > > with clever analysis of which block was the larger, and by how much,
> > > and so on and so forth.  He also reported that every such solution
> > > he'd seen was either bug-ridden or actually slower than
> > >
> > >         Given an array A...FR...Z, to arrive at R...ZA...F:
> > >         Reverse the A...F sequence byte for byte
> > >         Reverse the R...Z sequence byte for byte
> > >         Reverse the entire array byte for byte
> > >
> > >      I have not examined your code closely -- in truth, I have not
> > > even examined it cursorily.  The very fact that it's longer than
> > > Bentley's solution tells me it's almost certainly inferior; Bentley's
> > > is certainly easier to analyze for correctness.
> >
> > I'll look into it.
> > Thank you.
> 
> Well, I've written it.
> Now I have to time it.
> 
> I'm optimistic though.
> The solution that you gave me,
> always does
> (lo_size - 1) / 2 + (hi_size - 1) / 2 + (lo_size + hi_size - 1) / 2
> swaps.
> That's the worst case for the function that I wrote.

I Win!
by a slight amount, on the implementation that I'm using,
in a test that I contrived, with a slightly microoptimised
version of the function that I originally posted (block_swap), 
against the first version that popped into my head
of the algorithm that you described (block_swap2).

/* BEGIN block_swap_time.c output */

No Discrepancies!

block_swap time is 5.390000
block_swap2 time is 5.547000

The array has 15000 long unsigned elements.

/* END block_swap_time.c output */

I made an (original) array of 15000 long unsigned
ans populated it with a prng and the I made a (copy) of it.
I tested block_swap against block_swap2 by using
block_swap to swap all the possible combinations of
block sizes in the (copy), and by each time using block_swap2
to undo the swap. Then I checked to make sure
that the copy was restored to be the same as the original, 
and it was.

Then I tested each function and timed them.
The advantage that block_swap has over block_swap2
is that there is a best case for block_swap,
which is when the blocks being swapped are of equal sizes,
then it only does about half as many swaps
    ((lo_size + hi_size) / 2)
as block_swap2 does.
block_swap also has intermediate cases.

/* BEGIN block_swap_time.c */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define SIZE    15000
#define str(s)  # s
#define xstr(s) str(s)

void block_swap(void *base, size_t lo_size, size_t hi_size);
void block_swap2(void *base, size_t lo_size, size_t hi_size);

int 
main(void)
{
    clock_t start, stop;
    double time;
    long unsigned lu_seed = 123456789LU;
    long unsigned *original;
    long unsigned *copy;
    size_t right;
    size_t left;

    original = malloc(SIZE * sizeof *original);
    copy = malloc(SIZE * sizeof *copy);
    if (original == NULL || copy == NULL) {
        puts("\noriginal == NULL || copy == NULL\n");
        exit(EXIT_FAILURE);
    }

    for (right = 0; right != SIZE; ++right) {
        original[right] = lu_seed;
        lu_seed = lu_seed * 69069 + 362437;
    }
    memcpy(copy, original, SIZE);
    
    left = 0;
    right = SIZE;
    puts("/* BEGIN block_swap_time.c output */\n");
    do {
        block_swap(copy, left, right);
        block_swap2(copy, right, left);
        if (memcmp(copy, original, SIZE) != 0) {
            free(copy);
            free(original);
            puts("Discrepancy!\n");
            exit(EXIT_SUCCESS);
        }
        ++left;
    } while (--right != 0);
    puts("No Discrepancies!\n"); 

    left = 0;
    right = SIZE;
    stop = clock();
    do {
        start = clock();
    } while (start == stop);
    do {
        block_swap(copy, left, right);
        block_swap(copy, right, left);
        ++left;
    } while (--right != 0);
    stop = clock();
    time = (double)(stop - start) / (double)CLOCKS_PER_SEC;
    printf("block_swap time is %f\n", time); 
    
    left = 0;
    right = SIZE;
    stop = clock();
    do {
        start = clock();
    } while (start == stop);
    do {
        block_swap2(copy, left, right);
        block_swap2(copy, right, left);
        ++left;
    } while (--right != 0);   
    stop = clock();
    time = (double)(stop - start) / (double)CLOCKS_PER_SEC;
    printf("block_swap2 time is %f\n\n", time);

    puts("The array has " xstr(SIZE) 
        " long unsigned elements.\n");
    if (memcmp(copy, original, SIZE) != 0) {
        puts("\nThere's a problem!\n");
    }
    free(copy);
    free(original);
    puts("/* END block_swap_time.c output */");
    return 0;
}

void 
block_swap(void *base, size_t lo_size, size_t hi_size)
{
    size_t mod;
    unsigned char *end, *middle, swap;
    
    mod = lo_size != 0 && hi_size != 0;
    while (mod != 0) {
        end = base;
        middle = end + lo_size;
        if (hi_size > lo_size) {
            mod = hi_size % lo_size;
            hi_size -= mod;
            base = end + hi_size;
            do {
                swap = *end;
                *end++ = *middle;
                *middle++ = swap;
            } while (--hi_size != 0);
            hi_size = mod;
        } else {
            mod = lo_size % hi_size;
            lo_size -= mod;
            end = middle + hi_size;
            do {
                swap = *--middle;
                *middle = *--end;
                *end = swap;
            } while (--lo_size != 0);
            lo_size = mod;
        }
    }
}

void 
block_swap2(void *base, size_t lo_size, size_t hi_size)
{
    unsigned char *first, *middle, *after, swap;

    if (lo_size == 0 || hi_size == 0) {
        return;
    }
    first = base;
    middle = first + lo_size;
    while (--middle > first) {
        swap = *middle;
        *middle = *first;
        *first++ = swap;
    }
    first = base;
    middle = first + lo_size;
    after = middle + hi_size;
    while (--after > middle) {
        swap = *after;
        *after = *middle;
        *middle++ = swap;
    }
    first = base;
    after = first + lo_size + hi_size;
    while (--after > first) {
        swap = *after;
        *after = *first;
        *first++ = swap;
    }
}

/* END block_swap_time.c */


-- 
pete

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-01 19:24 -0400
  Re: My latest magnum opus! Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-01 21:13 -0400
    Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-01 22:29 -0400
      Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-01 22:58 -0400
        Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-02 00:41 -0400
    Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-02 00:53 -0400
    Re: My latest magnum opus! cri@tiac.net (Richard Harter) - 2011-09-02 05:39 +0000
      Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-02 02:59 -0400
      Re: My latest magnum opus! Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-02 08:21 -0400
        Re: My latest magnum opus! cri@tiac.net (Richard Harter) - 2011-09-02 13:39 +0000
          Re: My latest magnum opus! Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-02 20:53 -0400
            Re: My latest magnum opus! James Dow Allen <jdallen2000@yahoo.com> - 2011-09-03 03:18 -0700
            Re: My latest magnum opus! cri@tiac.net (Richard Harter) - 2011-09-03 17:16 +0000
    Re: My latest magnum opus! Andrey Tarasevich <andreytarasevich@hotmail.com> - 2011-09-02 09:21 -0700
  Re: My latest magnum opus! ImpalerCore <jadill33@gmail.com> - 2011-09-06 06:51 -0700
    Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-06 18:36 -0400
    Re: My latest magnum opus! Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-06 21:04 -0400

csiph-web