爲什麼我的mergesort比我的quicksort慢？

他們都在同一時間複雜度，但是當我一個隨機產生的鏈表上運行我的歸併排序擁有10項：爲什麼我的mergesort比我的quicksort慢？

public LinkedList<Integer> linkedListSort(LinkedList<Integer> list) { 
    if (list.size() <= 1) return list; 
    LinkedList<Integer> left = new LinkedList<Integer>(); 
    LinkedList<Integer> right = new LinkedList<Integer>(); 
    int middle = list.size()/2; 
    for (int i = 0; i < middle; i++) { 
     left.add((int)list.get(i)); steps++; 
    } 
    for (int i = middle; i < list.size(); i++) { 
     right.add((int)list.get(i)); steps++; 
    } 
    left = linkedListSort(left); 
    right = linkedListSort(right); 
    return merge(left, right); 
} 

public LinkedList<Integer> merge(LinkedList<Integer> left, LinkedList<Integer> right) { 
    LinkedList<Integer> result = new LinkedList<Integer>(); 
    while (!(left.isEmpty()) && !(right.isEmpty())) { 
     steps++; 
     if ((int)left.peekFirst() <= (int)right.peekFirst()) { 
      result.add(left.poll()); 
     } else { 
      result.add(right.poll()); 
     } 
    } 
    while (!(left.isEmpty())) {result.add(left.poll()); steps++;} 
    while (!(right.isEmpty())) {result.add(right.poll()); steps++;} 
    return result; 
}

它比我的快速排序是慢了許多：

public String arraySort(int[] array, int startIndex, int endIndex, int steps) { 
    int leftIndex = startIndex; 
    int rightIndex = endIndex; 
    int pivot = array[(leftIndex + rightIndex)/2]; 
    while (leftIndex <= rightIndex) { 
     steps++; 
     //search for an element with a higher value than the pivot, lower than it 
     while (array[leftIndex] < pivot) {steps++; leftIndex++;} 
     //search for an element with a lower value than the pivot, higher than it 
     while (array[rightIndex] > pivot) {steps++; rightIndex--;} 
     //check the left index hasn't overtaken the right index 
     if (leftIndex <= rightIndex) { 
      //swap the elements 
      int holder = array[leftIndex]; 
      array[leftIndex] = array[rightIndex]; 
      array[rightIndex] = holder; 
      leftIndex++; rightIndex--; 
     } 
    } 
    if (leftIndex < endIndex) arraySort(array, leftIndex, endIndex, steps); 
    if (rightIndex > startIndex) arraySort(array, startIndex, rightIndex, steps); 
    return "Quicksort on an unsorted array took " + steps + " steps."; 
}

這是什麼原因？我的quicksort/mergesort不是它應該是的還是mergesort在鏈接列表上執行的數量很大的隨機數？或者是其他東西？

謝謝！

來源

2015-04-18 ErlangBestLanguage

你怎麼測量每個的速度？你是使用微觀基準框架還是隻是一個接着一個地執行一個？ –

你爲什麼期望mergesort比quicksort更快？ –

@LuiggiMendoza我一直沒有正確測量，但我必須等待至少10秒才能完成合並，但我的快速排序不需要很長時間。此外，我一直在測量每個進行比較的數量和快速排序將需要大約75000和mergesort將需要3337856. – ErlangBestLanguage

你已經實現了一個快速排序的版本，它可以在你的mergesort每次遞歸調用時複製左/右的內容（和merge()一樣）。這可能是造成差異的主要原因。

其次，就像上面評論中提到的Luiggi--你如何做你的基準測試？你有沒有得到適當的JVM熱身？你是否運行足夠的週期並取平均值？對JVM進行適當的基準測試可能會非常棘手：如果您沒有經驗，最好查找micro-benchmarking framework並使用它！

來源

2015-04-18 21:03:39 alfasin

這實際上是一個很好的觀點，我會重新考慮我是如何做我的mergesort！謝謝！此外，我還沒有涉足任何適當的基準測試，主要是因爲執行時間明顯較長，但我會考慮這一點，謝謝！ – ErlangBestLanguage

爲什麼我的mergesort比我的quicksort慢？

回答

相關問題