logo标签列表

F#列表与序列运算符

listf#seq
3

看完这两个线程：F#有没有类似于Haskell中的take函数的等价物?，从F#序列中取N个具有N个不同索引的元素，我一直在思考在列表上使用序列运算符的最佳方法，或者是否使用它们。

目前，我是F#的新手，并正在编写一个程序，需要处理从HtmlAgilityPack获得的大量序列。Seq模块中有一些有趣的运算符，但正如那些线程中所述，可能与性能相关性差，如果我们被迫不断在seq和list之间进行转换，还会使代码混杂着一些非问题解决的内容......这也是我学习F#的原因。

举个简单的例子，当我需要从列表中取出'N'个元素时:

               listOfRows
               |> Seq.take 2
               // Now I don't have a list anymore, it returns a sequence
               |> List.ofSeq

那么，有人能够解释一下处理这些情况的最佳方法吗？我可以使用Seq.take和Seq.skip来解决问题，但这被认为是非常低效的。另一方面，很遗憾将功能内置于标准库中，并且不得不重新实现它以在不同的集合上使用相同的概念，或者通过显式转换使代码变得更加混乱。
我如何看待'list -> seq'和'seq -> list'之间每次转换的性能影响？
非常感谢。
5个回答
6
这些内容相当容易实现。
module List =

  let take n items =
    let rec take' acc = function
      | 0, _ -> List.rev acc
      | _, [] -> invalidOp "count exceeds number of elements"
      | n, h::t -> take' (h::acc) (n-1, t)
    take' [] (n, items)

  let rec skip n items =
    match n, items with
    | 0, _ -> items
    | _, [] -> invalidOp "count exceeds number of elements"
    | n, _::t -> skip (n-1) t

这里是它们与它们的 Seq 对应物相比的表现。

let n = 10000000
let l = List.init n id
let test f = f (n-1) l

test List.take               //Real: 00:00:03.724, CPU: 00:00:03.822, GC gen0: 57, gen1: 34, gen2: 1
test Seq.take |> Seq.toList  //Real: 00:00:04.953, CPU: 00:00:04.898, GC gen0: 57, gen1: 33, gen2: 0
test List.skip               //Real: 00:00:00.044, CPU: 00:00:00.046, GC gen0: 0, gen1: 0, gen2: 0
test Seq.skip |> Seq.toList  //Real: 00:00:01.147, CPU: 00:00:01.154, GC gen0: 0, gen1: 0, gen2: 0

如果你的应用程序时间毫秒级别很重要，那么也许值得创建“缺失”的“List”函数。否则，我会说使用“Seq”版本是完全可以的。
非常感谢您编写测试所付出的努力，这对于做出决策非常有帮助。我可能在问题上有些混淆，因为它也是为了理解“为什么我们应该自己重新实现这些运算符”。非常感谢您提供的代码，对我来说将非常有用。 - Jacobo Polavieja
我认为Brian和jpalmer的回答解释了为什么它们没有被实现到列表中。我能给出的唯一另一个原因是：由于list是seq，需要基于游标访问集合的函数只需要针对最抽象的类型seq实现。你自己去实现这些函数所得到的收益微乎其微，这也是我回答的部分意义所在。 - Daniel
3
一些内容的翻译可能取决于您如何使用全部端到端。
在许多情况下，一次性转换为列表，然后仅使用List操作符进行映射/遍历等操作即可。虽然没有“List.take”，但这是因为对于列表，如果您知道至少有两个元素并且想要获取这两个元素，则可以通过模式匹配来实现。例如：
let (item1::item2::rest) = someList

我怀疑这可能是您在此场景中想要做的事情（我预计使用HTML解析时，您可能已经有了一些期望的元素粗略模式等）。如果懒惰/流式传输很重要，那么Seq变得更加有用。简而言之，常见运算符（如map）都在所有集合类型（Seq、List、Array等）上，而不常见的运算符（如take）只在Seq上可用，通常是因为在具体类型时有更好的方法来完成任务（例如列表模式匹配以取出前几项）。
非常感谢。你说得完全正确，由于我刚开始学习 F#，我真的不知道我可以使用这种方式对列表进行模式匹配，这对我正在做的事情非常有用。非常感谢。 - Jacobo Polavieja
2

添加评论

就功能而言，take无法在原列表上进行操作-请考虑

a::b::c::d::[]

如果我们只想要前两个元素，那么我们至少需要修改 b 以便获得：

a::b::[]

自从修改了b，您还需要修改a，以便它指向新修改的b。因此，在列表上无法实现就地获取，这解释了为什么List模块中缺少该功能。如果您真的担心性能，请先进行分析，然后考虑切换到不同的数据类型。您可能更适合使用.Net System.Collections.Generic.List<_>，它具有许多与List和Array相同的方法-http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/manual/fsharp.powerpack/microsoft.fsharp.collections.resizearray.html
2

通过检查相应的转换实现，您可以完全理解Seq -> List和List -> Seq的性能影响：

// List.ofSeq
let ofSeq source = Seq.toList source
// List.toSeq
let toSeq list = Seq.ofList list
// Seq.ofList
let ofList (source : 'T list) = 
        (source :> seq<'T>)
// Seq.toList
let toList (source : seq<'T>) = 
        checkNonNull "source" source
        match source with 
        | :? ('T list) as res -> res
        | :? ('T[]) as res -> List.ofArray res
        | _ -> 
            use e = source.GetEnumerator()
            let mutable res = [] 
            while e.MoveNext() do
                res <- e.Current :: res
            List.rev res

与集合上的实际操作相比，转换本身对性能的影响相对较小。在我的旧Core 2 Duo 2.4Ghz笔记本上运行以下代码片段，将包含100万个元素的List转换为seq，然后再转回另一个List。

open System.Diagnostics

let tls = Stopwatch()
let l = [1..1000000]
tls.Start()
let s = List.toSeq l
//Seq.length s |> ignore
//Seq.length s |> ignore
tls.Stop()
printfn "List<int> of 1000000 -> Seq: %d ticks" tls.ElapsedTicks 

let tsl = Stopwatch()
tsl.Start()
let l' = Seq.toList s
//l'.Length |> ignore
//l'.Length |> ignore
tsl.Stop()
printfn "Seq<int> of 1000000 -> List: %d ticks" tsl.ElapsedTicks

显示分别为42和8个刻度的爆破。如果我们取消注释带有长度计数器执行的第一行，执行时间将为18695和12952个刻度。取消注释带有长度计数器执行的第二行后，执行持续时间显示为38377和25404个刻度，这表明惰性与观察到的现象无关。

似乎Seq和List类型之间的转换开销与集合操作的执行本身相比可以忽略不计。

微不足道？还是他们真的这么粗心？ - Daniel
非常感谢！解释得非常清楚。 - Jacobo Polavieja
1
List to Seq 就是在 List 上创建一个迭代器（在 .net 世界中是 Enumerable），因此它基本上不会引起太多性能问题（它只创建一个状态机，保存关于哪个是需要“yield”的当前元素的状态，并随着请求更多元素而递增）。另一方面，将 Seq（它将具有某些底层集合，从中产生值）转换为 List 在概念上与迭代列表并从中创建新列表相同，因此如果列表足够长，则可能是一个耗时和占用内存的过程。
就这些运算符的使用而言，一个可能的方法是将所有序列运算符分组在一起（与 linq 查询相同，其中您创建了一个管道，通过该管道逐个处理集合元素），然后最终如果需要，可以从结果 Seq 创建列表，因为列表是在对 seq 进行所有过滤、映射、take 等操作的末尾创建的，当最终数据准备好时，您将其转换为 List。创建中间列表将无法很好地工作，并会导致性能问题。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接