中位数的中位数 java 实施
Median of medians java implementation
我实现了基于algs4 quickselect using the Wikipedia article的中位数选择算法的中位数，但我的代码运行不正常：
1）据说中位数的中位数找到第k个最大元素。但是，我的代码找到第 k 个 smallest 元素。
2) 我的实现比 quickselect 慢 1-20 倍，但是 medians of medians 算法应该渐近更快。
我检查了很多次，但我找不到问题所在。
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)));
}
}
1) it is said that median of medians finds kth largest element.
However, my code finds kth smallest element.
这不是严格意义上的。任何选择算法都可以找到最小或最大的元素，因为这本质上是相同的任务。这取决于你如何比较元素以及如何对它们进行分区（你以后总是可以做类似 length - 1 - result 的事情）。您的代码似乎确实找到了第 k 个最小元素，顺便说一句，这是实现选择算法的最典型和最直观的方法。
2) my implementation runs 1-20 times slower than quickselect, but the
median of medians algorithm should be asymptotically faster.
不仅仅是渐近速度更快。在最坏的情况下 渐近更快 。在平均情况下，两者都是线性的，但 MoM 具有更高的常数因子。由于您随机生成测试，因此您不太可能遇到最坏的情况。如果您使用随机快速选择，那么对于 any 输入，它不太可能命中最坏的情况，否则概率将取决于所使用的基准选择算法。
考虑到这一点，并且中位数的中位数具有很高的常数因子，您不应该期望它比 quickselect 表现更好！虽然它可能优于排序，但即便如此——排序中的那些对数因子对于小输入来说并不大（lg 10000 大约是 13-14）。
以my MoM solution for a LeetCode problem为例。对于具有 5 亿个元素 的数组，Arrays.sort 有时优于 MoM。不过，在最好的情况下，它的运行速度大约快两倍。
因此，MoM 主要具有理论意义。当您需要 100% 保证不超过某个时间限制时，我可以想象一个实际用例。比如说，飞机、航天器或核反应堆上的一些实时系统。时间限制不是很紧，但即使超过一纳秒也是灾难性的。但这是一个极其人为的例子，我怀疑它实际上是这样工作的。
即使您可以找到 MoM 的实际用例，您也可以改用 Introselect 之类的东西。它基本上从 quickselect 开始，然后如果事情看起来不太好则切换到 MoM。但是测试它会是一场噩梦——你怎么想出一个真正强制算法切换的测试（并因此测试 MoM 部分），特别是如果它是随机的？
您的代码总体上看起来不错，但我会将一些辅助方法封装为私有的，甚至将它们移至另一个 class 以单独测试，因为这样的事情很难正确处理。如果结果正确，您可能不会注意到效果。例如，我不确定您的五人一组代码是否 100% 正确。有时你在我希望看到元素计数的地方使用 right - left，应该是 right - left + 1.
此外，我会用纯整数算术等价物替换那些 ceil/floor 调用。也就是说，Math.floor((i - left) / 5d)) => (i - left) / 5、Math.ceil((right - left) / 5d) => (right - left + 4) / 5（顺便说一下，这是我不喜欢 right - left 的部分, 但我不确定是不是错了）。
我实现了基于algs4 quickselect using the Wikipedia article的中位数选择算法的中位数，但我的代码运行不正常：
1）据说中位数的中位数找到第k个最大元素。但是，我的代码找到第 k 个 smallest 元素。
2) 我的实现比 quickselect 慢 1-20 倍，但是 medians of medians 算法应该渐近更快。
我检查了很多次，但我找不到问题所在。
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)));
}
}
1) it is said that median of medians finds kth largest element. However, my code finds kth smallest element.
这不是严格意义上的。任何选择算法都可以找到最小或最大的元素，因为这本质上是相同的任务。这取决于你如何比较元素以及如何对它们进行分区（你以后总是可以做类似 length - 1 - result 的事情）。您的代码似乎确实找到了第 k 个最小元素，顺便说一句，这是实现选择算法的最典型和最直观的方法。
2) my implementation runs 1-20 times slower than quickselect, but the median of medians algorithm should be asymptotically faster.
不仅仅是渐近速度更快。在最坏的情况下 渐近更快 。在平均情况下，两者都是线性的，但 MoM 具有更高的常数因子。由于您随机生成测试，因此您不太可能遇到最坏的情况。如果您使用随机快速选择，那么对于 any 输入，它不太可能命中最坏的情况，否则概率将取决于所使用的基准选择算法。
考虑到这一点，并且中位数的中位数具有很高的常数因子，您不应该期望它比 quickselect 表现更好！虽然它可能优于排序，但即便如此——排序中的那些对数因子对于小输入来说并不大（lg 10000 大约是 13-14）。
以my MoM solution for a LeetCode problem为例。对于具有 5 亿个元素 的数组，Arrays.sort 有时优于 MoM。不过，在最好的情况下，它的运行速度大约快两倍。
因此，MoM 主要具有理论意义。当您需要 100% 保证不超过某个时间限制时，我可以想象一个实际用例。比如说，飞机、航天器或核反应堆上的一些实时系统。时间限制不是很紧，但即使超过一纳秒也是灾难性的。但这是一个极其人为的例子，我怀疑它实际上是这样工作的。
即使您可以找到 MoM 的实际用例，您也可以改用 Introselect 之类的东西。它基本上从 quickselect 开始，然后如果事情看起来不太好则切换到 MoM。但是测试它会是一场噩梦——你怎么想出一个真正强制算法切换的测试（并因此测试 MoM 部分），特别是如果它是随机的？
您的代码总体上看起来不错，但我会将一些辅助方法封装为私有的，甚至将它们移至另一个 class 以单独测试，因为这样的事情很难正确处理。如果结果正确，您可能不会注意到效果。例如，我不确定您的五人一组代码是否 100% 正确。有时你在我希望看到元素计数的地方使用 right - left，应该是 right - left + 1.
此外，我会用纯整数算术等价物替换那些 ceil/floor 调用。也就是说，Math.floor((i - left) / 5d)) => (i - left) / 5、Math.ceil((right - left) / 5d) => (right - left + 4) / 5（顺便说一下，这是我不喜欢 right - left 的部分, 但我不确定是不是错了）。