C＃中這個迭代算法有更好的功能版本嗎？

Question

我希望找出一種方法來寫下帶有擴展功能的功能樣式。理想情況下，與迭代/循環版本相比，這種功能風格會表現得很好。我猜測沒有辦法。可能是因爲有許多額外的函數調用和堆棧分配等等。

基本上我認爲使它變得麻煩的模式是它既計算一個用於謂詞的值，然後再次需要該計算值作爲由此產生的集合。

// This is what is passed to each function. 
// Do not assume the array is in order. 
var a = (0).To(999999).ToArray().Shuffle(); 

// Approx times in release mode (on my machine): 
// Functional is avg 20ms per call 
// Iterative is avg 5ms per call 
// Linq is avg 14ms per call 

private static List<int> Iterative(int[] a) 
{ 
    var squares = new List<int>(a.Length); 

    for (int i = 0; i < a.Length; i++) 
    { 
     var n = a[i]; 

     if (n % 2 == 0) 
     { 
      int square = n * n; 

      if (square < 1000000) 
      { 
       squares.Add(square); 
      } 
     } 
    } 

    return squares; 
} 

private static List<int> Functional(int[] a) 
{ 
    return 
    a 
     .Where(x => x % 2 == 0 && x * x < 1000000) 
     .Select(x => x * x) 
     .ToList(); 
} 

private static List<int> Linq(int[] a) 
{ 
    var squares = 
     from num in a 
     where num % 2 == 0 && num * num < 1000000 
     select num * num; 

    return squares.ToList(); 
} 

Answer 1

只是解決您的雙重計算問題：

return (from x in a 
     let sq = x * x 
     where x % 2 == 0 && sq < 1000000 
     select sq).ToList(); 

這就是說，我不知道，這將導致太多的性能提升。功能變體是否明顯比迭代變體更快？該代碼爲自動優化提供了相當多的潛力。

Answer 2

康拉德的建議的替代方案。這避免雙重計算，也避免了甚至計算平方時，它不必：

return a.Where(x => x % 2 == 0) 
     .Select(x => x * x) 
     .Where(square => square < 1000000) 
     .ToList(); 

就個人而言，我不會出汗性能上的差異，直到我看到它在顯著更大的上下文。 （我假設這僅僅是一個例子，通常情況下，你可能會計算一次1000000的平方根，然後比較n和那個，以減少幾毫秒的時間。兩個比較或當然Abs操作。）

編輯：請注意更多功能的版本將根本避免使用ToList。改爲返回IEnumerable<int>，並讓來電者將其轉換爲List<T>，如果他們想要。如果他們不這樣做，他們不會受到打擊。如果他們只想要前5個值，則可以撥打Take(5)。取決於上下文，懶惰可能是是對原始版本的巨大性能勝利。

Answer 3

某些並行處理如何？或者解決方案必須是LINQ（我認爲這很慢）。

var squares = new List<int>(a.Length); 

Parallel.ForEach(a, n => 
{ 
    if(n < 1000 && n % 2 == 0) squares.Add(n * n);    
} 

LINQ的版本是：

return a.AsParallel() 
    .Where(n => n < 1000 && n % 2 == 0) 
    .Select(n => n * n) 
    .ToList(); 

Answer 4

我不認爲有一個實用的解決方案，這將是完全開啓水準與迭代解決方案的性能，明智的。在我的計時中（見下文），來自OP的'功能'實現看起來大約是迭代實施的兩倍。

像這樣的微基準很容易出現各種問題。在應對變化問題的常見策略是反覆調用被計時的方法和計算每次通話的平均時間 - 這樣的：

// from main 
Time(Functional, "Functional", a);  
Time(Linq, "Linq", a);  
Time(Iterative, "Iterative", a); 
// ... 

static int reps = 1000; 
private static List<int> Time(Func<int[],List<int>> func, string name, int[] a) 
{ 
    var sw = System.Diagnostics.Stopwatch.StartNew(); 
    List<int> ret = null; 
    for(int i = 0; i < reps; ++i) 
    { 
     ret = func(a); 
    } 
    sw.Stop(); 
    Console.WriteLine(
     "{0} per call timings - {1} ticks, {2} ms", 
     name, 
     sw.ElapsedTicks/(double)reps, 
     sw.ElapsedMilliseconds/(double)reps); 
    return ret; 
} 

下面是一個會話定時：

 
Functional per call timings - 46493.541 ticks, 16.945 ms 
Linq per call timings - 46526.734 ticks, 16.958 ms 
Iterative per call timings - 21971.274 ticks, 8.008 ms 

有還有其他一些挑戰：定時器使用的選通效果，即時編譯器如何以及何時執行其操作，垃圾收集器運行其集合，競爭算法的運行順序，CPU的類型，操作系統交換其他進程等。

我嘗試了一下優化。我從測試中刪除了方塊（num * num < 1000000） - 將其更改爲（num < 1000） - 由於輸入中沒有負面因素，這似乎是安全的 - 也就是說，我取了不等式兩邊的平方根。令人驚訝的是，與OP中的方法相比，我得到了不同的結果 - 與OP實現中的三個實現中的241,849相比，我的優化輸出中只有500個項目。那麼爲什麼差異呢？當平方溢出32位整數時，輸入的大部分數據是這樣，所以這些額外的241,349項來自數字，當平方溢出到負數或低於100萬的數字時仍然通過我們的均勻性測試。

優化（功能性）的定時：

 
Optimized per call timings - 16849.529 ticks, 6.141 ms 

這是改變所建議的功能的實現方式之一。它按預期輸出通過標準的500個項目。它看似「更快」，只是因爲它比迭代解決方案輸出的項目更少。

我們可以通過在他們的實現中添加一個檢查塊來使原始實現爆炸並帶有OverflowException。下面是一個添加到「迭代」方法的選中塊：

private static List<int> Iterative(int[] a) 
{ 
    checked 
    { 
     var squares = new List<int>(a.Length); 

     // rest of method omitted for brevity... 

     return squares; 
    } 
}