You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
142 lines
3.2 KiB
142 lines
3.2 KiB
/*!
|
|
\file dfkvkselect.c
|
|
\brief Sorts only the largest k values
|
|
|
|
\date Started 7/14/00
|
|
\author George
|
|
\version\verbatim $Id: fkvkselect.c 10711 2011-08-31 22:23:04Z karypis $\endverbatim
|
|
*/
|
|
|
|
|
|
#include <GKlib.h>
|
|
|
|
/* Byte-wise swap two items of size SIZE. */
|
|
#define QSSWAP(a, b, stmp) do { stmp = (a); (a) = (b); (b) = stmp; } while (0)
|
|
|
|
|
|
/******************************************************************************/
|
|
/*! This function puts the 'topk' largest values in the beginning of the array */
|
|
/*******************************************************************************/
|
|
int gk_dfkvkselect(size_t n, int topk, gk_fkv_t *cand)
|
|
{
|
|
int i, j, lo, hi, mid;
|
|
gk_fkv_t stmp;
|
|
float pivot;
|
|
|
|
if (n <= topk)
|
|
return n; /* return if the array has fewer elements than we want */
|
|
|
|
for (lo=0, hi=n-1; lo < hi;) {
|
|
mid = lo + ((hi-lo) >> 1);
|
|
|
|
/* select the median */
|
|
if (cand[lo].key < cand[mid].key)
|
|
mid = lo;
|
|
if (cand[hi].key > cand[mid].key)
|
|
mid = hi;
|
|
else
|
|
goto jump_over;
|
|
if (cand[lo].key < cand[mid].key)
|
|
mid = lo;
|
|
|
|
jump_over:
|
|
QSSWAP(cand[mid], cand[hi], stmp);
|
|
pivot = cand[hi].key;
|
|
|
|
/* the partitioning algorithm */
|
|
for (i=lo-1, j=lo; j<hi; j++) {
|
|
if (cand[j].key >= pivot) {
|
|
i++;
|
|
QSSWAP(cand[i], cand[j], stmp);
|
|
}
|
|
}
|
|
i++;
|
|
QSSWAP(cand[i], cand[hi], stmp);
|
|
|
|
|
|
if (i > topk)
|
|
hi = i-1;
|
|
else if (i < topk)
|
|
lo = i+1;
|
|
else
|
|
break;
|
|
}
|
|
|
|
/*
|
|
if (cand[lo].key < cand[hi].key)
|
|
printf("Hmm Error: %d %d %d %f %f\n", i, lo, hi, cand[lo].key, cand[hi].key);
|
|
|
|
|
|
for (i=topk; i<n; i++) {
|
|
for (j=0; j<topk; j++)
|
|
if (cand[i].key > cand[j].key)
|
|
printf("Hmm Error: %d %d %f %f %d %d\n", i, j, cand[i].key, cand[j].key, lo, hi);
|
|
}
|
|
*/
|
|
|
|
return topk;
|
|
}
|
|
|
|
|
|
/******************************************************************************/
|
|
/*! This function puts the 'topk' smallest values in the beginning of the array */
|
|
/*******************************************************************************/
|
|
int gk_ifkvkselect(size_t n, int topk, gk_fkv_t *cand)
|
|
{
|
|
int i, j, lo, hi, mid;
|
|
gk_fkv_t stmp;
|
|
float pivot;
|
|
|
|
if (n <= topk)
|
|
return n; /* return if the array has fewer elements than we want */
|
|
|
|
for (lo=0, hi=n-1; lo < hi;) {
|
|
mid = lo + ((hi-lo) >> 1);
|
|
|
|
/* select the median */
|
|
if (cand[lo].key > cand[mid].key)
|
|
mid = lo;
|
|
if (cand[hi].key < cand[mid].key)
|
|
mid = hi;
|
|
else
|
|
goto jump_over;
|
|
if (cand[lo].key > cand[mid].key)
|
|
mid = lo;
|
|
|
|
jump_over:
|
|
QSSWAP(cand[mid], cand[hi], stmp);
|
|
pivot = cand[hi].key;
|
|
|
|
/* the partitioning algorithm */
|
|
for (i=lo-1, j=lo; j<hi; j++) {
|
|
if (cand[j].key <= pivot) {
|
|
i++;
|
|
QSSWAP(cand[i], cand[j], stmp);
|
|
}
|
|
}
|
|
i++;
|
|
QSSWAP(cand[i], cand[hi], stmp);
|
|
|
|
|
|
if (i > topk)
|
|
hi = i-1;
|
|
else if (i < topk)
|
|
lo = i+1;
|
|
else
|
|
break;
|
|
}
|
|
|
|
/*
|
|
if (cand[lo].key > cand[hi].key)
|
|
printf("Hmm Error: %d %d %d %f %f\n", i, lo, hi, cand[lo].key, cand[hi].key);
|
|
|
|
|
|
for (i=topk; i<n; i++) {
|
|
for (j=0; j<topk; j++)
|
|
if (cand[i].key < cand[j].key)
|
|
printf("Hmm Error: %d %d %f %f %d %d\n", i, j, cand[i].key, cand[j].key, lo, hi);
|
|
}
|
|
*/
|
|
|
|
return topk;
|
|
}
|
|
|