[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: new algorithm for wilcoxon signed-rank test
From: |
John Darrington |
Subject: |
Re: new algorithm for wilcoxon signed-rank test |
Date: |
Thu, 5 Feb 2009 16:16:29 +0900 |
User-agent: |
Mutt/1.5.13 (2006-08-11) |
I think it's quite amazing! I remember thinking when I first put that
routine into pspp, that there was some redundant calculations here,
but then thought that if there was a better way somebody would have
already come up with it ...
One small point about the implementation: It seems that array[0] is
never used. So it count be one int smaller.
J'
----- Forwarded message from Ben Pfaff <address@hidden> -----
To: Ben Pfaff <address@hidden>, John Darrington <address@hidden>,
Michel Boaventura <address@hidden>,
address@hidden
From: Ben Pfaff <address@hidden>
...
Actually, here's a solution that is even better. A test program using it
calculates (correctly) and prints *all* the values for 1 <= N <= 30, 1 <=
W <=
N*(N+1)/2, in under .2 seconds *total*.
The runtime of this algorithm is O(N*W) and it uses O(W) space.
int ranksum6(int N, int W)
{
int *array;
int max;
int total;
assert (N >= 0);
if (N == 0)
return 0;
else if (W <= 0)
return 1 << N;
else if (W > N * (N + 1) / 2)
return 0;
else if (N == 1)
return 1;
array = calloc (sizeof *array, W + 1);
array[W] = 1;
max = W;
total = 0;
for (; N > 1; N--)
{
int max_sum = N * (N + 1) / 2;
int i;
if (max_sum < max)
max = max_sum;
for (i = 1; i <= max; i++)
if (array[i] != 0)
{
int new_W = i - N;
if (new_W <= 0)
total += array[i] * (1 << (N - 1));
else
array[new_W] += array[i];
}
}
total += array[1];
free (array);
return total;
}
--
PGP Public key ID: 1024D/2DE827B3
fingerprint = 8797 A26D 0854 2EAB 0285 A290 8A67 719C 2DE8 27B3
See http://pgp.mit.edu or any PGP keyserver for public key.
signature.asc
Description: Digital signature