Как взять подсписку без первого и последнего элемента с F #?

Question

Я отсортирован список целочисленных значений:

let ls = [1..4] 

Как я могу получить подсписок без первого и последнего элемента? (Наиболее оптимальным способом)

Ожидаемый результат: [2; 3].

Это то, что у меня есть до сих пор, и да, это работает, но я, по-моему, это не лучший подход.

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

Answer 1

Это один из способов:

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 2

Для достижения этой цели вам не нужны стандартные библиотечные функции, вы просто просите об эффективном способе. Определение рекурсивной функции с аккумулятором, который содержит промежуточные результаты, тогда станет жизнеспособным решением, даже если список должен быть отменен при его окончании.

Я предоставляю индивидуальный Дискриминационный Союз, чтобы отслеживать состояние, это моделируется по линиям 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 3

Несколько длинный ответ, поступающая в ответ на ваш невинно сформулированный классификаторе: «В наиболее оптимальным образом»

Оптимальное с точки зрения которого?

1. Производительность? (Скорее всего)
2. Производительность, но также и производительность GC?
3. Использование памяти?
4. x86?
5. 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 

Затем я измерил время выполнения и время GC на 64 и максимальном размере намеке позволил: (подсказки размера используются только не- идиоматическая версия)

x86 и максимальный размер намек позволили:

x64 и не более 100 намек позволил:

x86 и не более 100 намек позволил:

Глядя на диаграммах мы можем отметить некоторые несколько удивительные вещи:

1. Все варианты итерации 10000000 раз. Можно было бы ожидать, что время выполнения не будет отличаться между различными вариантами, но они это делают.
2. Жесткие старые оценки x86 последовательно улучшаются в целом. Я не буду рассуждать о том, почему.
3. OPs исходная версия, хотя, казалось бы, расточительные оценки довольно хорошо. Скорее всего, этот список очень оптимизирован (IIRC делает некоторые безопасные мошенники доступными только для разработчиков F #)
4. Версия для кашеров на бумаге лучшего решения кажется наихудшей. Я думаю, это потому, что он выделяет дополнительные объекты State, которые основаны на куче. (Это, очевидно, не должно быть истолковано как критика навыков кеферов)
5. Неидиоматическое решение имеет хорошие оценки с хорошим размером, но не так хорошо, как я ожидал. Возможно, создание финальных списков - это то, что стоит больше всего циклов. Также может быть, что функции хвостовых рекурсивных над списками более эффективны, чем в то время как циклы, поскольку сопоставление образцов IIRC более эффективны, чем вызов List.Tail/List.Head/List.IsEmpty
6. Время GC почти такое же, как время выполнения.
7. Я ожидал, что время GC неидиоматического решения будет значительно ниже остальных. Однако, хотя ResizeArray < _>, вероятно, быстро собирают объекты списка, нет.
8. На х86 арке разница в производительности между решением Petr и неидиоматическим может не гарантировать дополнительной сложности.

Некоторые заключительные мысли:

1. OPs оригинальное решение сделал довольно хорошо
2. Сбор мусора требует времени
3. Всегда измеряйте ...

Надеюсь, это было несколько интересно

Edit: Номера измерения производительности GC не должны быть чрезмерно интерпретированы в какую-то вещь больше, чем: «GC может быть дорогим»

позже я изменился с в то время как цикл для рекурсии хвоста по списку, который несколько улучшил производительность, но недостаточно, чтобы гарантировать обновление диаграмм.