ウィキペディアの記事を使用して、algs4 quickselectに基づいて中央値選択アルゴリズムの中央値を実装しましたが、私のコードはうまく機能しません。
1) 中央値の中央値は、k 番目に大きい要素を見つけると言われています。ただし、私のコードは k 番目に小さい要素を見つけます。
2) 私の実装は、quickselect よりも 1 倍から 20 倍遅く実行されますが、中央値アルゴリズムの中央値は漸近的に高速になるはずです。
何度も確認しましたが、問題が見つかりません。
public class MedianOfMedians {
public static Comparable medianOfMedians(Comparable[] nums, int k) {
return nums[select(nums, 0, nums.length - 1, k)];
}
private static int select(Comparable[] nums, int lo, int hi, int k) {
while (lo < hi) {
int pivotIndex = pivot(nums, lo, hi);
int j = partition(nums, lo, hi, pivotIndex);
if (j < k) {
lo = j + 1;
} else if (j > k) {
hi = j - 1;
} else {
return j;
}
}
return lo;
}
private static int pivot(Comparable[] list, int left, int right) {
// for 5 or less elements just get median
if (right - left < 5) {
return partition5(list, left, right);
}
// otherwise move the medians of five-element subgroups to the first n/5 positions
for (int i = left; i <= right; i += 5) {
// get the median of the i'th five-element subgroup
int subRight = i + 4;
if (subRight > right) {
subRight = right;
}
int median5 = partition5(list, i, subRight);
exch(list, median5, (int) (left + Math.floor((i - left) / 5d)));
}
// compute the median of the n/5 medians-of-five
return select(list,
left,
(int) (left + Math.ceil((right - left) / 5d) - 1),
(int) (left + (right - left) / 10d));
}
private static int partition5(Comparable[] list, int lo, int hi) {
for (int i = lo; i <= hi; i++) {
for (int j = i; j > lo; j--) {
if (less(list[j - 1], list[j])) {
exch(list, j, j - 1);
}
}
}
return (hi + lo) / 2;
}
private static int partition(Comparable[] a, int lo, int hi, int pivotIndex) {
exch(a, lo, pivotIndex);
int i = lo;
int j = hi + 1;
Comparable v = a[lo];
while (true) {
while (less(a[++i], v) && i != hi) { }
while (less(v, a[--j]) && j != lo) { }
if (j <= i) break;
exch(a, i, j);
}
exch(a, j, lo);
return j;
}
private static void exch(Comparable[] nums, int i, int j) { }
private static boolean less(Comparable v, Comparable w) { }
}
JUnit テスト:
public class MedianOfMediansTest {
private final static int TESTS_COUNT = 100;
@org.junit.Test
public void test() {
// generate TESTS_COUNT arrays of 10000 entries from 0..Integer.MAX_VALUE
Integer[][] tests = generateTestComparables(TESTS_COUNT, 10000, 10000, 0, Integer.MAX_VALUE);
for (int i = 0; i < tests.length; i++) {
Integer[] array1 = Arrays.copyOf(tests[i], tests[i].length);
Integer[] array2 = Arrays.copyOf(tests[i], tests[i].length);
Integer[] array3 = Arrays.copyOf(tests[i], tests[i].length);
long time = System.nanoTime();
final int a = (Integer) MedianOfMedians.medianOfMedians(array1, 0);
long nanos_a = System.nanoTime() - time;
time = System.nanoTime();
final int b = (Integer) Quick.select(array2, 0);
long nanos_b = System.nanoTime() - time;
time = System.nanoTime();
Arrays.sort(array3);
final int c = array3[0];
long nanos_c = System.nanoTime() - time;
System.out.println("MedianOfMedians: " + a + " (" + nanos_a + ") " +
"QuickSelect: " + b + " (" + nanos_b + ") " +
"Arrays.sort: " + c + " (" + nanos_c + ")");
System.out.println(((double) nanos_a) / ((double) nanos_b));
Assert.assertEquals(c, a);
Assert.assertEquals(b, a);
}
}
public static Integer[][] generateTestComparables(int numberOfTests,
int arraySizeMin, int arraySizeMax,
int valueMin, int valueMax) {
Random rand = new Random(System.currentTimeMillis());
Integer[][] ans = new Integer[numberOfTests][];
for (int i = 0; i < ans.length; i++) {
ans[i] = new Integer[randInt(rand, arraySizeMin, arraySizeMax)];
for (int j = 0; j < ans[i].length; j++) {
ans[i][j] = randInt(rand, valueMin, valueMax);
}
}
return ans;
}
public static int randInt(Random rand, int min, int max) {
return (int) (min + (rand.nextDouble() * ((long) max - (long) min)));
}
}