.NET中的比較次數4.5排序

我知道4.5的排序算法從4.0改變，但我懷疑實現內省排序的東西是錯誤的。似乎在逆序排序列表的情況下行爲不規律，當有人希望與「排序」情況下的相同數量的比較（如4.0）時，這個數字奇怪地非常大。.NET中的比較次數4.5排序

.NET 4 64

隨機

25514058，分類20525265，顛倒20525285

.NET 4.5 64

隨機

22112103，分類16935357，反轉 !!

經常拿（使用4.0和4.5編譯）比較的數量的代碼是：

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace sortTest { 
class Program { 
    class CmpCount : IComparer<int> { 
     private int _count; 
     /// <summary> 
     /// 
     /// </summary> 
     public int Count { 
      get { 
       return _count; 
      } 
     } 



     public int Compare(int x, int y) { 
      _count++; 
      return x.CompareTo(y); 
     } 
    } 
    static void Main(string[] args) { 
     Random rnd = new Random(1234); 
     List<int> list = new List<int>(); 
     for (int i = 0; i < 1000000; i++) { 
      list.Add(rnd.Next()); 
     } 
     CmpCount cmp = new CmpCount(); 
     list.Sort(cmp); 
     int random = cmp.Count; 

     cmp = new CmpCount(); 
     list.Sort(cmp); 
     int sorted = cmp.Count; 

     cmp = new CmpCount(); 
     list.Reverse(); 
     list.Sort(cmp); 
     int reversed = cmp.Count; 

     Console.WriteLine("random {0}, sorted {1}, reversed {2}",random,sorted,reversed); 
    } 
} 
}

編輯：我調試的源代碼，似乎堆排序不會被調用。也許它需要一個特殊的製作輸入，這將觸發它。所以在上面的例子中，4.5排序實際上只是一個快速排序。

快速查看源代碼，似乎4.0 quicksort更復雜，而4.5是窮人（直接從書？）實現。

如果我理解正確，4.5也似乎盲目地傾向於已排序的列表。這也許是逆序排序列表的問題

來源

2013-06-12 Panos Theof

introsort的.NET 4.5實現開始嘗試執行Quicksort。當它看到遞歸深度超出特定點時，它將停止Quicksort並從Heap排序開始。

因此，期望大量的比較並不是不合理的，因爲算法正在進行部分排序，然後重新啓動以進行完全排序。

此外，沒有說明.NET Quicksort如何選擇項目來進行分區。可能它使用的是3的中值。但它是隨機抽取三個？首先，中間和最後？對於兩種相同的數組，分區可能不同（因此比較次數可能不同）。

無論如何，Introsort並不聲稱是完美的。算法很可能會檢測到潛在的最壞情況，並切換到堆排序，即使使用快速排序會更快。 Introsort避免了最壞情況的行爲，但有時可能表現出非最佳行爲。

另外，不能保證你排序的數組是相同的。你確定Random類的實現在.NET 4和.NET 4.5之間沒有變化嗎？有可能Random(1234)在4.5上創建了不同於4.0的序列。如果是這樣，你不會比較同一陣列上的排序。

來源

2013-06-12 17:09:41

我們可以通過嘗試更小的輸入數組來檢查是否正在觸發堆排序。在那之後，如果我們得出結論說它是按堆排序的話，那麼它似乎是唯一的原因就是你所說的是他們選擇關鍵點的方式不是原來的'中間值（第一，中間，最後）但別的東西（可能只是隨機？）。相關的，我認爲你對「隨機」的評論也是現貨，但原因不同。 OP並沒有聲稱這兩個數組在4.0和4.5中是相同的（實際上......它們應該是「隨機的」），但OP的樣本大小似乎沒有了。 – rliu

@roliu：他正在用種子初始化rng：'rnd = Random（1234）'，所以每次他在.NET 4上運行它時都會得到相同的序列。並且每個.NET 4.5運行都會得到相同的序列序列。這兩個序列是否相同是一個懸而未決的問題。樣本大小爲「1000000」：這是他添加到列表中的項目數。 –

對不起，我錯過了種子。對於樣本量，我的意思是列表數量。他反過來產生的特定隨機列表可能可以與quicksort一起使用，但不能插入。 – rliu

.NET中的比較次數4.5排序

回答

相關問題