代码之家 › 专栏 › 技术社区 › Yin Zhu

F#Seq的一个实现问题

functional-programming f# haskell .net

Yin Zhu · 技术社区 · 14 年前

我最近在研究F#源代码。

在序列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}

我想这个附加操作需要线性时间。在第一段代码中,append操作如下: seq { yield n; yield! {n-1; n-2; ...; 1} } ,这需要固定的时间。

代码中的注释表明 linear (也许这个线性时间不是线性时间)。也许这个 线性的 与对序列而不是Moand/F计算表达式使用自定义实现有关(如F#规范中所述,但规范中未提及这样做的原因…)。

有谁能澄清这里的模糊性吗?谢谢!

(p.s.因为这是一个语言设计和优化问题,我还附加了Haskell标记以查看那里的人是否有见解。)

2 回复 | 直到 14 年前

Tomas Petricek 14 年前

什么时候? 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 使用递归调用返回的元素,因此不需要遍历它来生成所有元素—只需返回它(这也消除了内存开销)。

相关的。 同样的问题也在平面设计中讨论过 interesting paper about it (他们的名字是 投降! 是 yield foreach ).

kvb 13 年前

我不知道你在找什么样的答案。如您所注意到的,注释与编译器的行为不匹配。我不能说这是一个注释与实现不同步的实例,还是它实际上是一个性能缺陷(例如,规范似乎没有提出任何特定的性能要求)。

但是,理论上编译器的机器应该可以生成一个在线性时间内对示例进行操作的实现。实际上,甚至可以使用计算表达式在库中构建这样的实现。下面是一个粗略的例子,主要基于托马斯引用的论文:

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)空间来执行此操作。