链表分区功能和反向结果

一尘不染

链表分区功能和反向结果

algorithm

我写了这个F＃函数，将列表分区到某个点，而且不再进一步-就像takeWhile和之间的交叉partition。

let partitionWhile c l =
    let rec aux accl accr =
        match accr with
        | [] -> (accl, [])
        | h::t ->
            if c h then
                aux (h::accl) t
            else
                (accl, accr)
    aux [] l

唯一的问题是“已摄取”项目是相反的：

> partitionWhile ((>=) 5) [1..10];;
val it : int list * int list = ([5; 4; 3; 2; 1], [6; 7; 8; 9; 10])

除了求助之外rev，还有没有其他方法可以编写此函数，使第一个列表的顺序正确？

阅读 179

2020-07-28

共1个答案

一尘不染

这是基于延续的版本。它是尾递归的，并以原始顺序返回列表。

let partitionWhileCps c l =
  let rec aux f = function
    | h::t when c h -> aux (fun (acc, l) -> f ((h::acc), l)) t
    | l -> f ([], l)
  aux id l

以下是一些基准，以及Brian回答后的讨论（以及累加器版本供参考）：

let partitionWhileAcc c l =
  let rec aux acc = function
    | h::t when c h -> aux (h::acc) t
    | l -> (List.rev acc, l)
  aux [] l

let test = 
  let l = List.init 10000000 id
  (fun f ->
    let r = f ((>) 9999999) l
    printfn "%A" r)

test partitionWhileCps // Real: 00:00:06.912, CPU: 00:00:07.347, GC gen0: 78, gen1: 65, gen2: 1
test partitionWhileAcc // Real: 00:00:03.755, CPU: 00:00:03.790, GC gen0: 52, gen1: 50, gen2: 1

Cps平均约7 Acc秒，约4秒。简而言之，继续进行此练习不会给您带来任何好处。

2020-07-28