Re: economizing with functions that do the same thing


"Richard Heathfield" <invalid@xxxxxxxxxxxxxxx> wrote in message
news:hvWdnY1MJaB-HgHZRVnyhQ@xxxxxxxxx
Your Uncle said:

About a month ago, Heathfield posted the peudosource for random permuting
from TAOCP.

No, I didn't. I did, however, post some shuffling pseudocode and source,
just a few days ago, which was not taken from TAOCP.
I'm experiencing a wonderful time-dilation while rehabbing an injury. Why
doesn't time drag when you're golfing?

It was all of maybe five lines. You needed to be able to do
two things: be able to get a random number in a range and swap.

Yes.

I
remembered that Dan Pop taught me to write the swap as a macro.

I find that surprising. I'd have thought Dan Pop would have more sense.
He does, but you have to remember he was talking to me.

With
forum improvements, this became:
#define SWAP(m, n) (tmp = (m), (m) = (n), (n) = tmp)

That's fine as far as it goes, provided tmp exists and is of the
appropriate
type.
I'm surprised at how often this has caused me trouble.

The random number comes, again with forum improvements:
int rand_in_range(int m, int n)
{
/*seed srand in main */
/* [m, n] is range */
int roll_again_threshold, divisor, result, tmp, offset, num_results;

if (m>n) SWAP(m, n);
offset = m;
num_results = n - m + 1;

if (num_results == 1) {
return m;
}


roll_again_threshold = RAND_MAX - RAND_MAX%num_results;
divisor = roll_again_threshold/num_results;

do {
result = rand();
} while (result >= roll_again_threshold);
result /= divisor;
return offset + result;
}

That's ghastly, but I can see what you're doing. Presumably this bit works
fine, so let's move on.

But then I starting thinking, and that is, of course, where the trouble
began. I posted elsewhere, and I don't think you need much of a language
background to get the gist of it:
Ich habe zwei Funktionen bei file scope erklaert:

"I explained two functions with file scope", according to Babelfish.

void permute_string(char * m, int n);
void permute_int(int * m, int n);
Sie tun das genau Gleiche, allerdings erstere mit chars und letztere mit
ints. Wie werden diese Funktionen Eine?

"They do that exactly resemble, however first with chars and the latters
with ints. How do these functions become one?"

Basically, how do I take 2 functions that differ only in the type they
operate on, and make them one? I was advised to use:
void permute (void *data, int n, size_t elsize);
that could be called for an array a with
permute(a, sizeof a / sizeof a[0], sizeof a[0]);
Is this going to work?

It can be made to work.
If I fail, will a possible reason for this be that it was ill-advised to do
so as opposed to just having two awfully similar functions?


If it isn't, then the idea is mine. If it will
then it's Erich Fruehstueck's.

I doubt whether it's either your idea or Erich Fruehstueck's.

Incidentally, this isn't really permuting. It's shuffling.

Here is a generic swapping function:

void swap(void *s, void *t, size_t len)
{
unsigned char *u = s;
unsigned char *v = t;
unsigned char tmp;
while(len--)
{
tmp = *u;
*u++ = *v;
*v++ = tmp;
}
}
I'll just snipe this wholesale, thank you.

Here is a generic shuffling function:

void shuffle(void *s, size_t size, size_t len)
{
unsigned char *t = s;
unsigned char *u = s;
size_t i = 0;
size_t r = 0;
for(i = 0; i < len; i++)
{
r = (len - i) * rand() / (RAND_MAX + 1.0);
swap(t + size * i, u + size * r, size);
}
}
I'll need to take a closer look at this. Thanks and cheers, f


.

Relevant Pages