Seq.iter比本機映射慢：任何通用解決方案？

問題已經顯示出之前，其原因由約翰·帕爾默回答： why is Seq.iter and Seq.map so much slower?Seq.iter比本機映射慢：任何通用解決方案？

let ar = Array.zeroCreate<int> (64*1024*1024) 
#time 
//Real: 00:00:00.171, CPU: 00:00:00.171, GC gen0: 0, gen1: 0, gen2: 0 
for i in 0 .. ar.Length - 1 do 
    ar.[i] <- ar.[i]*3 

//Real: 00:00:00.327, CPU: 00:00:00.328, GC gen0: 0, gen1: 0, gen2: 0 
ar |> Array.iteri(fun i _ -> ar.[i] <- ar.[i]*3) 

//Real: 00:00:02.249, CPU: 00:00:02.250, GC gen0: 0, gen1: 0, gen2: 0 
ar |> Seq.iteri(fun i _ -> ar.[i] <- ar.[i]*3)

我不知道是否有某種「內聯」，或者可以映射其他通用機制，說的序列（它的最後一個已知？）具體類型來加速這些行爲。例如在這裏我有靜態的保證，我會迭代一個數組。

你知道理論上存在滿意的解決方案嗎？（會有什麼奇特的名字？）

是否有一些語言很好地承認和解決這個問題？

來源

2012-11-28 nicolas

您可以使用F＃不支持的更高版本的泛型來做到這一點。Haskell和Scala都可以這樣做，並且類型可以像'Iterable c => ca - >（a - >（）） - >（）'，然後您可以爲'Array'，'Seq'和其他任何其他集合類型。你可能會發現感興趣的http://adriaanm.github.com/files/higher.pdf。 – Lee

你在做什麼，爲所有集合製作最佳的通用'map'和'iter'函數？我的猜測是，如果可能的話F＃不會有獨立的模塊，比如'Array'，'List'和'Seq'。 – Daniel

編譯器實際上做了一些優化 - 在https://github.com/fsharp/fsharp/blob/master/src/fsharp/FSharp.Core/seq.fs第1027行檢查「Seq.Length」的實現儘管它不會爲'map/iter'類型的函數打擾 –

的確，您在F＃中沒有更高的固定類型，但仍然可以使用內聯函數並模擬一些Typeclass行爲。通過定義你有一個通用的解決方案，以本地映射函子：

type Fmap = Fmap with 
    static member ($) (_Functor:Fmap, x:List<_>) = fun f -> List.map f x 
    static member ($) (_Functor:Fmap, x:array<_>) = fun f -> Array.map f x 
    static member ($) (_Functor:Fmap, x:_ [,] ) = fun f -> Array2D.map f x 
    static member ($) (_Functor:Fmap, x:_ [,,] ) = fun f -> Array3D.map f x 
    static member ($) (_Functor:Fmap, x:_ [,,,]) = fun f -> 
     Array4D.init (x.GetLength 0) (x.GetLength 1) (x.GetLength 2) (x.GetLength 3) (fun a b c d -> f x.[a,b,c,d]) 

let inline fmap f x = (Fmap $ x) f

就拿FMAP，這個功能是在線，它會接受在重載定義的任何類型，它會以最快的速度執行的調用函數直接（這是實際發生在幕後）。您可以使用fmap並放棄結果，在您的情況下，您可能需要定義類似fmapi的索引。

請記住，您應該始終使用具體類型調用這些函數，如果您通過Seq <'a>它將會失敗，您不應該混合兩種方法：子類型和ad-hoc多態性。

來源

2012-11-29 10:11:52 Gustavo

所以這就是答案，理論上，更好的類型，並且實際上增加了f＃代碼。然而，我認爲喬恩也有一個更高的關注點。 – nicolas

對於iter您可以檢查收集的類型併發送到最佳實施。遇到問題的位置是map，需要返回T<'b>以獲得某些T<'a>。這需要更高的KINED類型，F＃不直接支持。下面是在map說明該問題的嘗試：

module AnySeq = 
    let map<'a, 'b, 'c, 'd when 'a :> seq<'b> and 'd :> seq<'c>> (f: 'b -> 'c) (s: 'a) : 'd = 
    let (!) x = unbox (box x) 
    let tyDef = s.GetType().GetGenericTypeDefinition() 
    if tyDef = typedefof<list<_>> then !(List.map f !s) 
    elif tyDef = typedefof<array<_>> then !(Array.map f !s) 
    else !(Seq.map f !s)

如果你試圖用它來轉換一個int list到float list：

let ints = List.init 10000000 id 
let floats = ints |> AnySeq.map float

你得到的值限制錯誤：

The value 'floats' has been inferred to have generic type val floats : '_a when '_a :> seq

它可以工作，如果你添加一個類型註釋到floats，但你沒有完成任何事情。

來源

2012-11-28 17:02:23 Daniel

Do you know of satisfactory solution that exists in theory to this ? (what would be there fancy name ?)

你不能吃你的蛋糕和它。

Are there some langage that acknowledge and solve that issue nicely ?

F＃確認了這個問題並很好地解決了它。您可以擁有清晰的性能配置文件和像F＃一樣的快速編譯，或者由於大量複雜的編譯器以及特殊情況下的優化傳遞，您可能具有不可預知的性能配置文件和編譯速度慢的問題。 F＃選擇了前者（實用）的解決方案。

來源

2012-11-30 05:41:40

關於更一般的問題，你有一個很好的觀點。如果我可以標記2個答案，我也會標記這個答案。 – nicolas

Seq.iter比本機映射慢：任何通用解決方案？

回答

相關問題