flashsort.h (5310B)
1 #pragma once
2
3 /**
4 * \file
5 *
6 * type safe flashsort implementation
7 *
8 * flashsort is in the classification sort category (no string compare) and sorts numbers (int, uint, float, ...).
9 *
10 * struct and pointer elements in the input array are supported
11 *
12 *
13 * the performance depends on how uniform is the distribution,
14 * the more uniform the better (high variance).
15 *
16 * adjust the m parameter (number of classes) to change the performance/memory usage ratio.
17 *
18 * when the variance is high, a m/size ratio of 0.1 gives good performance and low memory usage.
19 *
20 * an array of size m * sizeof(size_t) is allocated the heap and then freed
21 *
22 *
23 * Example:
24 *
25 * // declare an array
26 * typ struct {
27 * i32 key;
28 * i32 value;
29 * } elemt;
30 *
31 * elemt array[1000];
32 *
33 * // define flashsortGet
34 * #define flashsortGet(ptr) (ptr)->key
35 *
36 * // call flashsort
37 * flashsort(array, ARRAY_SIZE(array));
38 *
39 * // or call flashsortM to be able to set the number of classes
40 * // flashsortM(array, ARRAY_SIZE(array), 0.43 * ARRAY_SIZE(array));
41 *
42 * #undef flashsortGet
43 */
44
45
46 /**
47 * flashsort with predefined m/size ratio for high variance distributions
48 *
49 * the flashsortGet macro or function has to be defined before calling flashsortM
50 * flashsortGet takes an address in parameter and returns a key
51 *
52 * \param
53 * arr array to sort
54 * \param
55 * size number of elements in the array
56 */
57 #define flashsort(arr, size) flashsortM(arr, size, size / 16 /* m classes */)
58
59
60
61
62
63 // ********
64 // internal helper macros
65 #define flashsortSubKMacro(num)\
66 if (num > 0 and min < 0)\
67 k = c * ((toUnsignedType(num))(num) + (toUnsignedType(num))(-min)) + 1;\
68 else\
69 k = c * ((num) - min) + 1
70 // end internal helper macros
71
72
73 // ********
74 /**
75 * flashsort with predefined m/size ratio for high variance distributions
76 *
77 * the flashsortGet macro or function has to be defined before calling flashsortM
78 * flashsortGet takes an address in parameter and returns a key
79 *
80 * \param
81 * arr array to sort, this parameter is evaluated multiple times,
82 * it cannot be a value returned by a function that changes during the flashsort execution
83 * \param
84 * size number of elements in the array
85 * \param
86 * m number of classes
87 */
88 #define flashsortM(arr, asize, mc) do {\
89 size_t UNIQVAR(size) = asize;\
90 size_t UNIQVAR(m) = mc;\
91 if (UNIQVAR(m) < 2) {\
92 logE("number of class m is too low: %zu", UNIQVAR(m));\
93 break;\
94 }\
95 /* Phase 1*/\
96 var min = flashsortGet(&arr[0]);\
97 var max = flashsortGet(&arr[0]);\
98 /* added { to isolate variable definition in range */\
99 {rangeFrom(i, 0, UNIQVAR(size)) {\
100 min = MIN(flashsortGet(&arr[i]), min);\
101 max = MAX(flashsortGet(&arr[i]), max);\
102 /*logVarG(i);\
103 logI("v %u %d", flashsortGet(&arr[i]), flashsortGet(&arr[i)]);\
104 logI("min %u max %u", min, max);\
105 logVarG(flashsortGet(&arr[i)]);\
106 logVarG(arr[i]);\
107 logVarG(flashsortGet(&arr[i]));*/\
108 }}\
109 \
110 /*logVarG(min);\
111 logVarG(max);*/\
112 \
113 if (min == max)\
114 break;\
115 \
116 /* Divide to UNIQVAR(m) class */\
117 /* c could be float instead of double, but the performance is better with double (intel skylake cpu) */\
118 double c;\
119 /* avoid overflow */\
120 if (max > 0 and min < 0)\
121 c = (double)(UNIQVAR(m) - 1) / ((toUnsignedType(max))max + (toUnsignedType(min))(-min));\
122 else\
123 c = (double)(UNIQVAR(m) - 1) / (max - min);\
124 /*logVarG(UNIQVAR(m));\
125 logVarG((double)c);*/\
126 \
127 size_t *L = callocArray(L, UNIQVAR(m) + 1);\
128 /* added { to isolate variable definition in range */\
129 {range(i, UNIQVAR(size)) {\
130 size_t k;\
131 flashsortSubKMacro(flashsortGet(&arr[i]));\
132 /* L[k]: the number of class K */\
133 L[k]++;\
134 }}\
135 /* added { to isolate variable definition in range */\
136 {rangeFrom(k, 2, UNIQVAR(m)+1) {\
137 /* L[k]: upper bound of class K */\
138 L[k] += L[k - 1];\
139 }}\
140 \
141 /* Phase 2 */\
142 /* number of move */\
143 size_t move = 0;\
144 size_t j = 0;\
145 size_t k = UNIQVAR(m);\
146 /* Only move UNIQVAR(size) - 1 step */\
147 while (move < UNIQVAR(size) - 1)\
148 {\
149 /* flashsortGet(&arr[j]) is in right class */\
150 while (j >= L[k])\
151 {\
152 j++;\
153 flashsortSubKMacro(flashsortGet(&arr[j]));\
154 }\
155 /* temp to hold the value */\
156 var flash = flashsortGet(&arr[j]);\
157 var flashEl = arr[j];\
158 /* stop when flashsortGet(&arr[j]) is changed */\
159 while (j < L[k])\
160 {\
161 flashsortSubKMacro(flash);\
162 /* swap */\
163 var tmpEl = flashEl;\
164 flashEl = arr[--L[k]];\
165 arr[L[k]] = tmpEl;\
166 flash = flashsortGet(&flashEl);\
167 move++;\
168 }\
169 }\
170 \
171 /* Phase 3
172 Use Insertion sort for every class
173 Don't sort the UNIQVAR(m) class,
174 Because the UNIQVAR(m) class is all max */\
175 rangeFrom(k, 1, UNIQVAR(m)) {\
176 for (size_t i = L[k] + 1; i < L[k + 1]; i++) {\
177 var key = flashsortGet(&arr[i]);\
178 var keyEl = arr[i];\
179 i64 j = i - 1;\
180 while (j >= 0 and flashsortGet(&arr[j]) > key)\
181 {\
182 arr[j+1] = arr[j];\
183 j--;\
184 }\
185 arr[j+1] = keyEl;\
186 }\
187 }\
188 free(L);\
189 }while(0)
190
191 // vim: set expandtab ts=2 sw=2: