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 a pivoting index of an array for partitioning.
22 *
23 * <p>An ideal strategy will pick [1/2, 1/2] across a variety of data.
24 *
25 * @since 1.2
26 */
27 enum PivotingStrategy {
28 /**
29 * Pivot around the centre of the range.
30 */
31 CENTRAL {
32 @Override
33 int pivotIndex(double[] data, int left, int right, int ignored) {
34 return med(left, right);
35 }
36
37 @Override
38 int[] getSampledIndices(int left, int right, int ignored) {
39 return new int[] {med(left, right)};
40 }
41
42 @Override
43 int samplingEffect() {
44 return UNCHANGED;
45 }
46 },
47 /**
48 * Pivot around the median of 3 values within the range: the first; the centre; and the last.
49 */
50 MEDIAN_OF_3 {
51 @Override
52 int pivotIndex(double[] data, int left, int right, int ignored) {
53 return med3(data, left, med(left, right), right);
54 }
55
56 @Override
57 int[] getSampledIndices(int left, int right, int ignored) {
58 return new int[] {left, med(left, right), right};
59 }
60
61 @Override
62 int samplingEffect() {
63 return UNCHANGED;
64 }
65 },
66 /**
67 * Pivot around the median of 9 values within the range.
68 * Uses the median of 3 medians of 3. The returned value
69 * is ranked 4, 5, or 6 out of the 9 values.
70 * This is also known in the literature as Tukey’s "ninther" pivot.
71 */
72 MEDIAN_OF_9 {
73 @Override
74 int pivotIndex(double[] data, int left, int right, int ignored) {
75 final int s = (right - left) >>> 3;
76 final int m = med(left, right);
77 final int x = med3(data, left, left + s, left + (s << 1));
78 final double a = data[x];
79 final int y = med3(data, m - s, m, m + s);
80 final double b = data[y];
81 final int z = med3(data, right - (s << 1), right - s, right);
82 return med3(a, b, data[z], x, y, z);
83 }
84
85 @Override
86 int[] getSampledIndices(int left, int right, int ignored) {
87 final int s = (right - left) >>> 3;
88 final int m = med(left, right);
89 return new int[] {
90 left, left + s, left + (s << 1),
91 m - s, m, m + s,
92 right - (s << 1), right - s, right
93 };
94 }
95
96 @Override
97 int samplingEffect() {
98 return UNCHANGED;
99 }
100 },
101 /**
102 * Pivot around the median of 3 or 9 values within the range.
103 *
104 * <p>Note: Bentley & McIlroy (1993) choose a size of 40 to pivot around 9 values;
105 * and a lower size of 7 to use the central; otherwise the median of 3.
106 * This method does not switch to the central method for small sizes.
107 */
108 DYNAMIC {
109 @Override
110 int pivotIndex(double[] data, int left, int right, int ignored) {
111 if (right - left >= MED_9) {
112 return MEDIAN_OF_9.pivotIndex(data, left, right, ignored);
113 }
114 return MEDIAN_OF_3.pivotIndex(data, left, right, ignored);
115 }
116
117 @Override
118 int[] getSampledIndices(int left, int right, int ignored) {
119 if (right - left >= MED_9) {
120 return MEDIAN_OF_9.getSampledIndices(left, right, ignored);
121 }
122 return MEDIAN_OF_3.getSampledIndices(left, right, ignored);
123 }
124
125 @Override
126 int samplingEffect() {
127 return UNCHANGED;
128 }
129 },
130 /**
131 * Pivot around the median of 5 values within the range.
132 * Requires that {@code right - left >= 4}.
133 *
134 * <p>Warning: This has the side effect that the 5 values are also partially sorted.
135 *
136 * <p>Uses the same spacing as {@link DualPivotingStrategy#SORT_5}.
137 */
138 MEDIAN_OF_5 {
139 @Override
140 int pivotIndex(double[] data, int left, int right, int ignored) {
141 // 1/6 = 5/30 ~ 1/8 + 1/32 + 1/64 : 0.1666 ~ 0.1719
142 // Ensure the value is above zero to choose different points!
143 // This is safe if len >= 4.
144 final int len = right - left;
145 final int sixth = 1 + (len >>> 3) + (len >>> 5) + (len >>> 6);
146 // Note: No use of median(left, right). This is not targeted by median of 3 killer
147 // input as it does not use the end points left and right.
148 final int p3 = left + (len >>> 1);
149 final int p2 = p3 - sixth;
150 final int p1 = p2 - sixth;
151 final int p4 = p3 + sixth;
152 final int p5 = p4 + sixth;
153 return Sorting.median5(data, p1, p2, p3, p4, p5);
154 }
155
156 @Override
157 int[] getSampledIndices(int left, int right, int ignored) {
158 final int len = right - left;
159 final int sixth = 1 + (len >>> 3) + (len >>> 5) + (len >>> 6);
160 final int p3 = left + (len >>> 1);
161 final int p2 = p3 - sixth;
162 final int p1 = p2 - sixth;
163 final int p4 = p3 + sixth;
164 final int p5 = p4 + sixth;
165 return new int[] {p1, p2, p3, p4, p5};
166 }
167
168 @Override
169 int samplingEffect() {
170 return PARTIAL_SORT;
171 }
172 },
173 /**
174 * Pivot around the median of 5 values within the range.
175 * Requires that {@code right - left >= 4}.
176 *
177 * <p>Warning: This has the side effect that the 5 values are also partially sorted.
178 *
179 * <p>Uses the same spacing as {@link DualPivotingStrategy#SORT_5B}.
180 */
181 MEDIAN_OF_5B {
182 @Override
183 int pivotIndex(double[] data, int left, int right, int ignored) {
184 // 1/7 = 5/35 ~ 1/8 + 1/64 : 0.1429 ~ 0.1406
185 // Ensure the value is above zero to choose different points!
186 // This is safe if len >= 4.
187 final int len = right - left;
188 final int seventh = 1 + (len >>> 3) + (len >>> 6);
189 final int p3 = left + (len >>> 1);
190 final int p2 = p3 - seventh;
191 final int p1 = p2 - seventh;
192 final int p4 = p3 + seventh;
193 final int p5 = p4 + seventh;
194 Sorting.sort4(data, p1, p2, p4, p5);
195 // p2 and p4 are sorted: check if p3 is between them
196 if (data[p3] < data[p2]) {
197 return p2;
198 }
199 return data[p3] > data[p4] ? p4 : p3;
200 }
201
202 @Override
203 int[] getSampledIndices(int left, int right, int ignored) {
204 final int len = right - left;
205 final int seventh = 1 + (len >>> 3) + (len >>> 6);
206 final int p3 = left + (len >>> 1);
207 final int p2 = p3 - seventh;
208 final int p1 = p2 - seventh;
209 final int p4 = p3 + seventh;
210 final int p5 = p4 + seventh;
211 return new int[] {p1, p2, p3, p4, p5};
212 }
213
214 @Override
215 int samplingEffect() {
216 return PARTIAL_SORT;
217 }
218 },
219 /**
220 * Pivot around the target index.
221 */
222 TARGET {
223 @Override
224 int pivotIndex(double[] data, int left, int right, int k) {
225 return k;
226 }
227
228 @Override
229 int[] getSampledIndices(int left, int right, int k) {
230 return new int[] {k};
231 }
232
233 @Override
234 int samplingEffect() {
235 return UNCHANGED;
236 }
237 };
238
239 /** Sampled points are unchanged. */
240 static final int UNCHANGED = 0;
241 /** Sampled points are partially sorted. */
242 static final int PARTIAL_SORT = 0x1;
243 /** Sampled points are sorted. */
244 static final int SORT = 0x2;
245 /** Size to pivot around the median of 9. */
246 private static final int MED_9 = 40;
247
248 /**
249 * Compute the median index.
250 *
251 * <p>Note: This intentionally uses the median as {@code left + (right - left + 1) / 2}.
252 * If the median is {@code left + (right - left) / 2} then the median is 1 position lower
253 * for even length due to using an inclusive right bound. This median is not as affected
254 * by median-of-3 killer sequences. For benchmarking it is useful to maintain the classic
255 * median-of-3 behaviour to be able to trigger worst case performance on input
256 * used in the literature.
257 *
258 * @param left Lower bound (inclusive).
259 * @param right Upper bound (inclusive).
260 * @return the median index
261 */
262 private static int med(int left, int right) {
263 return (left + right + 1) >>> 1;
264 }
265
266 /**
267 * Find the median index of 3.
268 *
269 * @param data Values.
270 * @param i Index.
271 * @param j Index.
272 * @param k Index.
273 * @return the median index
274 */
275 private static int med3(double[] data, int i, int j, int k) {
276 return med3(data[i], data[j], data[k], i, j, k);
277 }
278
279 /**
280 * Find the median index of 3 values.
281 *
282 * @param a Value.
283 * @param b Value.
284 * @param c Value.
285 * @param ia Index of a.
286 * @param ib Index of b.
287 * @param ic Index of c.
288 * @return the median index
289 */
290 private static int med3(double a, double b, double c, int ia, int ib, int ic) {
291 if (a < b) {
292 if (b < c) {
293 return ib;
294 }
295 return a < c ? ic : ia;
296 }
297 if (b > c) {
298 return ib;
299 }
300 return a > c ? ic : ia;
301 }
302
303 /**
304 * Find a pivot index of the array so that partitioning into 2-regions can be made.
305 *
306 * <pre>{@code
307 * left <= p <= right
308 * }</pre>
309 *
310 * <p>The argument {@code k} is the target index in {@code [left, right]}. Strategies
311 * may use this to help select the pivot index. If not available (e.g. selecting a pivot
312 * for quicksort) then choose a value in {@code [left, right]} to be safe.
313 *
314 * @param data Array.
315 * @param left Lower bound (inclusive).
316 * @param right Upper bound (inclusive).
317 * @param k Target index.
318 * @return pivot
319 */
320 abstract int pivotIndex(double[] data, int left, int right, int k);
321
322 // The following methods allow the strategy and side effects to be tested
323
324 /**
325 * Get the indices of points that will be sampled.
326 *
327 * @param left Lower bound (inclusive).
328 * @param right Upper bound (inclusive).
329 * @param k Target index.
330 * @return the indices
331 */
332 abstract int[] getSampledIndices(int left, int right, int k);
333
334 /**
335 * Get the effect on the sampled points.
336 * <ul>
337 * <li>0 - Unchanged
338 * <li>1 - Partially sorted
339 * <li>2 - Sorted
340 * </ul>
341 *
342 * @return the effect
343 */
344 abstract int samplingEffect();
345 }