1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 package org.apache.commons.numbers.examples.jmh.arrays;
19
20 /**
21 * A strategy to pick two pivot indices of an array for partitioning.
22 *
23 * <p>An ideal strategy will pick the tertiles across a variety of data so
24 * to divide the data into [1/3, 1/3, 1/3].
25 *
26 * @see <a href="https://en.wiktionary.org/wiki/tertile">Tertile (Wiktionary)</a>
27 * @since 1.2
28 */
29 enum DualPivotingStrategy {
30 /**
31 * Pivot around the medians at 1/3 and 2/3 of the range.
32 *
33 * <p>Requires {@code right - left >= 2}.
34 *
35 * <p>On sorted data the tertiles are: 0.3340 0.6670
36 * <p>On random data the tertiles are:
37 * <pre>
38 * min max mean sd median skew
39 * [1] 0.0000 0.9970 0.3327 0.2357 0.2920 0.5654
40 * [2] 0.0020 1.0000 0.3346 0.2356 0.2940 0.5675
41 * [3] 0.0000 0.9970 0.3328 0.2356 0.2920 0.5656
42 * </pre>
43 */
44 MEDIANS {
45 @Override
46 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
47 // Original 'medians' method from the dual-pivot quicksort paper by Vladimir Yaroslavskiy
48 final int len = right - left;
49 // Do not pivot at the ends by setting 1/3 to at least 1.
50 // This is safe if len >= 2.
51 final int third = Math.max(1, len / 3);
52 final int m1 = left + third;
53 final int m2 = right - third;
54 // Ensure p1 is lower
55 if (data[m1] < data[m2]) {
56 pivot2[0] = m2;
57 return m1;
58 }
59 pivot2[0] = m1;
60 return m2;
61 }
62
63 @Override
64 int[] getSampledIndices(int left, int right) {
65 final int len = right - left;
66 final int third = Math.max(1, len / 3);
67 final int m1 = left + third;
68 final int m2 = right - third;
69 return new int[] {m1, m2};
70 }
71
72 @Override
73 int samplingEffect() {
74 return UNCHANGED;
75 }
76 },
77 /**
78 * Pivot around the 2nd and 4th values from 5 approximately uniformly spaced within the range.
79 * Uses points +/- sixths from the median: 1/6, 1/3, 1/2, 2/3, 5/6.
80 *
81 * <p>Requires {@code right - left >= 4}.
82 *
83 * <p>Warning: This has the side effect that the 5 values are also sorted.
84 *
85 * <p>On sorted data the tertiles are: 0.3290 0.6710
86 * <p>On random data the tertiles are:
87 * <pre>
88 * min max mean sd median skew
89 * [1] 0.0010 0.9820 0.3327 0.1778 0.3130 0.4650
90 * [2] 0.0030 0.9760 0.3348 0.1778 0.3150 0.4665
91 * [3] 0.0010 0.9870 0.3325 0.1779 0.3130 0.4698
92 * </pre>
93 */
94 SORT_5 {
95 @Override
96 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
97 // 1/6 = 5/30 ~ 1/8 + 1/32 + 1/64 : 0.1666 ~ 0.1719
98 // Ensure the value is above zero to choose different points!
99 // This is safe if len >= 4.
100 final int len = right - left;
101 final int sixth = 1 + (len >>> 3) + (len >>> 5) + (len >>> 6);
102 final int p3 = left + (len >>> 1);
103 final int p2 = p3 - sixth;
104 final int p1 = p2 - sixth;
105 final int p4 = p3 + sixth;
106 final int p5 = p4 + sixth;
107 Sorting.sort5(data, p1, p2, p3, p4, p5);
108 pivot2[0] = p4;
109 return p2;
110 }
111
112 @Override
113 int[] getSampledIndices(int left, int right) {
114 final int len = right - left;
115 final int sixth = 1 + (len >>> 3) + (len >>> 5) + (len >>> 6);
116 final int p3 = left + (len >>> 1);
117 final int p2 = p3 - sixth;
118 final int p1 = p2 - sixth;
119 final int p4 = p3 + sixth;
120 final int p5 = p4 + sixth;
121 return new int[] {p1, p2, p3, p4, p5};
122 }
123
124 @Override
125 int samplingEffect() {
126 return SORT;
127 }
128 },
129 /**
130 * Pivot around the 2nd and 4th values from 5 approximately uniformly spaced within the range.
131 * Uses points +/- sevenths from the median: 3/14, 5/14, 1/2, 9/14, 11/14.
132 *
133 * <p>Requires {@code right - left >= 4}.
134 *
135 * <p>Warning: This has the side effect that the 5 values are also sorted.
136 *
137 * <p>On sorted data the tertiles are: 0.3600 0.6400
138 * <p>On random data the tertiles are:
139 * <pre>
140 * min max mean sd median skew
141 * [1] 0.0010 0.9790 0.3330 0.1780 0.3140 0.4665
142 * [2] 0.0030 0.9800 0.3348 0.1778 0.3150 0.4681
143 * [3] 0.0010 0.9770 0.3322 0.1777 0.3130 0.4677
144 * </pre>
145 */
146 SORT_5B {
147 @Override
148 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
149 // 1/7 = 5/35 ~ 1/8 + 1/64 : 0.1429 ~ 0.1406
150 // Ensure the value is above zero to choose different points!
151 // This is safe if len >= 4.
152 final int len = right - left;
153 final int seventh = 1 + (len >>> 3) + (len >>> 6);
154 final int p3 = left + (len >>> 1);
155 final int p2 = p3 - seventh;
156 final int p1 = p2 - seventh;
157 final int p4 = p3 + seventh;
158 final int p5 = p4 + seventh;
159 Sorting.sort5(data, p1, p2, p3, p4, p5);
160 pivot2[0] = p4;
161 return p2;
162 }
163
164 @Override
165 int[] getSampledIndices(int left, int right) {
166 final int len = right - left;
167 final int seventh = 1 + (len >>> 3) + (len >>> 6);
168 final int p3 = left + (len >>> 1);
169 final int p2 = p3 - seventh;
170 final int p1 = p2 - seventh;
171 final int p4 = p3 + seventh;
172 final int p5 = p4 + seventh;
173 return new int[] {p1, p2, p3, p4, p5};
174 }
175
176 @Override
177 int samplingEffect() {
178 return SORT;
179 }
180 },
181 /**
182 * This strategy is the same as {@link #SORT_5B} with the exception that it
183 * returns identical pivots if the data at the chosen pivots is equal.
184 *
185 * <p>This allows testing switching to a single pivot strategy against using
186 * a dual pivot partitioning with effectively only 1 pivot. This requires
187 * the dual pivot partition function to check pivot1 == pivot2. If the
188 * dual pivot partition function checks data[pivot1] == data[pivot2] then
189 * the switching choice cannot be enabled/disabled by changing pivoting strategy
190 * and must use another mechanism.
191 *
192 * <p>This specific strategy has been selected for single-pivot switching as
193 * {@link #SORT_5B} benchmarks as consistently fast across all data input.
194 */
195 SORT_5B_SP {
196 @Override
197 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
198 final int pivot1 = SORT_5B.pivotIndex(data, left, right, pivot2);
199 if (data[pivot1] == data[pivot2[0]]) {
200 // Here 3 of 5 middle values are the same.
201 // Present single-pivot pivot methods would not
202 // have an advantage pivoting on p2, p3, or p4; just use 'p2'
203 pivot2[0] = pivot1;
204 }
205 return pivot1;
206 }
207
208 @Override
209 int[] getSampledIndices(int left, int right) {
210 return SORT_5B.getSampledIndices(left, right);
211 }
212
213 @Override
214 int samplingEffect() {
215 return SORT;
216 }
217 },
218 /**
219 * Pivot around the 2nd and 4th values from 5 approximately uniformly spaced within the range.
220 * Uses points +/- eights from the median: 1/4, 3/8, 1/2, 5/8, 3/4.
221 *
222 * <p>Requires {@code right - left >= 4}.
223 *
224 * <p>Warning: This has the side effect that the 5 values are also sorted.
225 *
226 * <p>On sorted data the tertiles are: 0.3750 0.6250
227 * <p>On random data the tertiles are:
228 * <pre>
229 * min max mean sd median skew
230 * [1] 0.0010 0.9790 0.3324 0.1779 0.3130 0.4666
231 * [2] 0.0030 0.9850 0.3348 0.1778 0.3150 0.4686
232 * [3] 0.0010 0.9720 0.3327 0.1779 0.3130 0.4666
233 * </pre>
234 */
235 SORT_5C {
236 @Override
237 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
238 // 1/8 = 0.125
239 // Ensure the value is above zero to choose different points!
240 // This is safe if len >= 4.
241 final int len = right - left;
242 final int eighth = 1 + (len >>> 3);
243 final int p3 = left + (len >>> 1);
244 final int p2 = p3 - eighth;
245 final int p1 = p2 - eighth;
246 final int p4 = p3 + eighth;
247 final int p5 = p4 + eighth;
248 Sorting.sort5(data, p1, p2, p3, p4, p5);
249 pivot2[0] = p4;
250 return p2;
251 }
252
253 @Override
254 int[] getSampledIndices(int left, int right) {
255 final int len = right - left;
256 final int eighth = 1 + (len >>> 3);
257 final int p3 = left + (len >>> 1);
258 final int p2 = p3 - eighth;
259 final int p1 = p2 - eighth;
260 final int p4 = p3 + eighth;
261 final int p5 = p4 + eighth;
262 return new int[] {p1, p2, p3, p4, p5};
263 }
264
265 @Override
266 int samplingEffect() {
267 return SORT;
268 }
269 },
270 /**
271 * Pivot around the 2nd and 4th values from 5 medians approximately uniformly spaced within
272 * the range. The medians are from 3 samples. The 5 samples of 3 do not overlap thus this
273 * method requires {@code right - left >= 14}. The samples can be visualised as 5 sorted
274 * columns:
275 *
276 * <pre>
277 * v w x y z
278 * 1 2 3 4 5
279 * a b c d e
280 * </pre>
281 *
282 * <p>The pivots are points 2 and 4. The other points are either known to be below or
283 * above the pivots; or potentially below or above the pivots.
284 *
285 * <p>Pivot 1: below {@code 1,a,b}; potentially below {@code v,c,d,e}. This ranks
286 * pivot 1 from 4/15 to 8/15 and exactly 5/15 if the input data is sorted/reverse sorted.
287 *
288 * <p>Pivot 2: above {@code 5,y,z}; potentially above {@code e,v,w,x}. This ranks
289 * pivot 2 from 7/15 to 11/15 and exactly 10/15 if the input data is sorted/reverse sorted.
290 *
291 * <p>Warning: This has the side effect that the 15 samples values are partially sorted.
292 *
293 * <p>On sorted data the tertiles are: 0.3140 0.6860
294 * <p>On random data the tertiles are:
295 * <pre>
296 * min max mean sd median skew
297 * [1] 0.0090 0.9170 0.3783 0.1320 0.3730 0.2107
298 * [2] 0.0030 0.8950 0.2438 0.1328 0.2270 0.6150
299 * [3] 0.0110 0.9140 0.3779 0.1319 0.3730 0.2114
300 * </pre>
301 * <p>Note the bias towards the outer regions.
302 */
303 SORT_5_OF_3 {
304 @Override
305 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
306 // Step size of 1/16 of the length
307 final int len = right - left;
308 final int step = Math.max(1, len >>> 4);
309 final int step3 = step * 3;
310 final int p3 = left + (len >>> 1);
311 final int p2 = p3 - step3;
312 final int p1 = p2 - step3;
313 final int p4 = p3 + step3;
314 final int p5 = p4 + step3;
315 // 5 medians of 3
316 Sorting.sort3(data, p1 - step, p1, p1 + step);
317 Sorting.sort3(data, p2 - step, p2, p2 + step);
318 Sorting.sort3(data, p3 - step, p3, p3 + step);
319 Sorting.sort3(data, p4 - step, p4, p4 + step);
320 Sorting.sort3(data, p5 - step, p5, p5 + step);
321 // Sort the medians
322 Sorting.sort5(data, p1, p2, p3, p4, p5);
323 pivot2[0] = p4;
324 return p2;
325 }
326
327 @Override
328 int[] getSampledIndices(int left, int right) {
329 final int len = right - left;
330 final int step = Math.max(1, len >>> 4);
331 final int step3 = step * 3;
332 final int p3 = left + (len >>> 1);
333 final int p2 = p3 - step3;
334 final int p1 = p2 - step3;
335 final int p4 = p3 + step3;
336 final int p5 = p4 + step3;
337 return new int[] {
338 p1 - step, p1, p1 + step,
339 p2 - step, p2, p2 + step,
340 p3 - step, p3, p3 + step,
341 p4 - step, p4, p4 + step,
342 p5 - step, p5, p5 + step,
343 };
344 }
345
346 @Override
347 int samplingEffect() {
348 return PARTIAL_SORT;
349 }
350 },
351 /**
352 * Pivot around the 2nd and 3rd values from 4 medians approximately uniformly spaced within
353 * the range. The medians are from 3 samples. The 4 samples of 3 do not overlap thus this
354 * method requires {@code right - left >= 11}. The samples can be visualised as 4 sorted
355 * columns:
356 *
357 * <pre>
358 * w x y z
359 * 1 2 3 4
360 * a b c d
361 * </pre>
362 *
363 * <p>The pivots are points 2 and 3. The other points are either known to be below or
364 * above the pivots; or potentially below or above the pivots.
365 *
366 * <p>Pivot 1: below {@code 1,a,b}; potentially below {@code w,c,d}. This ranks
367 * pivot 1 from 4/12 to 7/12 and exactly 5/12 if the input data is sorted/reverse sorted.
368 *
369 * <p>Pivot 2: above {@code 4,y,z}; potentially above {@code d,w,x}. This ranks
370 * pivot 2 from 5/15 to 8/12 and exactly 7/12 if the input data is sorted/reverse sorted.
371 *
372 * <p>Warning: This has the side effect that the 12 samples values are partially sorted.
373 *
374 * <p>On sorted data the tertiles are: 0.3850 0.6160
375 * <p>On random data the tertiles are:
376 * <pre>
377 * min max mean sd median skew
378 * [1] 0.0160 0.9580 0.4269 0.1454 0.4230 0.1366
379 * [2] 0.0020 0.8270 0.1467 0.1193 0.1170 1.1417
380 * [3] 0.0140 0.9560 0.4264 0.1453 0.4230 0.1352
381 * </pre>
382 * <p>Note the large bias towards the outer regions.
383 */
384 SORT_4_OF_3 {
385 @Override
386 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
387 // Step size of 1/13 of the length: 1/13 ~ 1/16 + 1/64 : 0.0769 ~ 0.0781
388 final int len = right - left;
389 final int step = Math.max(1, (len >>> 4) + (len >>> 6));
390 final int step3 = step * 3;
391 final int p1 = left + (step << 1) - 1;
392 final int p2 = p1 + step3;
393 final int p3 = p2 + step3;
394 final int p4 = p3 + step3;
395 // 5 medians of 3
396 Sorting.sort3(data, p1 - step, p1, p1 + step);
397 Sorting.sort3(data, p2 - step, p2, p2 + step);
398 Sorting.sort3(data, p3 - step, p3, p3 + step);
399 Sorting.sort3(data, p4 - step, p4, p4 + step);
400 // Sort the medians
401 Sorting.sort4(data, p1, p2, p3, p4);
402 pivot2[0] = p3;
403 return p2;
404 }
405
406 @Override
407 int[] getSampledIndices(int left, int right) {
408 final int len = right - left;
409 final int step = Math.max(1, (len >>> 4) + (len >>> 6));
410 final int step3 = step * 3;
411 final int p1 = left + (step << 1) - 1;
412 final int p2 = p1 + step3;
413 final int p3 = p2 + step3;
414 final int p4 = p3 + step3;
415 return new int[] {
416 p1 - step, p1, p1 + step,
417 p2 - step, p2, p2 + step,
418 p3 - step, p3, p3 + step,
419 p4 - step, p4, p4 + step,
420 };
421 }
422
423 @Override
424 int samplingEffect() {
425 return PARTIAL_SORT;
426 }
427 },
428 /**
429 * Pivot around the 1st and 3rd values from 3 medians approximately uniformly spaced within
430 * the range. The medians are from 3 samples. The 3 samples of 3 do not overlap thus this
431 * method requires {@code right - left >= 8}. The samples can be visualised as 3 sorted
432 * columns:
433 *
434 * <pre>
435 * x y z
436 * 1 2 3
437 * a b c
438 * </pre>
439 *
440 * <p>The pivots are points 1 and 3. The other points are either known to be below or
441 * above the pivots; or potentially below or above the pivots.
442 *
443 * <p>Pivot 1: below {@code a}; potentially below {@code b, c}. This ranks
444 * pivot 1 from 2/9 to 4/9 and exactly 2/9 if the input data is sorted/reverse sorted.
445 *
446 * <p>Pivot 2: above {@code z}; potentially above {@code x,y}. This ranks
447 * pivot 2 from 6/9 to 8/9 and exactly 8/9 if the input data is sorted/reverse sorted.
448 *
449 * <p>Warning: This has the side effect that the 9 samples values are partially sorted.
450 *
451 * <p>On sorted data the tertiles are: 0.1280 0.8720
452 * <p>On random data the tertiles are:
453 * <pre>
454 * min max mean sd median skew
455 * [1] 0.0010 0.9460 0.3062 0.1560 0.2910 0.4455
456 * [2] 0.0030 0.9820 0.3875 0.1813 0.3780 0.2512
457 * [3] 0.0010 0.9400 0.3063 0.1558 0.2910 0.4453
458 * </pre>
459 * <p>Note the bias towards the central region.
460 */
461 SORT_3_OF_3 {
462 @Override
463 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
464 // Step size of 1/8 of the length
465 final int len = right - left;
466 final int step = Math.max(1, len >>> 3);
467 final int step3 = step * 3;
468 final int p2 = left + (len >>> 1);
469 final int p1 = p2 - step3;
470 final int p3 = p2 + step3;
471 // 3 medians of 3
472 Sorting.sort3(data, p1 - step, p1, p1 + step);
473 Sorting.sort3(data, p2 - step, p2, p2 + step);
474 Sorting.sort3(data, p3 - step, p3, p3 + step);
475 // Sort the medians
476 Sorting.sort3(data, p1, p2, p3);
477 pivot2[0] = p3;
478 return p1;
479 }
480
481 @Override
482 int[] getSampledIndices(int left, int right) {
483 final int len = right - left;
484 final int step = Math.max(1, len >>> 3);
485 final int step3 = step * 3;
486 final int p2 = left + (len >>> 1);
487 final int p1 = p2 - step3;
488 final int p3 = p2 + step3;
489 return new int[] {
490 p1 - step, p1, p1 + step,
491 p2 - step, p2, p2 + step,
492 p3 - step, p3, p3 + step,
493 };
494 }
495
496 @Override
497 int samplingEffect() {
498 return PARTIAL_SORT;
499 }
500 },
501 /**
502 * Pivot around the 2nd and 4th values from 5 medians approximately uniformly spaced within
503 * the range. The medians are from 5 samples. The 5 samples of 5 do not overlap thus this
504 * method requires {@code right - left >= 24}. The samples can be visualised as 5 sorted
505 * columns:
506 *
507 * <pre>
508 * v w x y z
509 * q r s t u
510 * 1 2 3 4 5
511 * f g h i j
512 * a b c d e
513 * </pre>
514 *
515 * <p>The pivots are points 2 and 4. The other points are either known to be below or
516 * above the pivots; or potentially below or above the pivots.
517 *
518 * <p>Pivot 1: below {@code 1,a,b,f,g}; potentially below {@code q,v,c,d,e,h,i,j}. This ranks
519 * pivot 1 from 6/25 to 14/25 and exactly 8/25 if the input data is sorted/reverse sorted.
520 *
521 * <p>Pivot 2 by symmetry from 12/25 to 20/25 and exactly 18/25 for sorted data.
522 *
523 * <p>Warning: This has the side effect that the 25 samples values are partially sorted.
524 *
525 * <p>On sorted data the tertiles are: 0.3050 0.6950
526 * <p>On random data the tertiles are:
527 * <pre>
528 * min max mean sd median skew
529 * [1] 0.0270 0.8620 0.3996 0.1093 0.3970 0.1130
530 * [2] 0.0030 0.8100 0.2010 0.1106 0.1860 0.6691
531 * [3] 0.0270 0.8970 0.3994 0.1093 0.3970 0.1147
532 * </pre>
533 * <p>Note the bias towards the outer regions on random data but the inner region on
534 * sorted data.
535 */
536 SORT_5_OF_5 {
537 @Override
538 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
539 // Step size of 1/25 of the length
540 final int len = right - left;
541 final int step = Math.max(1, len / 25);
542 final int step2 = step << 1;
543 final int step5 = step * 5;
544 final int p3 = left + (len >>> 1);
545 final int p2 = p3 - step5;
546 final int p1 = p2 - step5;
547 final int p4 = p3 + step5;
548 final int p5 = p4 + step5;
549 // 5 medians of 3
550 Sorting.sort5(data, p1 - step2, p1 - step, p1, p1 + step, p1 + step2);
551 Sorting.sort5(data, p2 - step2, p2 - step, p2, p2 + step, p2 + step2);
552 Sorting.sort5(data, p3 - step2, p3 - step, p3, p3 + step, p3 + step2);
553 Sorting.sort5(data, p4 - step2, p4 - step, p4, p4 + step, p4 + step2);
554 Sorting.sort5(data, p5 - step2, p5 - step, p5, p5 + step, p5 + step2);
555 // Sort the medians
556 Sorting.sort5(data, p1, p2, p3, p4, p5);
557 pivot2[0] = p4;
558 return p2;
559 }
560
561 @Override
562 int[] getSampledIndices(int left, int right) {
563 // Step size of 1/25 of the length
564 final int len = right - left;
565 final int step = Math.max(1, len / 25);
566 final int step2 = step << 1;
567 final int step5 = step * 5;
568 final int p3 = left + (len >>> 1);
569 final int p2 = p3 - step5;
570 final int p1 = p2 - step5;
571 final int p4 = p3 + step5;
572 final int p5 = p4 + step5;
573 return new int[] {
574 p1 - step2, p1 - step, p1, p1 + step, p1 + step2,
575 p2 - step2, p2 - step, p2, p2 + step, p2 + step2,
576 p3 - step2, p3 - step, p3, p3 + step, p3 + step2,
577 p4 - step2, p4 - step, p4, p4 + step, p4 + step2,
578 p5 - step2, p5 - step, p5, p5 + step, p5 + step2,
579 };
580 }
581
582 @Override
583 int samplingEffect() {
584 return PARTIAL_SORT;
585 }
586 },
587 /**
588 * Pivot around the 3rd and 5th values from 7 approximately uniformly spaced within the range.
589 * Uses points +/- eights from the median: 1/8, 1/4, 3/8, 1/2, 5/8, 3/4, 7/8.
590 *
591 * <p>Requires {@code right - left >= 6}.
592 *
593 * <p>Warning: This has the side effect that the 7 values are also sorted.
594 *
595 * <p>On sorted data the tertiles are: 0.3760 0.6240
596 * <p>On random data the tertiles are:
597 * <pre>
598 * min max mean sd median skew
599 * [1] 0.0020 0.9600 0.3745 0.1609 0.3640 0.3092
600 * [2] 0.0030 0.9490 0.2512 0.1440 0.2300 0.6920
601 * [3] 0.0030 0.9620 0.3743 0.1609 0.3640 0.3100
602 * </pre>
603 * <p>Note the bias towards the outer regions.
604 */
605 SORT_7 {
606 @Override
607 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
608 // Ensure the value is above zero to choose different points!
609 // This is safe if len >= 4.
610 final int len = right - left;
611 final int eighth = Math.max(1, len >>> 3);
612 final int p4 = left + (len >>> 1);
613 final int p3 = p4 - eighth;
614 final int p2 = p3 - eighth;
615 final int p1 = p2 - eighth;
616 final int p5 = p4 + eighth;
617 final int p6 = p5 + eighth;
618 final int p7 = p6 + eighth;
619 Sorting.sort7(data, p1, p2, p3, p4, p5, p6, p7);
620 pivot2[0] = p5;
621 return p3;
622 }
623
624 @Override
625 int[] getSampledIndices(int left, int right) {
626 final int len = right - left;
627 final int eighth = Math.max(1, len >>> 3);
628 final int p4 = left + (len >>> 1);
629 final int p3 = p4 - eighth;
630 final int p2 = p3 - eighth;
631 final int p1 = p2 - eighth;
632 final int p5 = p4 + eighth;
633 final int p6 = p5 + eighth;
634 final int p7 = p6 + eighth;
635 return new int[] {p1, p2, p3, p4, p5, p6, p7};
636 }
637
638 @Override
639 int samplingEffect() {
640 return SORT;
641 }
642 },
643 /**
644 * Pivot around the 3rd and 6th values from 8 approximately uniformly spaced within the range.
645 * Uses points +/- ninths from the median: m - 4/9, m - 3/9, m - 2/9, m - 1/9; m + 1 + 1/9,
646 * m + 1 + 2/9, m + 1 + 3/9, m + 1 + 4/9.
647 *
648 * <p>Requires {@code right - left >= 7}.
649 *
650 * <p>Warning: This has the side effect that the 8 values are also sorted.
651 *
652 * <p>On sorted data the tertiles are: 0.3380 0.6630
653 * <p>On random data the tertiles are:
654 * <pre>
655 * min max mean sd median skew
656 * [1] 0.0030 0.9480 0.3327 0.1485 0.3200 0.4044
657 * [2] 0.0050 0.9350 0.3345 0.1485 0.3220 0.4056
658 * [3] 0.0020 0.9320 0.3328 0.1485 0.3200 0.4063
659 * </pre>
660 */
661 SORT_8 {
662 @Override
663 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
664 // 1/9 = 4/36 = 8/72 ~ 7/64 ~ 1/16 + 1/32 + 1/64 : 0.11111 ~ 0.1094
665 // Ensure the value is above zero to choose different points!
666 // This is safe if len >= 7.
667 final int len = right - left;
668 final int ninth = Math.max(1, (len >>> 4) + (len >>> 5) + (len >>> 6));
669 // Work from middle outward. This is deliberate to ensure data.length==7
670 // throws an index out-of-bound exception.
671 final int m = left + (len >>> 1);
672 final int p4 = m - (ninth >> 1);
673 final int p3 = p4 - ninth;
674 final int p2 = p3 - ninth;
675 final int p1 = p2 - ninth;
676 final int p5 = m + (ninth >> 1) + 1;
677 final int p6 = p5 + ninth;
678 final int p7 = p6 + ninth;
679 final int p8 = p7 + ninth;
680 Sorting.sort8(data, p1, p2, p3, p4, p5, p6, p7, p8);
681 pivot2[0] = p6;
682 return p3;
683 }
684
685 @Override
686 int[] getSampledIndices(int left, int right) {
687 final int len = right - left;
688 final int ninth = Math.max(1, (len >>> 4) + (len >>> 5) + (len >>> 6));
689 final int m = left + (len >>> 1);
690 final int p4 = m - (ninth >> 1);
691 final int p3 = p4 - ninth;
692 final int p2 = p3 - ninth;
693 final int p1 = p2 - ninth;
694 final int p5 = m + (ninth >> 1) + 1;
695 final int p6 = p5 + ninth;
696 final int p7 = p6 + ninth;
697 final int p8 = p7 + ninth;
698 return new int[] {p1, p2, p3, p4, p5, p6, p7, p8};
699 }
700
701 @Override
702 int samplingEffect() {
703 return SORT;
704 }
705 },
706 /**
707 * Pivot around the 4th and 8th values from 11 approximately uniformly spaced within the range.
708 * Uses points +/- twelfths from the median: ..., m - 1/12, m, m + 1/12, ... .
709 *
710 * <p>Requires {@code right - left >= 10}.
711 *
712 * <p>Warning: This has the side effect that the 11 values are also sorted.
713 *
714 * <p>On sorted data the tertiles are: 0.3460 0.6540
715 * <p>On random data the tertiles are:
716 * <pre>
717 * min max mean sd median skew
718 * [1] 0.0060 0.9000 0.3328 0.1301 0.3230 0.3624
719 * [2] 0.0100 0.9190 0.3345 0.1299 0.3250 0.3643
720 * [3] 0.0060 0.8970 0.3327 0.1302 0.3230 0.3653
721 * </pre>
722 */
723 SORT_11 {
724 @Override
725 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
726 // 1/12 = 8/96 ~ 1/16 + 1/32 ~ 9/96 : 0.8333 ~ 0.09375
727 // Ensure the value is above zero to choose different points!
728 // This is safe if len >= 10.
729 final int len = right - left;
730 final int twelfth = Math.max(1, (len >>> 4) + (len >>> 6));
731 final int p6 = left + (len >>> 1);
732 final int p5 = p6 - twelfth;
733 final int p4 = p5 - twelfth;
734 final int p3 = p4 - twelfth;
735 final int p2 = p3 - twelfth;
736 final int p1 = p2 - twelfth;
737 final int p7 = p6 + twelfth;
738 final int p8 = p7 + twelfth;
739 final int p9 = p8 + twelfth;
740 final int p10 = p9 + twelfth;
741 final int p11 = p10 + twelfth;
742 Sorting.sort11(data, p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11);
743 pivot2[0] = p8;
744 return p4;
745 }
746
747 @Override
748 int[] getSampledIndices(int left, int right) {
749 final int len = right - left;
750 final int twelfth = Math.max(1, (len >>> 4) + (len >>> 6));
751 final int p6 = left + (len >>> 1);
752 final int p5 = p6 - twelfth;
753 final int p4 = p5 - twelfth;
754 final int p3 = p4 - twelfth;
755 final int p2 = p3 - twelfth;
756 final int p1 = p2 - twelfth;
757 final int p7 = p6 + twelfth;
758 final int p8 = p7 + twelfth;
759 final int p9 = p8 + twelfth;
760 final int p10 = p9 + twelfth;
761 final int p11 = p10 + twelfth;
762 return new int[] {p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11};
763 }
764
765 @Override
766 int samplingEffect() {
767 return SORT;
768 }
769 };
770
771 /** Sampled points are unchanged. */
772 static final int UNCHANGED = 0;
773 /** Sampled points are partially sorted. */
774 static final int PARTIAL_SORT = 0x1;
775 /** Sampled points are sorted. */
776 static final int SORT = 0x2;
777
778 /**
779 * Find two pivot indices of the array so that partitioning into 3-regions can be made.
780 *
781 * <pre>{@code
782 * left <= p1 <= p2 <= right
783 * }</pre>
784 *
785 * <p>Returns two pivots so that {@code data[p1] <= data[p2]}.
786 *
787 * @param data Array.
788 * @param left Lower bound (inclusive).
789 * @param right Upper bound (inclusive).
790 * @param pivot2 Second pivot.
791 * @return first pivot
792 */
793 abstract int pivotIndex(double[] data, int left, int right, int[] pivot2);
794
795 // The following methods allow the strategy and side effects to be tested
796
797 /**
798 * Get the indices of points that will be sampled.
799 *
800 * @param left Lower bound (inclusive).
801 * @param right Upper bound (inclusive).
802 * @return the indices
803 */
804 abstract int[] getSampledIndices(int left, int right);
805
806 /**
807 * Get the effect on the sampled points.
808 * <ul>
809 * <li>0 - Unchanged
810 * <li>1 - Partially sorted
811 * <li>2 - Sorted
812 * </ul>
813 *
814 * @return the effect
815 */
816 abstract int samplingEffect();
817 }