Sorting arraylist with mergesort vs custom sort

Question

我正在寫一個程序，它必須能夠排序高達10億個隨機Squares。我在下面寫了一個小例子程序，它創建了一個Squares的隨機ArrayList，然後用兩種不同的方法對它進行排序。

當我正在尋找一種有效的排序方法時，我發現使用Merge Sort本意是最有效/最快的。但是，當將合併排序與自定義排序（不知道這種排序是否有名稱）進行比較時，我發現我寫的排序效率更高。

我從我的程序得到的輸出是

時間納秒比較排序：2346757466

時間納秒歸併排序：24156585699

標準排序是更快

那麼爲什麼我寫的比排序更快？
是否可以改進任何一種使用過的排序以實現更快，更高效的排序？

import java.security.SecureRandom; 
import java.util.ArrayList; 
import java.util.Comparator; 
import java.util.Objects; 

public class SortSquares { 
    public void run() { 
     ArrayList<Square> list = new ArrayList<Square>(); 
     SecureRandom rand = new SecureRandom(); 
     int randSize = 10; 
     for(int i = 1; i <= 10000000; i++) 
      list.add(new Square(i + rand.nextInt(randSize), i + rand.nextInt(randSize))); 

     //Create shallow copies to allow for timing 
     ArrayList<Square> comp = new ArrayList<Square>(list); 
     ArrayList<Square> merge = new ArrayList<Square>(list); 

     long startTime = System.nanoTime(); 
     comp.sort(new SquareSort()); 
     long endTime = System.nanoTime(); 
     long duration = (endTime - startTime); 
     System.out.println("Time in nanoseconds for comparator sort: " + duration); 

     long startTime1 = System.nanoTime(); 
     merge = mergeSort(merge); 
     long endTime1 = System.nanoTime(); 
     long duration1 = (endTime1 - startTime1); 
     System.out.println("Time in nanoseconds for merge sort: " + duration1); 

     if(duration < duration1) 
      System.out.println("Standard Sort is faster"); 
     else if(duration == duration1) 
      System.out.println("The sorts are the same"); 
     else 
      System.out.println("Merge Sort is faster"); 
    } 

    private class SquareSort implements Comparator<Square> { 
     @Override 
     public int compare(Square s1, Square s2) { 
      if(s1.getLocation()[0] > s2.getLocation()[0]) { 
       return 1; 
      } else if(s1.getLocation()[0] == s2.getLocation()[0]) { 
       if(s1.getLocation()[1] > s2.getLocation()[1]) { 
        return 1; 
       } else if(s1.getLocation()[1] == s2.getLocation()[1]) { 
        return 0; 
       } else { 
        return -1; 
       } 
      } else { 
       return -1; 
      } 
     } 
    } 

    public ArrayList<Square> mergeSort(ArrayList<Square> whole) { 
     ArrayList<Square> left = new ArrayList<Square>(); 
     ArrayList<Square> right = new ArrayList<Square>(); 
     int center; 

     if (whole.size() <= 1) {  
      return whole; 
     } else { 
      center = whole.size()/2; 

      for (int i = 0; i < center; i++) { 
       left.add(whole.get(i)); 
      } 

      for (int i = center; i < whole.size(); i++) { 
       right.add(whole.get(i)); 
      } 

      left = mergeSort(left); 
      right = mergeSort(right); 

      merge(left, right, whole); 
     } 
     return whole; 
    } 

    private void merge(ArrayList<Square> left, ArrayList<Square> right, ArrayList<Square> whole) { 
     int leftIndex = 0; 
     int rightIndex = 0; 
     int wholeIndex = 0; 

     while (leftIndex < left.size() && rightIndex < right.size()) { 
      if ((left.get(leftIndex).compareTo(right.get(rightIndex))) < 0) { 
       whole.set(wholeIndex, left.get(leftIndex)); 
       leftIndex++; 
      } else { 
       whole.set(wholeIndex, right.get(rightIndex)); 
       rightIndex++; 
      } 
      wholeIndex++; 
     } 

     ArrayList<Square> rest; 
     int restIndex; 
     if (leftIndex >= left.size()) { 
      rest = right; 
      restIndex = rightIndex; 
     } else { 
      rest = left; 
      restIndex = leftIndex; 
     } 

     for (int i = restIndex; i < rest.size(); i++) { 
      whole.set(wholeIndex, rest.get(i)); 
      wholeIndex++; 
     } 
    } 

    private class Square { 
     private int[] location = new int[2]; 

     public Square(int x, int y) { 
      location[0] = x; 
      location[1] = y; 
     } 

     public int[] getLocation() { 
      return location; 
     } 

     @Override 
     public boolean equals(Object obj) { 
      if(obj instanceof Square) 
       if(getLocation()[0] == ((Square) obj).getLocation()[0] && 
         getLocation()[1] == ((Square) obj).getLocation()[1]) 
       return true; 
      return false; 
     } 

     @Override 
     public int hashCode() { 
      return Objects.hash(getLocation()[0], getLocation()[1]);  
     } 

     public int compareTo(Square arg0) { 
      if(getLocation()[0] > arg0.getLocation()[0]) { 
       return 1; 
      } else if(getLocation()[0] == arg0.getLocation()[0]) { 
       if(getLocation()[1] > arg0.getLocation()[1]) { 
        return 1; 
       } else if(getLocation()[1] == arg0.getLocation()[1]) { 
        return 0; 
       } else { 
        return -1; 
       } 
      } else { 
       return -1; 
      } 
     } 
    } 

    public static void main(String[] args) { 
     SortSquares e = new SortSquares(); 
     e.run(); 
    } 
} 

Answer 1

正好相反：標準方法要快得多。

首先，您在每次調用遞歸函數mergeSort時創建兩個數組。標準的可能將原始數組中的元素合併，並將索引用於範圍的開始和結束。

其次，標準的方法可以在多核機器上啓動新線程。

Answer 2

考慮算法它很大程度上取決於數據。

假設你的排序方法是快速排序。 您有O（n2）最差情況運行時和O（nlogn）平均情況運行時。

歸併總是爲O（n log n）的。這意味着穩定。這就是爲什麼它被選擇用於java集合的排序。

你實現的sort和mergesort是相同的算法（對Java集合進行排序基於合併排序）。您需要多次運行相同的代碼，並首先預熱jvm以獲得更可靠的結果。 不知何故，你可以確保你的自定義mergesort是有效的，並與集合進行比較。

在任何情況下，您都不必爲簡單的事情實施自己的合併排序。

Answer 3

您可以使用jdk的java.util.Collections.sort（List list）方法。如上所述，它使用複雜度爲O（nlogn）的合併排序。

爲了衡量您的實施的性能，並與其他實施進行比較，我建議使用jmh http://openjdk.java.net/projects/code-tools/jmh/。請在下面找到一個簡短的例子。

import org.openjdk.jmh.annotations.*; 
import org.openjdk.jmh.runner.Runner; 
import org.openjdk.jmh.runner.options.Options; 
import org.openjdk.jmh.runner.options.OptionsBuilder; 

import java.util.*; 
import java.util.concurrent.TimeUnit; 

@BenchmarkMode(Mode.AverageTime) 
@OutputTimeUnit(TimeUnit.NANOSECONDS) 
@State(Scope.Benchmark) 
@Warmup(iterations = 5) 
@Measurement(iterations = 5) 
@Fork(value = 1) 
public class SortingPerformanceBenchmark 
{ 
    private final int[] dataArray = new int[10_000_000]; 
    List<Integer> arrayList; 

    @Setup 
    public void load() { 
     Random rand = new Random(); 
     for (int i = 0; i < dataArray.length; ++i) { 
      dataArray[i] = rand.nextInt(); 
     } 
    } 

    @Benchmark 
    public List<Integer> Benchmark_SortObjects() { 
      arrayList = new ArrayList(Arrays.asList(dataArray)); 
      Collections.sort(arrayList); 

      return arrayList; 
    } 

    public static void main(String... args) throws Exception { 
     Options opts = new OptionsBuilder() 
     .include(SortingPerformanceBenchmark.class.getSimpleName()) 
     .build(); 
    new Runner(opts).run(); 
    } 
}