代码之家  ›  专栏  ›  技术社区  ›  Markus Deibel

F中的类型的列表成员是否需要显式缓存#

  •  1
  • Markus Deibel  · 技术社区  · 6 年前

    我的问题可能是对f编译器到底有多聪明这个问题进行了深入研究。

    我有一个类型模块,它扫描一个配置文件,然后应该在起始地址和结束地址之间提供一个IP地址范围。

    type IpRange (config: string) =
        // Parse the config
        member __.StartIp = new MyIp(startIp)
        member __.EndIp = new MyIp(endIp)
    

    现在我想增加实际的范围给我所有的IP,所以我增加了

        member __.Range = 
            let result = new List<MyIp>()
            let mutable ipRunner = __.StartIp
            while ipRunner <= __.EndIp do
                result.Add(new MyIp(ipRunner))
                ipRunner <- (ipRunner + 1)
            result
    

    这很有效,但不是真正的习惯用法。

    然后我深入研究这个问题,提出了以下两个备选方案

    let rec GetIpRangeRec (startIp: MyIp) (endIp: MyIp) (ipList: MyIp list) = 
        if startIp <= endIp then
            GetIpRangeRec (startIp + 1) endIp (ipList@[startIp])
        else
            ipList 
    

    let GetIpRangeUnfold (startIp: MyIp) (endIp: MyIp) =
            startIp |> Seq.unfold(fun currentIp -> 
                                    if (currentIp <= endIp) then 
                                        Some(currentIp, currentIp + 1) 
                                    else 
                                        None)
    

    据我从阅读列表和序列中了解到的,没有缓存。因此,当我试图访问一个项目或枚举列表时,这三个解决方案都将重新评估代码以创建一个列表。

    我可以用 Seq.cache (如果需要的话,前面的强制转换到序列)导致

    member __.Range =
        GetIpRangeRec startIp endIp []
        |> List.toSeq
        |> Seq.cache
    

    但这真的有必要吗?

    我觉得我遗漏了一些东西,而f编译器实际上缓存了结果而没有明确地告诉它。

    2 回复  |  直到 6 年前
        1
  •  4
  •   Jarak    6 年前

    列表(通常至少,我想可能有一些我不知道的奇怪的边缘情况)直接存储为它们的值。因此,递归函数将专门生成 MyIp 只有当你做了一些奇怪的事情 MyIP 每次访问时都会重新评估。如中所示,当函数返回时,您将得到一个完整的 MyIP S.

    然而,有一个小问题,即您所实现的功能并不是特别有效。相反,我建议用这种稍微有点另类的方式来做:

    let rec GetIpRangeRec (startIp: MyIp) (endIp: MyIp) (ipList: MyIp list) = 
        if startIp <= endIp then
            GetIpRangeRec (startIp + 1) endIp (startIp :: ipList)
        else
            List.rev ipList 
    

    基本上,问题是每次使用 @ 运算符要附加到列表的末尾,运行时必须步行到列表的末尾才能进行附加。这意味着您将最终对列表进行大量的迭代。相反,最好只是提前(即追加,但在前面),然后在返回列表之前反转列表。这意味着您只需要遍历列表一次,因为预处理始终是一个常量时间操作(您只需创建一个新的列表条目,其中包含指向列表前面的指针)。

    实际上,由于您可能不想在函数之外使用预先提供的列表,因此我建议您改为这样做:

    let GetIpRange startIp endIp = 
        let rec GetIpRangeRec (start: MyIp) (end: MyIp) (ipList: MyIp list) = 
            if start <= end then
                GetIpRangeRec (start + 1) end (start :: ipList)
            else
                List.rev ipList 
    
        GetIpRangeRec startIp endIp List.empty
    

    (请注意,我没有测试过这个,所以它可能不会完全工作)。如果你真的想预先提供一个开始清单,那么你可以坚持第一个清单。

    另外,请记住,虽然列表通常适合顺序访问,但是对于随机访问来说,它们是很糟糕的。如果您需要对列表进行随机查找,那么我建议您使用 List.toArray 一旦你把完整的清单拿回来。不过,如果您只是按顺序迭代,那么可能不需要麻烦。

    不过,我还要再强调一点:从全功能编程“纯粹主义”的角度来看,您的第一个实现可能并不完全是“功能性的”,但所涉及的唯一可变性都隐藏在函数内部。也就是说,您不会改变传递给函数的任何内容。从功能纯度的角度来看,这是非常好的,可能有利于性能。记住,F首先是功能性的,而不仅仅是狂热的功能性的;)

    编辑:我想再加一件事:我不知道你 MyIP 类型是被构造的,但是如果你能用数字来构建它们,那么使用序列理解可能是值得的,比如 seq {1 .. 100} 然后用管道输送到 map 创建 MyIP S,例如 seq {1 .. 100} |> Seq.map makeIp |> Seq.toList . 这将是最简单的方法,但仅当您可以简单地指定一个简单的数字范围时才有效。

        2
  •  2
  •   Just another metaprogrammer    6 年前

    Seq 在f中比较懒惰(偶尔缓存结果也有好处)。弗斯 List 不是懒惰,它是一个不变的单链表,不会从缓存中得到任何好处。