sherwood.c

Sherwood算法消除最坏实例

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define SLkListLen 1000

int val[SLkListLen+1];
int ptr[SLkListLen+1];
int head = 0, tail = 0;
long st_search = 0;
long st_As = 0;
long st_Bs = 0;
long st_Cs = 0;
long st_Ds = 0;

/***start the search from (i)th to the end, if not found, return 0 ***/
int search(int x, int i){
  if( st_search++, x < val[i])
    return 0;
  while( st_search++, x > val[i] && i != 0)
    i = ptr[i];
  if( st_search++, x == val[i])
    return i;
  else
    return 0;
}

/*************** As **************/
int As(int x){
  return search(x, head);
}

/*************** Ds **************/
int Ds(int x){
  int i;
  int y;

  i = rand() % SLkListLen + 1;
  y = val[i]; st_Ds++;
  if(x < y)
    return search(x, head);
  else if(x > y)
    return search(x, ptr[i]);
  else
    return i;
}

/*************** Bs **************/
int Bs(int x){
  int i, j;
  int y, max;

  i = head;
  max = val[i]; /*initial value is the minimal value*/
  st_Bs++;
  for(j = 1; j <= (int)(sqrt(SLkListLen)); j++){
  /*find the maximal value in the first sqrt(SLkListLen) values not bigger than x */
    y = val[j]; st_Bs++;
    if(max < y && y <= x){
      i = j; max = y;
    }
  }
  return search(x, i);
}

/*************** Cs **************/
int Cs(int x){ /* a Sherwood algorithm revised from algorithm B */
  int i, j, k;
  int y, max;

  i = head;
  max = val[i]; /*initial value is the minimal value*/
  st_Cs++;
  /*srand( (unsigned)time( NULL ) );*/
  for(j = 1; j <= (int)(sqrt(SLkListLen)); j++){
  /*find the maximal value in random sqrt(SLkListLen) values not bigger than x */
    k = rand() % SLkListLen + 1;
    y = val[k]; st_Cs++;
    if(max < y && y <= x){
      i = k; max = y;
    }
  }
  return search(x, i);
}

/***********statistic**************/
void statistic(){
  int i, j, n, x;
  unsigned long sum;
  double averg, averg0;
  
  printf("\ninput the times to run: ");
  scanf("%d", &n);
  val[0] = val[head] - 1;

  sum = 0, averg = 0.0, averg0 = 0.0;
  for(i = 0; i <= SLkListLen +1; i++){
    if(i == SLkListLen +1)
      x = val[tail] + 1;
    else
      x = val[i];
    for(j = 0; j < n; j++){
      As(x);
      sum = sum + st_As + st_search;
      st_As = st_search = 0;
    }
    averg = averg + sum*1.0 / n;
    sum = 0;
  }
  averg0 = averg / (SLkListLen + 2);
  printf("average access times to array val[] of A: %8f\n", averg0);

  sum = 0, averg = 0.0, averg0 = 0.0;
  for(i = 0; i <= SLkListLen +1; i++){
    if(i == SLkListLen +1)
      x = val[tail] + 1;
    else
      x = val[i];
    for(j = 0; j < n; j++){
      Bs(x);
      sum = sum + st_Bs + st_search;
      st_Bs = st_search = 0;
    }
    averg = averg + sum*1.0 / n;
    sum = 0;
  }
  averg0 = averg / (SLkListLen + 2);
  printf("average access times to array val[] of B: %8f\n", averg0);

  sum = 0, averg = 0.0, averg0 = 0.0;
  for(i = 0; i <= SLkListLen +1; i++){
    if(i == SLkListLen +1)
      x = val[tail] + 1;
    else
      x = val[i];
    for(j = 0; j < n; j++){
      Cs(x);
      sum = sum + st_Cs + st_search;
      st_Cs = st_search = 0;
    }
    averg = averg + sum*1.0 / n;
    sum = 0;
  }
  averg0 = averg / (SLkListLen + 2);
  printf("average access times to array val[] of C: %8f\n", averg0);

  sum = 0, averg = 0.0, averg0 = 0.0;
  for(i = 0; i <= SLkListLen +1; i++){
    if(i == SLkListLen +1)
      x = val[tail] + 1;
    else
      x = val[i];
    for(j = 0; j < n; j++){
      Ds(x);
      sum = sum + st_Ds + st_search;
      st_Ds = st_search = 0;
    }
    averg = averg + sum*1.0 / n;
    sum = 0;
  }
  averg0 = averg / (SLkListLen + 2);
  printf("average access times to array val[] of D: %8f\n", averg0);
}

/*********** sort **************/
void sort(){
  int i;
  int pre, p;

  ptr[0] = 1; ptr[1] = 0;
  for(i = 2; i <= SLkListLen; i++){
    pre = 0; p = ptr[pre];
    while(val[i] > val[p] && p != 0){
      pre = ptr[pre];
      p =ptr[pre];
    }
    ptr[i] = p;
    ptr[pre] = i;
  }
}

/***********main**************/
main(int argc, char *argv[]){
  int x;
  int i, n, p;
  FILE *infp;

  if(argc == 1){
    infp = stdin;
    n = SLkListLen;
    printf("input array val[]'s %d values: ", n);
  }
  else if(argc == 2){
    if( (infp = fopen(argv[1], "r")) == NULL){
      printf("Can't open the file!\n");
      exit(2);
    }
  }
  else{
    printf("Usage: %s              get val[]'s values from stdin\n", argv[0]);
    printf("       %s filename     get val[]'s values from file on disk\n", argv[0]);
    exit(1);
  }

  for(i = 1; i <= SLkListLen; i++)
    fscanf(infp, "%d", &val[i]);
  fclose(infp);

  sort();
/*
  printf("val: ");
  for(i = 1; i <= SLkListLen; i++)
    printf("%d ", val[i]);
  printf("\nptr: ");
  for(i = 1; i <= SLkListLen; i++)
    printf("%d ", ptr[i]);
  printf("\nhead: %d\n", ptr[0]);

  p = ptr[0];
  for(i = 1; i <= SLkListLen; i++){
    if(i == SLkListLen) tail = p;
    printf("%d ", val[p]);
    p = ptr[p];
  }
*/
  head = ptr[0];

  i = 1; 
  srand( (unsigned)time( NULL ) );
  while(i){
    statistic();
    printf("press<0> exit, press<1> again\n");
    scanf("%d", &i);
  }
}