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