Проблема реализации F # Seq

Question

Я копаюсь в исходном коде F # недавно.

в Seq.fs:

// Binding. 
//
// We use a type defintion to apply a local dynamic optimization. 
// We automatically right-associate binding, i.e. push the continuations to the right.
// That is, bindG (bindG G1 cont1) cont2 --> bindG G1 (cont1 o cont2)
// This makes constructs such as the following linear rather than quadratic:
//
//  let rec rwalk n = { if n > 0 then 
//                         yield! rwalk (n-1)
//                         yield n }

После просмотра кода выше я протестировал два кода:

let rec rwalk n = seq { if n > 0 then 
                         yield n
                         yield! rwalk (n-1)
                      }

и

let rec rwalk n = seq { if n > 0 then 
                         yield! rwalk (n-1)
                         yield n 
                      }

Я обнаружил, что первый очень быстрый, а второй очень медленный.Если n = 10000, на моей машине стоит 3 секунды, чтобы сгенерировать эту последовательность, таким образом, квадратичное время.

Квадратичное время является разумным, например,

seq { yield! {1; 2; ...; n-1}; yield n } переводится в

Seq.append {1; 2; ...; n-1} {n}

Эта операция добавления, как я полагаю, должна занимать линейное время.В первом коде операция добавления выглядит следующим образом: seq { yield n; yield! {n-1; n-2; ...; 1} }, что стоит постоянного времени.

Комментарии в коде говорят, что это linear (возможно, это линейное не линейное время).Возможно, это linear относится к использованию настраиваемой реализации для последовательности, а не к вычислительному выражению Moand / F # (как упомянуто в спецификации F #, однако в спецификации не указывается причина для этого ...).

Может кто-нибудь прояснить здесь нечеткость?Большое спасибо!

(ps, поскольку это проблема дизайна и оптимизации языка, я также прикрепил тег Haskell, чтобы увидеть, есть ли у людей понимание.)

Answer 1

Когда yield! появляется в позиции не-хвостового вызова , это означает то же самое, что и:

for v in <expr> do yield v

Проблема с этим (и причина, почемуэто квадратичное значение), то есть для рекурсивных вызовов это создает цепочку итераторов с вложенными циклами for.Вам необходимо выполнить итерацию по всей последовательности, сгенерированной <expr> для каждого отдельного элемента, поэтому, если итерация линейная, вы получите квадратичное время (потому что линейная итерация происходит для каждого элемента).

Допустим, функция rwalk генерирует [ 9; 2; 3; 7 ].На первой итерации рекурсивно сгенерированная последовательность имеет 4 элемента, поэтому вы должны выполнить итерацию по 4 элементам и добавить 1. В рекурсивном вызове вы должны выполнить итерацию по 3 элементам и добавить 1 и т. Д. Используя диаграмму, вы можетепосмотрите, как это квадратично:

x
x x 
x x x
x x x x

Кроме того, каждый из рекурсивных вызовов создает новый экземпляр объекта (IEnumerator), поэтому также существует некоторая стоимость памяти (хотя и только линейная).

В положении хвостового вызова компилятор / librar F # выполняет оптимизацию.Он «заменяет» текущий IEnumerable на тот, который был возвращен рекурсивным вызовом, поэтому ему не нужно перебирать его слишком много, чтобы сгенерировать все элементы - он просто возвращается (и это также уменьшает стоимость памяти).

Related. Та же проблема обсуждалась в дизайне языка C # и есть интересная статья об этом (их название для yield! - yield foreach).

Answer 2

Я не уверен, какой ответ ты ищешь.Как вы заметили, комментарий не соответствует поведению компилятора.Я не могу сказать, является ли это комментарием, не синхронизированным с реализацией, или это действительно ошибка производительности (например, спецификация, кажется, не вызывает каких-либо особых требований к производительности).

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

open System.Collections
open System.Collections.Generic

type 'a nestedState = 
/// Nothing to yield
| Done 
/// Yield a single value before proceeding
| Val of 'a
/// Yield the results from a nested iterator before proceeding
| Enum of (unit -> 'a nestedState)
/// Yield just the results from a nested iterator
| Tail of (unit -> 'a nestedState)

type nestedSeq<'a>(ntor) =
  let getEnumerator() : IEnumerator<'a> =
    let stack = ref [ntor]
    let curr = ref Unchecked.defaultof<'a>
    let rec moveNext() =
      match !stack with
      | [] -> false
      | e::es as l -> 
          match e() with
          | Done -> stack := es; moveNext()  
          | Val(a) -> curr := a; true
          | Enum(e) -> stack := e :: l; moveNext()
          | Tail(e) -> stack := e :: es; moveNext()
    { new IEnumerator<'a> with
        member x.Current = !curr
      interface System.IDisposable with
        member x.Dispose() = () 
      interface IEnumerator with
        member x.MoveNext() = moveNext()
        member x.Current = box !curr
        member x.Reset() = failwith "Reset not supported" }
  member x.NestedEnumerator = ntor
  interface IEnumerable<'a> with
    member x.GetEnumerator() = getEnumerator()
  interface IEnumerable with
    member x.GetEnumerator() = upcast getEnumerator()

let getNestedEnumerator : 'a seq -> _ = function
| :? ('a nestedSeq) as n -> n.NestedEnumerator
| s -> 
    let e = s.GetEnumerator()
    fun () ->
      if e.MoveNext() then
        Val e.Current
      else
        Done

let states (arr : Lazy<_[]>) = 
  let state = ref -1 
  nestedSeq (fun () -> incr state; arr.Value.[!state]) :> seq<_>

type SeqBuilder() = 
  member s.Yield(x) =  
    states (lazy [| Val x; Done |])
  member s.Combine(x:'a seq, y:'a seq) = 
    states (lazy [| Enum (getNestedEnumerator x); Tail (getNestedEnumerator y) |])
  member s.Zero() =  
    states (lazy [| Done |])
  member s.Delay(f) = 
    states (lazy [| Tail (f() |> getNestedEnumerator) |])
  member s.YieldFrom(x) = x 
  member s.Bind(x:'a seq, f) = 
    let e = x.GetEnumerator() 
    nestedSeq (fun () -> 
                 if e.MoveNext() then  
                   Enum (f e.Current |> getNestedEnumerator) 
                 else  
                   Done) :> seq<_>

let seq = SeqBuilder()

let rec walkr n = seq { 
  if n > 0 then
    return! walkr (n-1)
    return n
}

let rec walkl n = seq {
  if n > 0 then
    return n
    return! walkl (n-1)
}

let time = 
  let watch = System.Diagnostics.Stopwatch.StartNew()
  walkr 10000 |> Seq.iter ignore
  watch.Stop()
  watch.Elapsed

Обратите внимание, что мой SeqBuilder не устойчив;в нем отсутствуют несколько элементов рабочего процесса, и он ничего не делает для удаления объектов или обработки ошибок.Тем не менее, он демонстрирует, что SequenceBuilder s не требуется для показа квадратичного времени выполнения на примерах, подобных вашему.

Также обратите внимание, что здесь есть компромисс между временем и пространством - вложенный итераторwalkr n будет выполнять итерацию последовательности за время O (n), но для этого требуется пространство O (n).