一些基本的序列和列表问题 [英] Some basic seq and list questions

问题描述

可能重复:
链接列表分区功能和反向结果

Possible Duplicate:
Linked list partition function and reversed results

实际上，我并不关心输入类型或输出类型，任何seq, array, list都可以. (不必一定是通用的)目前，我的代码将list作为输入，将(list * list)作为输出

Actually I don't care about the input type or the output type, any of seq, array, list will do. (It doesn't have to be generic) Currently my code takes list as input and (list * list) as output

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，然后是count，然后再进行tail n次……这仍然是O(n)

However, there is a pitfall. As fas as I see, List.rev is O(n^2), which would likely to dominate the overall speed? I think it is even slower than the ugly solution: Seq.takeWhile, then count, and then take tail n times... which is still O(n)

(如果有C#列表，那么我将使用它而不必将其反转...)

(If there is a C# List, then i would use that without having to reverse it...)

一个附带的问题，Array.ofList和List.toArray之间，或更一般地说，在List, Seq, Array中的A.ofB和B.ofA之间有什么区别?

A side question, what's difference between Array.ofList and List.toArray , or more generally, A.ofB and B.ofA in List, Seq, Array?

seq myList与List.toSeq myList相同吗?

另一个问题，嵌套的Seq.append与Seq.concat具有相同的复杂性吗?

Another side question, is nested Seq.append have same complexity as Seq.concat?

例如

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

推荐答案

1)List.rev的相关实现在编译器的local.fs中-是

1)The relevant implementation of List.rev is in local.fs in the compiler - it is

// 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)

The comment does seem odd as there is no obvious mutation. Note that this is in fact O(n) not O(n^2)

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

2) As pad said there is no difference - I prefer to use the to.. as I think

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可能更好.

Note that for each append we get an extra generator that has to be walked through. In comparison, the concat implementation will just have 1 single extra function rather than n so using concat is probably better.

这篇关于一些基本的序列和列表问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！