3

在查看了这两个线程之后：F# 是否具有与 Haskell 相同的功能？，从 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'之间的每次转换对性能的影响？

非常感谢。

4

5 回答 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版本非常好。

于 2011-09-15T02:28:58.083 回答
3

其中一些可能取决于您希望如何端到端地使用所有这些。

在许多情况下，最好先转换为列表，然后只使用列表运算符来映射/遍历/等。可能没有 a List.take，但那是因为对于列表，如果您知道将至少有两个元素并且您想抓住这两个元素，您可以通过模式匹配来做到这一点，例如

let (item1::item2::rest) = someList

所以我怀疑这可能是您在这种情况下想要做的（我希望通过 HTML 解析，您可能有某种预期的粗略模式，您正在寻找的元素等等）。

（如果惰性/流式传输是必不可少的，那么 Seq 变得更加有用。）

简而言之，最常见的运算符（like map）适用于所有集合类型（Seq, List, Array, ...），而不常见的运算符（like ）take仅在 Seq 上可用，通常是因为当你有一个具体的类型时有更好的方法来做事（例如列表模式匹配以获取第一个项目）。

于 2011-09-15T00:33:19.810 回答
2

添加评论

在纯粹的功能意义take上不能对列表进行操作 - 考虑

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

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

a::b::[]

由于b已修改，您还需要修改a以使其指向新修改的b. 因此，不可能在列表中实现就位，这就解释了为什么List模块中缺少它。

如果您真的担心性能，请先配置文件，然后再考虑切换到不同的数据类型。您可能最好使用System.Collections.Generic.List<_>具有许多相同方法的 .NetList和Array- http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/manual/fsharp.powerpack/microsoft.fsharp .collections.resizearray.html

于 2011-09-15T00:55:02.483 回答
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

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

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 个滴答声，这表明懒惰与观察到的现象无关。

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

于 2011-09-15T03:55:27.690 回答
1

List to Seq 只不过是在 List 上创建一个迭代器（在 .net 世界中是一个 Enumerable），所以基本上它不是一个会导致很多性能问题的操作（它只是创建一个状态机来保存关于它的状态列表中需要'yield'的当前元素，并在请求更多元素时增加它）。另一方面，将 Seq（它将具有一些从中产生值的基础集合）转换为 List 在概念上与迭代列表并从中创建新列表相同，因此它可能是一个耗时和消耗内存的过程，以防列表足够长。

As far as usage of these operator goes one possible approach would be to group all your sequence operator together (same as linq queries where your sort of create a pipeline through which the collection elements gets processed one by one) and then in the end if you need you can create the list from resulting Seq as the list is created at the end of all the filtering, mapping, take etc work on seq and when the final data is ready you convert it to List. Creating intermediate lists will not work out well and will cause performance issues.

于 2011-09-15T04:12:00.860 回答