4

我这里有这个功能：

let ProcessFile (allLines: string list) = 
    let list = new List<List<string>>()

    let rec SplitFile (input: string list) =
        if input.Length <> 0 then
            list.Add(new List<string>(input.TakeWhile(fun x -> x <> "")))
            let nextGroup = input.SkipWhile(fun x -> x <> "").SkipWhile(fun x -> x = "")
            SplitFile (Seq.toList nextGroup)

    SplitFile allLines |> ignore
    list

它以字符串列表的形式给出文件的内容，并将由空行分隔的每个组作为单独的列表，给我一个列表列表。

我的问题是，有没有更好的方法来做这个，它给我一个类似于字符串列表列表的东西，而不是我不得不使用 new List< List< string>>？因为这对我来说似乎不是特别整洁。

4

4 回答 4

5

更惯用的解决方案可能是：

let processFile xs =
  let rec nonEmpties n = function
    | [] as xs | ""::xs -> n, xs
    | _::xs -> nonEmpties (n+1) xs
  let rec loop xs =
    seq { match xs with
          | [] -> ()
          | ""::xs -> yield! loop xs
          | xs ->
              let n, ys = nonEmpties 0 xs
              yield Seq.take n xs
              yield! loop ys }
  loop xs

其中嵌套nonEmpties函数计算给定列表前面有多少非空元素，并在最后一个非空元素之后返回计数和尾部列表，该loop函数跳过空元素并产生非空元素序列.

该解决方案的一些有趣特征：

  • 完全尾递归，因此它可以处理任意长的非空字符串序列和非空字符串序列序列。

  • 通过返回输入列表来避免复制。

在测试输入 1,000 个 1,000 个字符串的序列时，这个解决方案比 yamen 的快 8 倍，比 Tomas 的快 50%。

这是一个更快的解决方案，它首先将输入列表转换为数组，然后作用于数组索引：

let processFile xs =
  let xs = Array.ofSeq xs
  let rec nonEmpties i =
    if i=xs.Length || xs.[i]="" then i else
      nonEmpties (i+1)
  let rec loop i =
    seq { if i < xs.Length then
            if xs.[i] = "" then
              yield! loop (i+1)
            else
              let j = nonEmpties i
              yield Array.sub xs i (j - i)
              yield! loop j }
  loop 0

On test input of 1,000 sequences of 1,000 strings this solution is 34x faster than yamen's and 6x faster than Tomas'.

于 2012-06-27T12:16:49.390 回答
2

您的代码对我来说非常易读，但是递归地使用TakeWhile和使用SkipWhile效率相当低。这是一个简单的函数递归解决方案：

let ProcessFile (allLines: string list) =
  // Recursively processes 'input' and keeps the list of 'groups' collected
  // so far. We keep elements of the currently generated group in 'current'  
  let rec SplitFile input groups current = 
    match input with 
    // Current line is empty and there was some previous group
    // Add the current group to the list of groups and continue with empty current
    | ""::xs when current <> [] -> SplitFile xs ((List.rev current)::groups) []
    // Current line is empty, but there was no previous group - skip & continue
    | ""::xs -> SplitFile xs groups []
    // Current line is non-empty - add it to the current group
    | x::xs -> SplitFile xs groups (x::current)
    // We reached the end - add current group if it is not empty
    | [] when current <> [] -> List.rev ((List.rev current)::groups)
    | [] -> List.rev groups

  SplitFile allLines  [] []

ProcessFile ["a"; "b"; ""; ""; "c"; ""; "d"]

seq { ... }基本上可以使用如下方式编写相同的代码。我们仍然需要使用current累加器yield（yield!

let ProcessFile (allLines: string list) =  
  let rec SplitFile input current = seq {
    match input with 
    | ""::xs when current <> [] -> 
        yield List.rev current
        yield! SplitFile xs []
    | ""::xs -> 
        yield! SplitFile xs []
    | x::xs -> 
        yield! SplitFile xs (x::current)
    | [] when current <> [] -> 
        yield List.rev current
    | [] -> () }

  SplitFile allLines []
于 2012-06-27T11:37:41.053 回答
0

就个人而言，我喜欢一个班轮：

let source = ["a"; "b"; ""; ""; "c"; ""; "d"]

source                                                                       // can be any enumerable or seq
|> Seq.scan (fun (i, _) e -> if e = "" then (i + 1, e) else (i, e)) (0, "")  // add the 'index'
|> Seq.filter (fun (_, e) -> e <> "")                                        // remove the empty entries
|> Seq.groupBy fst                                                           // group by the index
|> Seq.map (fun (_, l) -> l |> Seq.map snd |> List.ofSeq)                    // extract the list only from each group (discard the index)
|> List.ofSeq                                                                // turn back into a list

这里最大的问题是Seq.groupBy将整个列表读入内存，但无论如何你都在这样做。有一些实现groupBy只会查看相邻的条目，这就足够了，并且可以让您将文件输入为 aSeq而不是（例如，使用File.ReadLines而不是File.ReadAllLines）。

于 2012-06-27T11:53:44.497 回答
0

How about using plain old List.fold

let processFile lines =
([], lines) ||>
List.fold(fun acc l -> 
    match acc with
        | [] when l = "" -> acc        // filter empty lines at the start of the file
        | [] -> [[l]]                  // start the first group
        | []::xss when l = "" -> acc   // filter continous empty lines
        | xs::xss when l = "" ->       // found an empty line, start a new group
            let rxs = List.rev xs      // reverse the current group before starting a new one
            []::rxs::xss
        | xs::xss -> (l::xs)::xss)     // continue adding to the current group
|> List.rev
于 2012-06-27T17:08:03.493 回答