benchmark data set

gsl_permutation_next.test.c

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<assert.h>

typedef struct
{
  size_t size;
  size_t *data;
} gsl_permutation;


gsl_permutation *
gsl_permutation_calloc (const size_t n)
{
  size_t i;
  gsl_permutation * p;

  if (n == 0)
    return NULL;

  p = (gsl_permutation *) malloc (sizeof (gsl_permutation));

  if (p == 0)
    return NULL;

  p->data = (size_t *) malloc (n * sizeof (size_t));

  if (p->data == 0)
    {
      free (p);         /* exception in constructor, avoid memory leak */
      
      return NULL;
    }
  
  for (i = 0; i < n; i++)
    {
      p->data[i] = i;
    }

  p->size = n;

  return p;
}

void
gsl_permutation_free (gsl_permutation * p)
{
  if (p == NULL)
    {
      return;
    }
  free (p->data);
  free (p);
}


int
gsl_permutation_next (gsl_permutation * p)
{
  const size_t size = p->size;
  size_t i, j, k;

  if (size < 2)
    {
      return 1;
    }

  i = size - 2;

  while ((p->data[i] > p->data[i+1]) && (i != 0))
    {
      i--;
    }

  if ((i == 0) && (p->data[0] > p->data[1]))
    {
     return 1;
    }

  k = i + 1;

  for (j = i + 2; j < size; j++ )
    {
      if ((p->data[j] > p->data[i]) && (p->data[j] < p->data[k]))
        {
          k = j;
        }
    }

  /* swap i and k */

  {
    size_t tmp = p->data[i];
    p->data[i] = p->data[k];
    p->data[k] = tmp;
  }

  for (j = i + 1; j <= ((size + i) / 2); j++)
    {
      size_t tmp = p->data[j];
      p->data[j] = p->data[size + i - j];
      p->data[size + i - j] = tmp;
    }

  return 0;
}


int
gsl_permutation_next0 (gsl_permutation * p)
{
  const size_t size = p->size;
  size_t i, j, k;

  if (size < 2)
    {
      return 1;
    }

  i = size - 2;

  while ((p->data[i] > p->data[i+1]) && (i != 0))
    {
      i--;
    }

  if ((i == 0) && (p->data[0] > p->data[1]))
    {
     return 1;
    }

  k = size - 1;

  while(p->data[k] < p->data[i])
    {
        k--;
    }

  /* swap i and k */

  {
    size_t tmp = p->data[i];
    p->data[i] = p->data[k];
    p->data[k] = tmp;
  }

  for (j = i + 1; j <= ((size + i) / 2); j++)
    {
      size_t tmp = p->data[j];
      p->data[j] = p->data[size + i - j];
      p->data[size + i - j] = tmp;
    }
  return 0;
}

int
gsl_permutation_next_correctness (gsl_permutation * p)
{
  const size_t size = p->size;
  size_t i, j, k, k0;

  if (size < 2)
    {
      return 1;
    }

  i = size - 2;

  while ((p->data[i] > p->data[i+1]) && (i != 0))
    {
      i--;
    }

  if ((i == 0) && (p->data[0] > p->data[1]))
    {
     return 1;
    }

  k = i + 1;

  for (j = i + 2; j < size; j++ )
    {
      if ((p->data[j] > p->data[i]) && (p->data[j] < p->data[k]))
        {
          k = j;
        }
    }

  k0 = size - 1;

  while(p->data[k0] < p->data[i])
    {
        k0--;
    }

  assert(k0==k);

  /* swap i and k */

  {
    size_t tmp = p->data[i];
    p->data[i] = p->data[k];
    p->data[k] = tmp;
  }

  for (j = i + 1; j <= ((size + i) / 2); j++)
    {
      size_t tmp = p->data[j];
      p->data[j] = p->data[size + i - j];
      p->data[size + i - j] = tmp;
    }

  return 0;
}

void
gsl_permutation_reverse (gsl_permutation * p)
{
  const size_t size = p->size ;

  size_t i ;

  for (i = 0; i < (size / 2); i++)
    {
      size_t j = size - i - 1;

      size_t tmp = p->data[i] ;
      p->data[i] = p->data[j] ;
      p->data[j] = tmp ;
    }
}


int
gsl_permutation_fprintf (FILE * stream, const gsl_permutation * p, const char *format)
{
  size_t n = p->size ;

  size_t * data = p->data ;

  size_t i;

  for (i = 0; i < n; i++)
    {
      int status = fprintf (stream, format, data[i]);

      if (status < 0)
        return 1;
    }

  return 0;
}

int
main ()
{
  double t0, t1;
  clock_t start, end;
  gsl_permutation * p;
  const size_t N = 12, R = 10;
  size_t r, n;
  for (n = 3; n < N; n++)
    {  
      printf("%zu\t", n);
      p = gsl_permutation_calloc(n);
      //Check correctness
      while(gsl_permutation_next_correctness(p)==0);
      gsl_permutation_reverse(p); 
      for (r = 0; r < R; r++)
        {
          start = clock();
          while(gsl_permutation_next(p) == 0)
          end = clock();
          gsl_permutation_reverse(p);
          printf("%lf\t",(double)(end - start)*1000/CLOCKS_PER_SEC);

          start = clock();
          while(gsl_permutation_next0(p) == 0);
          end = clock();
          gsl_permutation_reverse(p);
          printf("%lf\t",(double)(end - start)*1000/CLOCKS_PER_SEC);
        }
      printf("\n");
      gsl_permutation_free(p);
    }
  return 0;
}