如何使用 F# 获取没有第一个和最后一个项目的子列表？

Question

我已经对整数值列表进行了排序：

let ls = [1..4]

如何获得没有第一个和最后一个元素的子列表？（以最优化的方式）

预期结果是[2; 3]。

这是我目前所拥有的，是的，它正在工作，但我认为这不是最好的方法。

[1..4] |> List.tail |> List.rev |> List.tail |> List.sort

Answer 1

您不需要标准库函数来实现此目的，您只是在寻求一种有效的方法。使用保存中间结果的累加器定义递归函数将是一个可行的解决方案，即使列表必须在其终止时反转。

我正在提供一个自定义的可区分联合来跟踪状态，这是按照 Option type 的方式建模的，带有一个额外的案例。

type 'a State = Zero | One | Other of 'a

let skipFirstAndLast xss =
    let rec aux acc = function
    | _,            []    -> List.rev acc
    | Zero,         x::xs -> aux acc (One, xs)
    | One,          x::xs -> aux acc (Other x, xs)
    | (Other prev), x::xs -> aux (prev :: acc) (Other x, xs)
    aux [] (Zero, xss)

[1..4] |> skipFirstAndLast // val it : int list = [2; 3]

Answer 2

这是其中一种方式：

let rec trim ls acc =
    match ls, acc with
    | [],      _   -> acc
    | h::[],   acc -> List.rev acc
    | h::n::t, []  -> trim t [n]  
    | h::t,    acc -> trim t (h::acc)

let reslt = trim ls []

Answer 3

为了回应您措辞天真的限定词，我们收到了一个有点长的答案："In the most optimal way"

在什么方面最优化？

性能？（最有可能）
性能还包括GC性能？
内存使用情况？
x86?
x64?

等等...

所以我决定衡量问题的某些方面。

我在各种不同的上下文中测量了此线程中的不同答案（也添加了非惯用版本）。

不用多说，这是我用来测量的程序

open System
open System.Diagnostics
open System.IO

module so29100251 =
    // Daystate solution (OP)
    module Daystate =
        // Applied minor fixes to it
        let trim = function
            | [] | [_] | [_;_] -> []
            | ls -> ls |> List.tail |> List.rev |> List.tail |> List.rev

    // kaefer solution
    module kaefer =
        type 'a State = Zero | One | Other of 'a

        let skipFirstAndLast xss =
            let rec aux acc = function
            | _,            []    -> List.rev acc
            | Zero,         x::xs -> aux acc (One, xs)
            | One,          x::xs -> aux acc (Other x, xs)
            | (Other prev), x::xs -> aux (prev :: acc) (Other x, xs)
            aux [] (Zero, xss)

    // Petr solution
    module Petr =
        let rec trimImpl ls acc =
            match ls, acc with
            | [],      _   -> acc
            | h::[],   acc -> List.rev acc
            | h::n::t, []  -> trimImpl t [n]
            | h::t,    acc -> trimImpl t (h::acc)

        let trim ls = trimImpl ls []

    // NonIdiomatic solution
    module NonIdiomatic =
        let trim (hint : int) (ls : 'T list) =
            // trims last of rest

            // Can't ask for ls.Length as that is O(n)
            let ra = ResizeArray<_> (hint)

            // Can't use for x in list do as it relies on .GetEnumerator ()
            let mutable c = ls
            while not c.IsEmpty do
                ra.Add c.Head
                c <- c.Tail

            let count = ra.Count

            let mutable result = []
            for i in (count - 2)..(-1)..1 do
                result <- ra.[i]::result
            result

open so29100251

type Time = MilliSeconds of int64

type TestKind<'T> =
     | Functional               of 'T
     | MeasurePerformance       of int*int

[<EntryPoint>]
let main argv =
    let factor  = 10000000
//    let maxHint = Int32.MaxValue
    let maxHint = 100

    let time (action : unit -> 'T) : 'T*Time =
        let sw = Stopwatch ()

        sw.Start ()

        let r = action ()

        sw.Stop ()

        r, MilliSeconds sw.ElapsedMilliseconds

    let adapt fn hint ls = fn ls

    let trimmers =
        [|
            "Daystate"      , adapt Daystate.trim
            "kaefer"        , adapt kaefer.skipFirstAndLast
            "Petr"          , adapt Petr.trim
            "NonIdiomatic"  , NonIdiomatic.trim
        |]


#if DEBUG
    let functionalTestCases =
        [|
            Functional []               , "empty"       , []
            Functional []               , "singleton"   , [1]
            Functional []               , "duoton"      , [1;2]
            Functional [2]              , "triplet"     , [1;2;3]
            Functional [2;3]            , "quartet"     , [1;2;3;4]
        |]

    let performanceMeasurements = [||]
#else
    let functionalTestCases = [||]

    let performanceMeasurements =
        [|
            "small"   , 10
            "big"     , 1000
            "bigger"  , 100000
//            "huge"    , 10000000
        |] |> Array.map (fun (name, size) -> MeasurePerformance (size, (factor / size))  , name       , [for x in 1..size -> x])
#endif

    let testCases =
        [|
            functionalTestCases
            performanceMeasurements
        |] |> Array.concat


    use tsv = File.CreateText ("result.tsv")

    tsv.WriteLine (sprintf "TRIMMER\tTESTCASE\tSIZE\tHINT\tRUNS\tMEMORY_BEFORE\tMEMORY_AFTER\tGC_TIME\tRUN_TIME")

    for trimName, trim in trimmers do
        for testKind, testCaseName, testCase in testCases do
            match testKind with
            | Functional expected ->
                let actual = trim 0 testCase
                if actual = expected then
                    printfn "SUCCESS: Functional test of %s trim on testcase %s successful" trimName testCaseName
                else
                    printfn "FAILURE: Functional test of %s trim on testcase %s failed" trimName testCaseName
            | MeasurePerformance (size,testRuns) ->

                let hint    = min size maxHint

                let before  = GC.GetTotalMemory(true)

                printfn "MEASURE: Running performance measurement on %s trim using testcase %s..." trimName testCaseName

                let timeMe () =
                    for x in 1..testRuns do
                        ignore <| trim hint testCase
                let _, MilliSeconds ms = time timeMe

                let after   = GC.GetTotalMemory(false)

                let timeGC () =
                    ignore <| GC.GetTotalMemory(true)
                let _, MilliSeconds msGC = time timeMe

                printfn "...%d ms (%d runs), %d (before) %d (after) %d ms (GC)" ms testRuns before after msGC

                tsv.WriteLine (sprintf "%s\t%s\t%d\t%d\t%d\t%d\t%d\t%d\t%d" trimName testCaseName size hint testRuns before after msGC ms)

    0

然后我测量了 x64 上的执行时间和 GC 时间以及允许的最大大小提示：（大小提示仅用于非惯用版本）

x86 和允许的最大尺寸提示：

x64，最多允许 100 个提示：

x86，最多允许 100 个提示：

查看性能图表，我们可以注意到一些令人惊讶的事情：

所有变体都迭代了 10000000 次。人们会期望不同变体之间的执行时间没有差异，但它们确实如此。
硬壳旧 x86 的总体得分始终更高。我不会猜测为什么。
OPs初版虽然看似垃圾但是分数还不错。 List.rev 非常优化可能对它有所帮助（IIRC 它做了一些仅对 F# 开发人员可用的安全作弊）
kaefer 版本虽然在纸面上是一个更好的解决方案，但似乎得分最差。我认为这是因为它分配了额外的基于堆的 State 对象。（这显然不应被理解为对kaefers技能的批评）
非惯用的解决方案在大小提示方面得分很高，但不如我预期的那么好。构建最终列表可能是花费最多周期的事情。也可能是列表上的尾递归函数比 while 循环更有效，因为 IIRC 模式匹配比调用 List.Tail/List.Head/List.IsEmpty
GC 时间几乎和执行时间一样长。
我预计非惯用解决方案的 GC 时间会明显低于其他解决方案。然而，虽然 ResizeArray<_> 可能很快收集到列表对象却不是。
在 x86 arch 上，Petr 解决方案与非惯用解决方案之间的性能差异可能不保证额外的复杂性。

一些最后的想法：

OPs原方案做的不错
垃圾收集需要时间
始终测量...

希望它有点有趣

编辑： GC 性能测量数字不应被过度解释为以下内容："GC can be expensive"

我后来从 while 循环更改为对列表进行尾递归，这确实在一定程度上提高了性能，但不足以保证更新图表。

如何使用 F# 获取没有第一个和最后一个项目的子列表？

How to take sublist without first and last item with F#?

f#

list

sublist