F＃中不可變集合和映射的風格是什麼

Question

我剛剛在Project Euler中解決了problem23，其中我需要集合來存儲所有豐富的數字。 F＃有一個不可變的集合，我可以使用Set.empty.Add(i)創建一個包含數字i的新集合。但我不知道如何使用不可變集來做更復雜的事情。

例如，在下面的代碼中，我需要看看數字'x'是否可以寫成一個集合中兩個數字的總和。我使用排序的數組和二進制搜索算法來完成工作。

請也評論我的以下程序的風格。謝謝！

let problem23 = 
    let factorSum x = 
     let mutable sum = 0 
     for i=1 to x/2 do 
      if x%i=0 then 
       sum <- sum + i 
     sum 
    let isAbundant x = x < (factorSum x) 
    let abuns = {1..28123} |> Seq.filter isAbundant |> Seq.toArray 
    let inAbuns x = Array.BinarySearch(abuns, x) >= 0 
    let sumable x = 
     abuns |> Seq.exists (fun a -> inAbuns (x-a)) 
    {1..28123} |> Seq.filter (fun x -> not (sumable x)) |> Seq.sum 

更新版本：

let problem23b = 
    let factorSum x = 
     {1..x/2} |> Seq.filter (fun i->x%i=0) |> Seq.sum 
    let isAbundant x = x < (factorSum x) 
    let abuns = Set({1..28123} |> Seq.filter isAbundant) 
    let inAbuns x = Set.contains x abuns 
    let sumable x = 
     abuns |> Seq.exists (fun a -> inAbuns (x-a)) 
    {1..28123} |> Seq.filter (fun x -> not (sumable x)) |> Seq.sum 

這個版本在約27秒運行一次，而前23秒（我已經多次運行）。因此，與具有二分搜索的排序數組相比，不可變的紅黑樹實際上沒有太多速度下降。集合/數組中元素的總數是6965。

Answer 1

您可以根據給定的值序列輕鬆創建Set。

let abuns = Set (seq {1..28123} |> Seq.filter isAbundant) 

inAbuns因此將被改寫爲

let inAbuns x = abuns |> Set.mem x 

Seq.exists將改爲Set.exists

但陣列實現精細太...

注意，沒有必要在factorSum中使用可變值，除了因爲您錯誤計算除數，而不是它們的總和的數：

let factorSum x = seq { 1..x/2 } |> Seq.filter (fun i -> x % i = 0) |> Seq.sum 

Answer 2

你的風格看起來好像沒什麼問題。算法中的不同步驟很明確，這是使某些工作起作用的最重要的部分。這也是我用來解決歐拉問題的策略。先讓它工作，然後讓它快速。

正如已經指出的那樣，用Set.contains替換Array.BinarySearch使得代碼更具可讀性。我發現在幾乎所有我寫過的PE解決方案中，我只使用數組進行查找。我發現在F＃中使用序列和列表作爲數據結構更自然。一旦你習慣了他們，那就是。

我不認爲在函數內使用可變性肯定是不好的。我已經將問題155從近3分鐘優化到7秒，並進行了一些積極的可變性優化。一般來說，我會把它作爲一個優化步驟，並開始使用摺疊/過濾器等來編寫它。在問題155的例子中，我確實開始使用不可變的函數組合，因爲它進行了測試，最重要的是理解，我的方法很簡單。

選擇錯誤的算法對於解決方案比首先使用稍慢的不可變方法更不利。一個好的算法仍然很快，即使它比可變版本慢（沙發你好隊長明顯！咳嗽）。

編輯：讓我們來看看你的版本

你problem23b（）把31秒我的電腦上。

優化1：使用新算法。

//useful optimization: if m divides n, (n/m) divides n also 
//you now only have to check m up to sqrt(n) 
let factorSum2 n = 
    let rec aux acc m = 
     match m with 
     | m when m*m = n -> acc + m 
     | m when m*m > n -> acc 
     | m -> aux (acc + (if n%m=0 then m + n/m else 0)) (m+1) 
    aux 1 2 

這仍然是非常多的功能風格，但在代碼中使用此更新的factorSum，執行時間從31秒變爲8秒。

一切都還在一成不變的風格，但是讓我們看看當一個數組的查找是用來代替一組發生了什麼：

優化2：使用數組用於查找：

let absums() = 
    //create abundant numbers as an array for (very) fast lookup 
    let abnums = [|1..28128|] |> Array.filter (fun n -> factorSum2 n > n) 
    //create a second lookup: 
    //a boolean array where arr.[x] = true means x is a sum of two abundant numbers 
    let arr = Array.zeroCreate 28124 
    for x in abnums do 
     for y in abnums do 
      if x+y<=28123 then arr.[x+y] <- true 
    arr 

let euler023() = 
    absums() //the array lookup 
    |> Seq.mapi (fun i isAbsum -> if isAbsum then 0 else i) //mapi: i is the position in the sequence 
    |> Seq.sum 

//I always write a test once I've solved a problem. 
//In this way, I can easily see if changes to the code breaks stuff. 
let test() = euler023() = 4179871 

執行時間：0.22秒（！）。

這就是我非常喜歡F＃的地方，它仍然允許你使用可變結構來修飾你的算法。但我仍然只能在之後做到這一點我先做了一些更優雅的工作。

Answer 3

下面是一個簡單的功能的解決方案，是比原始和超過100 ×較短更快：

let problem23 = 
    let rec isAbundant i t x = 
    if i > x/2 then x < t else 
     if x % i = 0 then isAbundant (i+1) (t+i) x else 
     isAbundant (i+1) t x 
    let xs = Array.Parallel.init 28124 (isAbundant 1 0) 
    let ys = Array.mapi (fun i b -> if b then Some i else None) xs |> Array.choose id 
    let f x a = x-a < 0 || not xs.[x-a] 
    Array.init 28124 (fun x -> if Array.forall (f x) ys then x else 0) 
    |> Seq.sum 

第一招是記錄該數字是豐富在由該數字本身，而不是使用索引的數組一個搜索結構。第二個訣竅是要注意，所有的時間都花在生成該數組上，因此要並行執行。