链接列表分区功能和扭转业绩 [英] Linked list partition function and reversed results
问题描述
我写了这个F#功能分区列表达到一定点并没有进一步的 - 就像在 takeWhile
交叉和分区
。
I wrote this F# function to partition a list up to a certain point and no further -- much like a cross between takeWhile
and 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
唯一的问题是,采取项目是相反的:
The only problem is that the "taken" items are reversed:
> partitionWhile ((>=) 5) [1..10];;
val it : int list * int list = ([5; 4; 3; 2; 1], [6; 7; 8; 9; 10])
除了诉诸调用转
,有没有办法这个功能可以写,将有第一个列表是正确的顺序?
Other than resorting to calling rev
, is there a way this function could be written that would have the first list be in the correct order?
推荐答案
下面是一个基于延续的版本。这是尾递归并返回列表中的原始顺序。
Here's a continuation-based version. It's tail-recursive and returns the list in the original order.
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
下面是一些基准一起去讨论以下布莱恩的回答(和蓄能器版本以供参考):
Here are some benchmarks to go along with the discussion following Brian's answer (and the accumulator version for reference):
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
厘泊
平均〜7秒,加</ code>〜4秒。总之,延续你买什么了这项工作。
Cps
averaged ~7s, Acc
~4s. In short, continuations buy you nothing for this exercise.
这篇关于链接列表分区功能和扭转业绩的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!