vecops.c

数据挖掘中的关联规则算法

      n   = (mid -off < BUFSIZE) ? mid -off : BUFSIZE;
      src = (int*)vec +mid -n;  /* get number of elements and */
      dst = buf;                /* copy source to the buffer */
      for (i = n;        --i >= 0; ) *dst++ = *src++;
      dst = (int*)vec +mid -n;  /* shift down/left second section */
      for (i = end -mid; --i >= 0; ) *dst++ = *src++;
      src = buf;                /* copy buffer to destination */
      for (i = n;        --i >= 0; ) *dst++ = *src++;
      mid -= n; end -= n;       /* second section has been shifted */
    } }                         /* down/left cnt elements */
  else {                        /* if second section is smaller */
    while (end > mid) {         /* while there are elements to shift */
      n   = (end -mid < BUFSIZE) ? end -mid : BUFSIZE;
      src = (int*)vec +mid +n;  /* get number of elements and */
      dst = buf +n;             /* copy source to the buffer */
      for (i = n;        --i >= 0; ) *--dst = *--src;
      dst = (int*)vec +mid +n;  /* shift up/right first section */
      for (i = mid -off; --i >= 0; ) *--dst = *--src;
      src = buf +n;             /* copy buffer to destination */
      for (i = n;        --i >= 0; ) *--dst = *--src;
      mid += n; off += n;       /* first section has been shifted */
    }                           /* up/right cnt elements */
  }
}  /* v_move() */

/*--------------------------------------------------------------------*/

void v_shuffle (void *vec, int n, double randfn (void))
{                               /* --- shuffle vector entries */
  int  i;                       /* vector index */
  void **v = vec, *t;           /* vector and exchange buffer */

  while (--n > 0) {             /* shuffle loop (n random selections) */
    i = (int)((n+1) *randfn()); /* compute a random index */
    if (i > n) i = n;           /* in the remaining section and */
    if (i < 0) i = 0;           /* exchange the vector elements */
    t = v[i]; v[i] = v[n]; v[n] = t;
  }
}  /* v_shuffle() */

/*--------------------------------------------------------------------*/

void v_reverse (void *vec, int n)
{                               /* --- reverse a pointer vector */
  void **v, *t;                 /* vector and exchange buffer */

  for (v = vec; --n > 0; ) {    /* reverse the order of the elements */
    t = v[n]; v[n] = v[0]; *v++ = t; }
}  /* v_reverse() */

/*--------------------------------------------------------------------*/

#define REC(type,rec) \
static void rec (type *vec, int n) \
{                               /* --- recursive part of sort */       \
  type *l, *r;                  /* pointers to exchange positions */   \
  type x, t;                    /* pivot element and exchange buffer */\
  int  m;                       /* number of elements in sections */   \
                                                                       \
  do {                          /* sections sort loop */               \
    l = vec; r = l +n -1;       /* start at left and right boundary */ \
    if (*l > *r) { t = *l; *l = *r; *r = t; }                          \
    x = vec[n >> 1];            /* get the middle element as pivot */  \
    if      (x < *l) x = *l;    /* compute median of three */          \
    else if (x > *r) x = *r;    /* to find a better pivot */           \
    while (1) {                 /* split and exchange loop */          \
      while (*++l < x)          /* skip left  elements that are */     \
        ;                       /* smaller than the pivot element */   \
      while (*--r > x)          /* skip right elements that are */     \
        ;                       /* greater than the pivot element */   \
      if (l >= r) {             /* if less than two elements left, */  \
        if (l <= r) { l++; r--; } break; }       /* abort the loop */  \
      t = *l; *l = *r; *r = t;  /* otherwise exchange elements */      \
    }                                                                  \
    m = (int)(vec +n -l);       /* compute the number of elements */   \
    n = (int)(r -vec +1);       /* right and left of the split */      \
    if (n > m) {                /* if right section is smaller, */     \
      if (m >= TH_INSERT)       /* but larger than the threshold, */   \
        rec(l, m); }            /* sort it by an recursive call */     \
    else {                      /* if the left section is smaller, */  \
      if (n >= TH_INSERT)       /* but larger than the threshold, */   \
        rec(vec, n);            /* sort it by an recursive call, */    \
      vec = l; n = m;           /* then switch to the right section */ \
    }                           /* keeping its size m in variable n */ \
  } while (n >= TH_INSERT);     /* while greater than threshold */     \
}  /* rec() */

/*--------------------------------------------------------------------*/

#define SORT(type,rec,sort) \
void sort (type *vec, int n) \
{                               /* --- sort a number vector */         \
  int  k;                       /* size of first section */            \
  type *l, *r;                  /* to traverse the vector */           \
  type t;                       /* exchange buffer */                  \
                                                                       \
  assert(vec && (n >= 0));      /* check the function arguments */     \
  if (n <= 1) return;           /* do not sort less than two elems. */ \
  if (n < TH_INSERT)            /* if less elements than threshold */  \
    k = n;                      /* for insertion sort, note the */     \
  else {                        /* number of elements, otherwise */    \
    rec(vec, n);                /* call the recursive sort function */ \
    k = TH_INSERT -1;           /* and get the number of elements */   \
  }                             /* in the first vector section */      \
  for (l = r = vec; --k > 0; )  /* find position of smallest element */\
    if (*++r < *l) l = r;       /* within the first k elements */      \
  r = vec;                      /* swap the smallest element */        \
  t = *l; *l = *r; *r = t;      /* to front as a sentinel */           \
  while (--n > 0) {             /* standard insertion sort */          \
    t = *++r;                   /* note the number to insert */        \
    for (l = r; *--l > t; k--)  /* shift right all numbers that are */ \
      l[1] = *l;                /* greater than the one to insert */   \
    l[1] = t;                   /* and store the number to insert */   \
  }                             /* in the place thus found */          \
}  /* sort() */

/*--------------------------------------------------------------------*/

REC (int,    _intrec)
SORT(int,    _intrec, v_intsort)

/*--------------------------------------------------------------------*/

REC (float,  _fltrec)
SORT(float,  _fltrec, v_fltsort)

/*--------------------------------------------------------------------*/

REC (double, _dblrec)
SORT(double, _dblrec, v_dblsort)

/*--------------------------------------------------------------------*/

#define REVERSE(type,reverse) \
void reverse (type *vec, int n) \
{                               /* --- reverse a number vector */      \
  type t;                       /* exchange buffer */                  \
  while (--n > 0) {             /* reverse the order of the elems. */  \
    t = vec[n]; vec[n] = vec[0]; *vec++ = t; }                         \
}  /* reverse() */

/*--------------------------------------------------------------------*/

REVERSE(int,    v_intrev)
REVERSE(float,  v_fltrev)
REVERSE(double, v_dblrev)