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

Question

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

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

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

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

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

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

Вопросы:

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

Answer 1

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 
    } 

Answer 2

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

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

(Вы должны также проверить Avoiding stack overflow (with F# infinite sequences of sequences) как FYI, хотя это лишь косвенно относится к этой проблеме.)