1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 package org.apache.commons.numbers.examples.jmh.arrays;
19
20
21
22
23
24
25
26
27
28
29 enum DualPivotingStrategy {
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 MEDIANS {
45 @Override
46 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
47
48 final int len = right - left;
49
50
51 final int third = Math.max(1, len / 3);
52 final int m1 = left + third;
53 final int m2 = right - third;
54
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94 SORT_5 {
95 @Override
96 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
97
98
99
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146 SORT_5B {
147 @Override
148 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
149
150
151
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
183
184
185
186
187
188
189
190
191
192
193
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
201
202
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
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235 SORT_5C {
236 @Override
237 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
238
239
240
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
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303 SORT_5_OF_3 {
304 @Override
305 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
306
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
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
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
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384 SORT_4_OF_3 {
385 @Override
386 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
387
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
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
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
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461 SORT_3_OF_3 {
462 @Override
463 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
464
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
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
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
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536 SORT_5_OF_5 {
537 @Override
538 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
539
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
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
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
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
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605 SORT_7 {
606 @Override
607 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
608
609
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
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661 SORT_8 {
662 @Override
663 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
664
665
666
667 final int len = right - left;
668 final int ninth = Math.max(1, (len >>> 4) + (len >>> 5) + (len >>> 6));
669
670
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
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723 SORT_11 {
724 @Override
725 int pivotIndex(double[] data, int left, int right, int[] pivot2) {
726
727
728
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
772 static final int UNCHANGED = 0;
773
774 static final int PARTIAL_SORT = 0x1;
775
776 static final int SORT = 0x2;
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793 abstract int pivotIndex(double[] data, int left, int right, int[] pivot2);
794
795
796
797
798
799
800
801
802
803
804 abstract int[] getSampledIndices(int left, int right);
805
806
807
808
809
810
811
812
813
814
815
816 abstract int samplingEffect();
817 }