¿Por qué usar una secuencia mucho más lenta que utilizando una lista en este ejemplo?

Question

Antecedentes: Tengo una secuencia de datos contiguos con sello de tiempo. La secuencia de datos tiene agujeros, algunos grandes, otros solo un valor perdido.
Cuando el agujero tiene un solo valor faltante, quiero parchar los agujeros usando un valor ficticio (se ignorarán los agujeros más grandes).

Me gustaría utilizar la generación diferida de la secuencia de parches, y estoy usando Seq.unfold.

He hecho dos versiones del método para parchear los agujeros en los datos.

El primero consume la secuencia de datos con agujeros en él y produce el parcheado secuencia. Esto es lo que quiero, pero los métodos funcionan terriblemente lento cuando el número de elementos en la secuencia de entrada se eleva por encima de 1000, y empeora progresivamente cuanto más elementos contiene la secuencia de entrada.

El segundo método consume una lista de los datos con agujeros y produce el parcheado secuencia y su ejecución es rápida. Sin embargo, esto no es lo que quiero, ya que esto obliga a la creación de instancias de toda la lista de entrada en la memoria.

Me gustaría utilizar el método (secuencia -> secuencia) en lugar del método (lista -> secuencia), para evitar tener toda la lista de entrada en la memoria al mismo tiempo.

Preguntas:

1) ¿Por qué es el primer método tan lento (empeorando progresivamente con listas de entrada más grandes) (Estoy sospechando que tiene que ver con la creación repetidamente nuevas secuencias con Seq.skip 1, pero no estoy seguro)

2) ¿Cómo puedo hacer que la aplicación de parches de agujeros en los datos rápidas, mientras que el uso de una entrada secuencia en lugar de una entrada lista?

El código:

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 construye una nueva secuencia. Creo que es por eso que su enfoque original es lento.

Mi primera inclinación es usar una expresión de secuencia y Seq.pairwise. Esto es rápido y fácil de leer.

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

Cada vez que se separa un ss utilizando Seq.hd y Seq.skip 1 que está casi seguro de caer en la trampa de ir O (n^2). IEnumerable<T> es un tipo horrible para los algoritmos recursivos (incluyendo eg Seq.unfold), ya que estos algoritmos casi siempre tienen la estructura de 'primer elemento' y 'resto de elementos', y no hay manera eficiente de crear un nuevo IEnumerable que represente el 'resto de elementos '. (IEnumerator<T> es factible, pero su modelo de programación API no es tan divertido/fácil de usar.)

Si necesita los datos originales para 'permanecer flojo', entonces debe usar un LazyList (en el PowerPack F #). Si no necesita la pereza, debe usar un tipo concreto de datos como 'list', que puede 'alinear' en O (1).

(También debe comprobar fuera de Avoiding stack overflow (with F# infinite sequences of sequences) como un FYI, aunque es sólo tangencialmente aplicable a este problema.)