Подтвердить что ты не робот

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

Я недавно врывался в исходный код 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 #, однако в спецификации не упоминается причина для этого...).

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

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

4b9b3361

ОТВЕТЫ

Ответ 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), поэтому также существует некоторая стоимость памяти (хотя и линейная).

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

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

Ответ 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 не нужно показывать квадратичное время работы на примерах, подобных вашим.

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