为什么在这个例子中使用序列比使用列表要慢得多？

Question

背景: 我有一串连续的时间戳数据。 这个数据序列中有一些缺口，有些很大，有些只是一个缺失的值。
每当出现仅有一个缺失值的缺口时，我希望用一个虚拟值来填补这个缺口（将忽略更大的缺口）。

我想要使用懒生成的方法来生成修补后的序列，因此我使用了Seq.unfold。

我制作了两个版本的修补数据方法。

第一个消耗具有间隙数据的序列并生成修补后的序列。 这正是我想要的，但是当输入序列中的元素数量上升到1000以上时，该方法运行得非常缓慢，并且随着输入序列包含的元素越来越多，情况会变得越来越糟糕。

第二个方法消耗一个带缺口数据的列表并生成修补后的序列，它运行速度很快。但这不是我想要的，因为这会强制在内存中实例化整个输入列表。

我希望使用(序列-> 序列)方法而不是(list -> 序列)方法，以避免同时将整个输入列表存储在内存中。

问题：

1) 为什么第一个方法如此缓慢（随着更大的输入列表而逐渐变得越来越糟） （我怀疑这与不断使用Seq.skip 1来创建新序列有关，但我不确定）

2) 如何在使用输入序列而不是输入列表的情况下快速修补数据中的缺口？

代码:

open System

// Method 1 (Slow)
let insertDummyValuesWhereASingleValueIsMissing1 (timeBetweenContiguousValues : TimeSpan) (values : seq<(DateTime * float)>) =
    let sizeOfHolesToPatch = timeBetweenContiguousValues.Add timeBetweenContiguousValues // Only insert dummy-values when the gap is twice the normal
    (None, values) |> Seq.unfold (fun (prevValue, restOfValues) ->  
        if restOfValues |> Seq.isEmpty then
            None // Reached the end of the input seq
        else
            let currentValue = Seq.hd restOfValues
            if prevValue.IsNone then
                Some(currentValue, (Some(currentValue), Seq.skip 1 restOfValues  )) // Only happens to the first item in the seq
            else
                let currentTime = fst currentValue
                let prevTime = fst prevValue.Value
                let timeDiffBetweenPrevAndCurrentValue = currentTime.Subtract(prevTime)
                if timeDiffBetweenPrevAndCurrentValue = sizeOfHolesToPatch then
                    let dummyValue = (prevTime.Add timeBetweenContiguousValues, 42.0) // 42 is chosen here for obvious reasons, making this comment superfluous
                    Some(dummyValue, (Some(dummyValue), restOfValues))
                else
                    Some(currentValue, (Some(currentValue), Seq.skip 1 restOfValues))) // Either the two values were contiguous, or the gap between them was too large to patch

// Method 2 (Fast)
let insertDummyValuesWhereASingleValueIsMissing2 (timeBetweenContiguousValues : TimeSpan) (values : (DateTime * float) list) =
    let sizeOfHolesToPatch = timeBetweenContiguousValues.Add timeBetweenContiguousValues // Only insert dummy-values when the gap is twice the normal
    (None, values) |> Seq.unfold (fun (prevValue, restOfValues) ->  
        match restOfValues with
        | [] -> None // Reached the end of the input list
        | currentValue::restOfValues -> 
            if prevValue.IsNone then
                Some(currentValue, (Some(currentValue), restOfValues  )) // Only happens to the first item in the list
            else
                let currentTime = fst currentValue
                let prevTime = fst prevValue.Value
                let timeDiffBetweenPrevAndCurrentValue = currentTime.Subtract(prevTime)
                if timeDiffBetweenPrevAndCurrentValue = sizeOfHolesToPatch then
                    let dummyValue = (prevTime.Add timeBetweenContiguousValues, 42.0) 
                    Some(dummyValue, (Some(dummyValue), currentValue::restOfValues))
                else
                    Some(currentValue, (Some(currentValue), restOfValues))) // Either the two values were contiguous, or the gap between them was too large to patch

// Test data
let numbers = {1.0..10000.0}
let contiguousTimeStamps = seq { for n in numbers -> DateTime.Now.AddMinutes(n)}

let dataWithOccationalHoles = Seq.zip contiguousTimeStamps numbers |> Seq.filter (fun (dateTime, num) -> num % 77.0 <> 0.0) // Has a gap in the data every 77 items

let timeBetweenContiguousValues = (new TimeSpan(0,1,0))

// The fast sequence-patching (method 2)
dataWithOccationalHoles |> List.of_seq |> insertDummyValuesWhereASingleValueIsMissing2 timeBetweenContiguousValues |> Seq.iter (fun pair -> printfn "%f %s" (snd pair) ((fst pair).ToString()))

// The SLOOOOOOW sequence-patching (method 1)
dataWithOccationalHoles |> insertDummyValuesWhereASingleValueIsMissing1 timeBetweenContiguousValues |> Seq.iter (fun pair -> printfn "%f %s" (snd pair) ((fst pair).ToString()))

- Treefrog

Answer 1

每当您使用Seq.hd和Seq.skip 1分解序列时，几乎肯定会陷入O（N ^ 2）的陷阱中。 对于递归算法（包括例如Seq.unfold），IEnumerable<T> 是一个糟糕的类型，因为这些算法几乎总是具有“第一个元素”和“其余元素”的结构，并且没有有效的方法创建代表“其余元素”的新IEnumerable。（IEnumerator<T>可行，但其API编程模型不太好/容易处理。）

如果需要原始数据保持“惰性”，则应使用LazyList（在F＃ PowerPack中）。 如果不需要惰性，则应使用像“list”这样的具体数据类型，可以以O（1）的时间进行“尾部”操作。

（您还应该查看避免使用F#无限序列时出现堆栈溢出问题作为FYI，尽管它仅与此问题有关联。）

- Brian

---

Brian，我是否正确理解您的意思，即从现有的序列创建新序列（例如，let seq2 = Seq.skip 1 seq1）的过程是一项昂贵的操作？ （我原本以为它是O（1）） 如果这很昂贵，那为什么呢？ （我印象中序列只在需要时才被评估？） - Treefrog

构建这个序列实际上很快：O(1)。但是，评估它的第一个元素意味着创建原始序列的枚举器，计算其第一个值，丢弃该值，计算下一个值，然后产生该值。因此，两个“Seq.skip 1”生成一个序列，当求值时将：创建内部元素的枚举器，该枚举器创建原始序列的枚举器，计算第一个值，将其丢弃，将下一个值传递给内部元素，内部元素然后将其丢弃，计算一个更多的值，并产生该值。每个嵌套的 Seq.skip 1 都会增加更多的工作，导致时间和空间复杂度为 O(N)。 - Brian

谢谢您抽出时间回复，Brian！ - Treefrog

这就解释了为什么 F# 提供了 Seq.head 函数，但没有提供 Seq.tail 函数。 - Stephen Hosking

Answer 2

Seq.skip构建了一个新的序列。我认为这就是你最初的方法缓慢的原因。

我的第一反应是使用序列表达式和Seq.pairwise。这种方法快速而且易于阅读。

let insertDummyValuesWhereASingleValueIsMissingSeq (timeBetweenContiguousValues : TimeSpan) (values : seq<(DateTime * float)>) =
  let sizeOfHolesToPatch = timeBetweenContiguousValues.Add timeBetweenContiguousValues // Only insert dummy-values when the gap is twice the normal
  seq {
    yield Seq.hd values
    for ((prevTime, _), ((currentTime, _) as next)) in Seq.pairwise values do
      let timeDiffBetweenPrevAndCurrentValue = currentTime.Subtract(prevTime)
      if timeDiffBetweenPrevAndCurrentValue = sizeOfHolesToPatch then
        let dummyValue = (prevTime.Add timeBetweenContiguousValues, 42.0) // 42 is chosen here for obvious reasons, making this comment superfluous
        yield dummyValue
      yield next
  }

- Jason

---

在学习 F# 的时候，我通过消除所有命令式构造进入了函数式编程的状态。我发现使用 Seq.unfold 比起无限简单的“循环和可变引用”方法，我的代码可读性急剧下降。 - Juliet

Jason，这就是我一直在寻找的解决方案。当我编写这个方法时，我的最初倾向是使用yield（我来自C#背景），但由于我没有F#书籍（等待唐·西姆的12月份发布），我无法弄清楚F#如何使用yield，因此我选择了Seq.unfold。 - Treefrog

@TreeFrog。更好的是，F#有yield!，这是我一直希望添加到C#中的yield foreach。 - ShuggyCoUk

@ShuggyCoUk。谢谢你告诉我，Shuggy。我会研究一下“yield！” - Treefrog

@Jason：“Seq.skip构造一个新序列” - 查看实现（通过Reflector），这似乎并不是事实。 Seq.skip返回的迭代器封装了传递的迭代器，尽管已经迭代了一些元素。没有复制序列。 - Richard