Сортировка arraylist с mergesort vs custom sort

Question

Я пишу программу, которая должна иметь возможность сортировать до 1 миллиарда случайных Squares. Я написал небольшую примерную программу ниже, которая создает случайный ArrayList из Squares, а затем сортирует его двумя разными способами.

Когда я искал эффективный метод сортировки, я обнаружил, что использование 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. Стандартный, вероятно, объединяет элементы inplace в исходном массиве и использует индексы для начала и конца диапазона.

Во-вторых, стандартный метод может запускать новые потоки на многоядерных машинах.

Answer 2

Рассмотрение алгоритмов В основном это зависит от данных.

Предположительно, ваш метод сортировки является быстрой сортировкой. У вас есть O (n2) наихудшее время исполнения и среднее время выполнения O (nlogn).

Mergesort всегда O (n log n). Это означает стабильность. Именно поэтому он был выбран для сортировки для коллекций java.

Оба типа и объединившаяся реализация - это один и тот же алгоритм (сортировка по коллекциям java основана на сортировке слияния). Вам нужно запустить один и тот же код много раз и сначала разогреть свой jvm, чтобы получить более надежные результаты. Как-то вы можете убедиться, что ваш пользовательский mergesort эффективен и сопоставляет с коллекциями.

В любом случае вам не нужно реализовывать свой собственный метод слияния для чего-то простого.

Answer 3

Вы можете использовать метод java.util.Collections.sort (Список) из jdk. Как упоминалось выше, он использует сортировку слияния со сложностью 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(); 
    } 
}