2

这个问题之前已经出现过，John Palmer 回答了它的原因： 为什么 Seq.iter 和 Seq.map 这么慢？

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)

我想知道是否有某种“内联”或其他通用机制可以映射，比如将序列映射到（它最后知道的？）具体类型以加速这些行为。例如，在这里我有静态保证我将遍历一个数组。

您知道理论上存在对此的满意解决方案吗？（会有什么花哨的名字？）

是否有一些语言可以很好地承认和解决这个问题？

4

3 回答 3

4

确实，您在 F# 中没有更高种类的类型，但您仍然可以使用内联函数并模拟一些 Typeclass 行为。通过定义 Functor，您可以获得原生映射的通用解决方案：

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> 它将失败，您不应该混合两种方法：子类型和临时多态性。

于 2012-11-29T10:11:52.550 回答
2

您知道理论上存在对此的满意解决方案吗？（会有什么花哨的名字？）

你不能吃你的蛋糕。

是否有一些语言可以很好地承认和解决这个问题？

F# 承认了这个问题并很好地解决了它。您可以像 F# 一样拥有清晰的性能配置文件和快速编译，也可以拥有不可预知的性能配置文件和缓慢的编译，这是由于大量复杂的编译器装载了针对此类特殊情况的优化通道。F# 选择了前一种（务实的）解决方案。

于 2012-11-30T05:41:40.793 回答
0

因为iter您可以检查集合的类型并分派到最佳实现。您遇到问题的地方是 with map，需要返回T<'b>一些T<'a>. 这需要 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)

如果您尝试使用它将 an 转换int list为float list：

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

你得到一个值限制错误：

'floats' 值已被推断为具有泛型类型 val floats : '_a when '_a :> seq

如果您向 中添加类型注释，它会起作用floats，但是您还没有完成任何事情。

于 2012-11-28T17:02:23.517 回答