[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Bug-gsl] Slow gsl_permutation_valid()
From: |
Rajeev Ayyagari |
Subject: |
[Bug-gsl] Slow gsl_permutation_valid() |
Date: |
Thu, 6 Nov 2003 11:42:28 -0500 (EST) |
Hello,
This is a suggestion rather than a bug report. The function
gsl_permutation_valid() in the current version (1.4) takes \Theta(1)
memory and runs in \Theta(n^2) time (where n is the size of the
permutation). It could be rewritten to use \Theta(n) memory and run in
\Theta(n) time. The time savings can be very significant if n is large (n
> 2000).
Here's an example of the faster implementation.
int myGslPermutationValid( gsl_permutation *p )
{
int *watch = (int *) cmalloc(p -> size);
for ( size_t i = 0; i < p -> size; i++ )
{
if ( p -> data[i] >= p -> size )
{
free( watch );
return GSL_FAILURE;
}
if ( watch[p -> data[i]] )
{
free( watch );
return GSL_FAILURE;
}
else
watch[p -> data[i]] = 1;
}
free( watch );
return GSL_SUCCESS;
}
Regards,
Rajeev.
- [Bug-gsl] Slow gsl_permutation_valid(),
Rajeev Ayyagari <=