0

可能重复：
链表分区函数和相反的结果

实际上我不关心输入类型或输出类型，任何一个seq, array, list都可以。（它不必是通用的）目前我的代码list作为输入和(list * list)输出

let takeWhile predicator list =
   let rec takeWhileRec newList remain =
       match remain with
       | [] -> (newList |> List.rev, remain)
       | x::xs -> if predicator x then
                     takeWhileRec (x::newList) xs
                  else
                     (newList |> List.rev, remain)
   takeWhileRec [] list

但是，有一个陷阱。据我所知，List.rev是 O(n^2)，它可能会主导整体速度吗？我认为它甚至比丑陋的解决方案还要慢：Seq.takeWhile, then count, then take tailn 次...仍然是 O(n)

（如果有一个 C# 列表，那么我会使用它而不必反转它......）

Array.ofList一个附带问题， and List.toArray，或更一般地说，A.ofBand B.ofAin之间有什么区别List, Seq, Array？

等同seq myList于List.toSeq myList?

另一个问题，嵌套Seq.append的复杂性是否与Seq.concat？

例如

  Seq.append (Seq.append (Seq.append a b) c) d // looks aweful
  Seq.concat [a;b;c;d]
4

3 回答 3

2

要回答您的问题：

1) List.rev的时间复杂度是O(n)，最坏情况的复杂度takeWhile也是O(n)。所以使用List.rev不会增加函数的复杂性。使用ResizeArray可以帮助您避免List.rev，但您必须容忍一些突变。

let takeWhile predicate list =
   let rec loop (acc: ResizeArray<_>) rest =
       match rest with       
       | x::xs when predicate x -> acc.Add(x); loop acc xs
       | _ -> (acc |> Seq.toList, rest)
   loop (ResizeArray()) list

2）没有区别。Array.ofList并List.toArray在内部使用相同的功能（参见此处和此处）。

3）。我认为Seq.concat与一堆相同的复杂性Seq.append。在 和 的上下文中， List比因为您有更多信息来为输出预先分配空间而更有效。Arrayconcatappend

于 2012-10-26T11:21:34.113 回答
2

1）相关的实现List.rev在local.fs编译器中——它是

// optimized mutation-based implementation. This code is only valid in fslib, where mutation of private
// tail cons cells is permitted in carefully written library code.
let rec revAcc xs acc =
    match xs with
    | [] -> acc
    | h::t -> revAcc t (h::acc)

let rev xs =
    match xs with
    | [] -> xs
    | [_] -> xs
    | h1::h2::t -> revAcc t [h2;h1]

该评论确实看起来很奇怪，因为没有明显的突变。请注意，这实际上O(n)不是O(n^2)

2) 正如 pad 所说，没有区别 - 我更喜欢使用to..我认为的

A
|> List.map ...
|> List.toArray

看起来比

A
|> List.map ...
|> Array.ofList

但是，这只是我。

3)

附加（编译器源）：

[<CompiledName("Append")>]
let append (source1: seq<'T>) (source2: seq<'T>) =
    checkNonNull "source1" source1
    checkNonNull "source2" source2
    fromGenerator(fun () -> Generator.bindG (toGenerator source1) (fun () -> toGenerator source2))

请注意，对于每个附加，我们都会获得一个必须遍历的额外生成器。相比之下， concat 实现将只有 1 个额外的功能，而不是n这样使用concat可能更好。

于 2012-10-26T11:38:43.550 回答
1

这个怎么样：

let takeWhile pred =
    let cont = ref true
    List.partition (pred >> fun r -> !cont && (cont := r; r))

它使用一个高效实现的库函数 List.partition。希望这就是你的意思:)

于 2012-10-26T11:21:32.737 回答