fkvkselect.c
Go to the documentation of this file.
1 
11 #include <GKlib.h>
12 
13 /* Byte-wise swap two items of size SIZE. */
14 #define QSSWAP(a, b, stmp) do { stmp = (a); (a) = (b); (b) = stmp; } while (0)
15 
16 
17 /******************************************************************************/
19 /*******************************************************************************/
20 int gk_dfkvkselect(size_t n, int topk, gk_fkv_t *cand)
21 {
22  int i, j, lo, hi, mid;
23  gk_fkv_t stmp;
24  float pivot;
25 
26  if (n <= topk)
27  return n; /* return if the array has fewer elements than we want */
28 
29  for (lo=0, hi=n-1; lo < hi;) {
30  mid = lo + ((hi-lo) >> 1);
31 
32  /* select the median */
33  if (cand[lo].key < cand[mid].key)
34  mid = lo;
35  if (cand[hi].key > cand[mid].key)
36  mid = hi;
37  else
38  goto jump_over;
39  if (cand[lo].key < cand[mid].key)
40  mid = lo;
41 
42 jump_over:
43  QSSWAP(cand[mid], cand[hi], stmp);
44  pivot = cand[hi].key;
45 
46  /* the partitioning algorithm */
47  for (i=lo-1, j=lo; j<hi; j++) {
48  if (cand[j].key >= pivot) {
49  i++;
50  QSSWAP(cand[i], cand[j], stmp);
51  }
52  }
53  i++;
54  QSSWAP(cand[i], cand[hi], stmp);
55 
56 
57  if (i > topk)
58  hi = i-1;
59  else if (i < topk)
60  lo = i+1;
61  else
62  break;
63  }
64 
65 /*
66  if (cand[lo].key < cand[hi].key)
67  printf("Hmm Error: %d %d %d %f %f\n", i, lo, hi, cand[lo].key, cand[hi].key);
68 
69 
70  for (i=topk; i<n; i++) {
71  for (j=0; j<topk; j++)
72  if (cand[i].key > cand[j].key)
73  printf("Hmm Error: %d %d %f %f %d %d\n", i, j, cand[i].key, cand[j].key, lo, hi);
74  }
75 */
76 
77  return topk;
78 }
79 
80 
81 /******************************************************************************/
83 /*******************************************************************************/
84 int gk_ifkvkselect(size_t n, int topk, gk_fkv_t *cand)
85 {
86  int i, j, lo, hi, mid;
87  gk_fkv_t stmp;
88  float pivot;
89 
90  if (n <= topk)
91  return n; /* return if the array has fewer elements than we want */
92 
93  for (lo=0, hi=n-1; lo < hi;) {
94  mid = lo + ((hi-lo) >> 1);
95 
96  /* select the median */
97  if (cand[lo].key > cand[mid].key)
98  mid = lo;
99  if (cand[hi].key < cand[mid].key)
100  mid = hi;
101  else
102  goto jump_over;
103  if (cand[lo].key > cand[mid].key)
104  mid = lo;
105 
106 jump_over:
107  QSSWAP(cand[mid], cand[hi], stmp);
108  pivot = cand[hi].key;
109 
110  /* the partitioning algorithm */
111  for (i=lo-1, j=lo; j<hi; j++) {
112  if (cand[j].key <= pivot) {
113  i++;
114  QSSWAP(cand[i], cand[j], stmp);
115  }
116  }
117  i++;
118  QSSWAP(cand[i], cand[hi], stmp);
119 
120 
121  if (i > topk)
122  hi = i-1;
123  else if (i < topk)
124  lo = i+1;
125  else
126  break;
127  }
128 
129 /*
130  if (cand[lo].key > cand[hi].key)
131  printf("Hmm Error: %d %d %d %f %f\n", i, lo, hi, cand[lo].key, cand[hi].key);
132 
133 
134  for (i=topk; i<n; i++) {
135  for (j=0; j<topk; j++)
136  if (cand[i].key < cand[j].key)
137  printf("Hmm Error: %d %d %f %f %d %d\n", i, j, cand[i].key, cand[j].key, lo, hi);
138  }
139 */
140 
141  return topk;
142 }
const gtsam::Symbol key('X', 0)
int n
int gk_ifkvkselect(size_t n, int topk, gk_fkv_t *cand)
Definition: fkvkselect.c:84
#define QSSWAP(a, b, stmp)
Definition: fkvkselect.c:14
std::ptrdiff_t j
int gk_dfkvkselect(size_t n, int topk, gk_fkv_t *cand)
Definition: fkvkselect.c:20


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:34:13