Почему использование последовательности намного медленнее, чем использование списка в этом примере

Question

Справочная информация: У меня есть последовательность непрерывных данных с отметкой времени. В последовательности данных есть дыры, некоторые большие, другие просто одно пропущенное значение.
Всякий раз, когда отверстие представляет собой единственное пропущенное значение, я хочу исправить отверстия, используя фиктивное значение (более крупные отверстия будут игнорироваться).

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

Я сделал две версии метода для исправления дыр в данных.

Первый использует последовательность данных с дырками и создает исправленную последовательность . Это то, что я хочу, но методы работают ужасно медленно, когда число элементов во входной последовательности становится больше 1000, и это становится все хуже, чем больше элементов содержит входная последовательность.

Второй метод использует список данных с дырками и создает исправленную последовательность , и он работает быстро. Это, однако, не то, что я хочу, так как это вызывает создание экземпляра всего списка ввода в памяти.

Я бы хотел использовать метод (sequence -> sequence), а не метод (list -> sequence), чтобы избежать одновременного хранения всего входного списка в памяти.

Вопросы:

1) Почему первый метод такой медленный (прогрессивно ухудшается с большими входными списками) (Я подозреваю, что это связано с повторным созданием новых последовательностей с Seq.skip 1, но я не уверен)

2) Как я могу сделать быстрое исправление дыр в данных, используя вход sequence вместо ввода list ?

код:

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()))

Answer 1

Каждый раз, когда вы разбиваете секвенцию, используя Seq.hd и Seq.skip 1, вы почти наверняка попадете в ловушку идущего О (N ^ 2). IEnumerable<T> - ужасный тип для рекурсивных алгоритмов (включая, например, Seq.unfold), так как эти алгоритмы почти всегда имеют структуру «первый элемент» и «остаток элементов», и не существует эффективного способа создания нового IEnumerable который представляет «остаток элементов». (IEnumerator<T> работоспособен, но с его моделью программирования API не так весело / легко работать.)

Если вам нужны исходные данные, чтобы «оставаться ленивыми», вам следует использовать LazyList (в F # PowerPack). Если вам не нужна лень, то вам следует использовать конкретный тип данных, такой как «список», который вы можете «хвостить» в O (1).

(Вы также должны проверить Предотвращение переполнения стека (с F # бесконечными последовательностями последовательностей) в качестве FYI, хотя это только косвенно применимо к этой проблеме.)

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
  }