中位數的中位數java實現

Question

我實現了平均中位數選擇算法基於使用Wikipedia articlealgs4 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))); 
    } 
} 

Answer 1

1）這是說，中位數的中值認定第k最大的元素。 但是，我的代碼找到第k個最小的元素。

這並非嚴格對稱。任何選擇算法都可以找到最小或最大的元素，因爲這基本上是相同的任務。這取決於你如何比較元素以及如何分割它們（並且你可以隨後做類似length - 1 - result的事情）。你的代碼似乎確實找到了最小的元素，這是實現選擇算法的最典型和直觀的方式。

2）我的實現運行速度比quickselect慢1-20倍，但中位數算法的中位數應該漸近地快一些。

不只是漸近地快。在最壞的情況下，漸近地更快。在平均情況下，兩者都是線性的，但是MoM具有較高的常數因子。由於您隨機生成測試，因此您不太可能遇到最糟糕的情況。如果您使用隨機快速選擇，那麼對於任何輸入，它不可能遇到最壞的情況，否則概率將取決於所使用的數據透視選擇算法。

考慮到這一點，以及中位數的中位數具有高常數因素的事實，您不應該指望它比快速選擇表現更好！儘管如此，它可能會優於排序，但即使如此 - 那些排序中的對數因子對於小輸入而言並不大（lg 10000約爲13-14）。例如，

以my MoM solution for a LeetCode problem。 Arrays.sort有時比具有500萬個元素的陣列具有更好的性能。儘管如此，最好的情況下它的運行速度要快兩倍。

因此，MoM主要是理論上的興趣。當你需要100％保證不超過一定的時間限制時，我可以想象一個實際的用例。比方說，飛機，航天器或核反應堆上的一些實時系統。時間限制不是很緊張，但超過一納秒就是災難性的。但這是一個非常人爲的例子，我懷疑它實際上是它的工作方式。

即使您可以找到MoM的實際用例，也可以使用類似Introselect的替代方法。它基本上以快速選擇開始，如果事情看起來不太好，則切換到MoM。但是測試它將會是一場噩夢 - 你將如何提出一個實際上迫使算法切換（並因此測試MoM部分）的測試，特別是如果它是隨機的？

你的代碼總體上看起來不錯，但我會做一些輔助方法package-private甚至將它們移動到另一個類來單獨測試，因爲這樣的事情很難正確地進行測試。如果結果是正確的，你可能不會注意到效果。例如，我不確定您的五位組代碼是否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的事情的一部分，但我不知道它是錯的）。