Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 01 Sep 2011 23:41:04 -0500
Message-ID: <4E605E61.3B94@mindspring.com>
Date: Fri, 02 Sep 2011 00:41:05 -0400
From: pete <pfiland@mindspring.com>
Reply-To: pfiland@mindspring.com
Organization: PF
X-Mailer: Mozilla 3.04Gold (WinNT; I)
MIME-Version: 1.0
Newsgroups: comp.lang.c
Subject: Re: My latest magnum opus!
References: <4E60142A.575D@mindspring.com> <j3palv$5tj$1@dont-email.me> <4E603F93.19F@mindspring.com> <4E604653.7407@mindspring.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Lines: 242
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 4.156.228.74
X-Trace: sv3-uj2gyL9Rh3fsYDQEMKo4IDEBVTAeCIbrgmUgXQ25QgO66D3eAApyRYyH+vhOZhTQkbHQNXJzuZxGa5t!J7YMmCggiDQSGF55tqZV9wblvlVhk0aCc/lxYW7aUkcDsg7apRGKgNIoU6YnFDaxtsZiAxoK0UN/!/3PQ0ixBXA==
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 7896
Xref: x330-a1.tempe.blueboxinc.net comp.lang.c:9868

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