Почему это выражение последовательности F # cubi c time вместо линейного?

Question

Я наткнулся на странное поведение сложности времени при использовании Seq.unfold. Вот минимальный случай, который я мог бы придумать, чтобы воспроизвести это.

let idUnfolder sequence =
   sequence
   |> Seq.tryHead
   |> Option.map (fun head -> (head, Seq.tail sequence))

let seqIdWithUnfold sequence =
   Seq.unfold idUnfolder sequence

Функция seqIdWithUnfold сама возвращает данную последовательность. Я ожидаю, что результирующая последовательность будет повторяться в линейном времени, так как Seq.unfold - это O (n), Seq.tryHead и Seq.tail - это O (1) (поправьте меня, если я ошибаюсь). Однако, несмотря на все мои знания, он имеет кубическую сложность c.

Я проверил время выполнения с помощью следующей функции с набором значений n.

let test n =
   let start = System.DateTime.Now
   Seq.init n id
   |> seqIdWithUnfold
   |> Seq.iter ignore
   let duration = System.DateTime.Now - start
   printfn "%f" duration.TotalSeconds

Что делает эту операцию сложностью c?

Answer 1

seq почти всегда O(n). A seq aka IEnumerable<T> по существу:

type Enumerator<'a> = {
    getNext : unit -> 'a option
}

type Seq<'a> = {
    getEnumerator: unit -> Enumerator<'a>
}

Каждый раз, когда вы оцениваете последовательность, создается новый Enumerator, который фиксирует состояние перечисления. Затем постоянно вызывается getNext, пока последовательность не завершится.

Вы можете убедиться в этом сами, если в любой момент заменить seq на

source |> Seq.map(fun x -> printfn "Eval %A" x; x)

Давайте покажем вызовы на getEnumerator, а также:

let sq  = 
    seq {  
        let mutable ctr = 0
        do printfn "Init  _" 
        while true do
            ctr <- ctr + 1
            printfn "Yield %d" ctr
            yield ctr
        }     

seqIdWithUnfold (sq |> Seq.take 3) |> Seq.toList |> printfn "%A"

И есть вывод:

Init  _
Yield 1
Init  _
Yield 1
Yield 2
Init  _
Yield 1
Yield 2
Yield 3
Init  _
Yield 1
Yield 2
Yield 3
[1; 2; 3]

Здесь показан шаблон classi c n(n+1)/2.

You можно увидеть, что сложность будет содержать n + n ² членов.

Если вы можете использовать список, вы получите O(n) вместо O(n^2).

Если вы действительно хотите O(1), используйте массивы.

Answer 2

Как отметил в комментариях Филипп Картер Seq.tail - это O (n).

Я не уверен, почему список F # будет неприемлемым, списки F # являются односвязными списками, поэтому вы можете получить константу хвост времени. Если вам нужно принять какую-либо последовательность в качестве своей подписи, просто преобразуйте ее в List перед развертыванием, это все равно делает его O (n). Этот пример, который вы представили, не может быть ленивым, если вам действительно не нужен хвост.

let seqIdWithUnfold sequence =
       sequence
           |> Seq.toList
           |> List.unfold idUnfolder 
           |> List.toSeq

Ваш пример обработки по-прежнему работает с модулем List

 let idUnfolder listSeq =
        listSeq
        |> List.tryHead
        |> Option.map (fun head -> (head, List.tail listSeq))

Но я думаю, он будет выглядеть немного чище, если

let idUnfolder =
    function | [] -> None
             | h::t -> Some(h, t);

Benchamarks

|          Method |        Mean |     Error |    StdDev |
|---------------- |------------:|----------:|----------:|
|        Original | 4,683.88 us | 36.462 us | 34.106 us |
|  ListConversion |    15.63 us |  0.202 us |  0.179 us |

// * Hints *
Outliers
  Benchmarkem.ListConversion: Default -> 1 outlier  was  removed (16.53 us)

// * Legends *
  Mean   : Arithmetic mean of all measurements
  Error  : Half of 99.9% confidence interval
  StdDev : Standard deviation of all measurements
  1 us   : 1 Microsecond (0.000001 sec)