performance - tamaño - recorrer lista python

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

Question

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

Me gustaría usar la generación perezosa de la secuencia parcheada, y así estoy usando Seq.unfold.

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

El primero consume la secuencia de datos con agujeros y produce la secuencia parcheada. Esto es lo que quiero, pero los métodos son terriblemente lentos cuando el número de elementos en la secuencia de entrada supera los 1000 y empeora progresivamente a medida que más elementos contiene la secuencia de entrada.

El segundo método consume una lista de los datos con agujeros y produce la secuencia parcheada y se ejecuta rápidamente. Sin embargo, esto no es lo que quiero, ya que esto fuerza la creación de instancias de toda la lista de entrada en la memoria.

Me gustaría usar 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é el primer método es tan lento (empeora progresivamente con las listas de entrada más grandes)? (Sospecho que tiene que ver con la creación repetida de nuevas secuencias con Seq.skip 1, pero no estoy seguro)

2) ¿Cómo puedo hacer el parcheo de agujeros en los datos rápidamente, mientras uso una secuencia de entrada en lugar de una lista de entrada?

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

Cada vez que separa una Seq.hd con Seq.hd y Seq.skip 1 , seguramente Seq.skip 1 en la trampa de ir O (N ^ 2). IEnumerable<T> es un tipo horrible para los algoritmos recursivos (incluido, por ejemplo, Seq.unfold ), ya que estos algoritmos casi siempre tienen la estructura de ''primer elemento'' y ''resto de elementos'', y no hay una forma eficiente de crear un nuevo IEnumerable que representa el ''resto de elementos''. ( IEnumerator<T> es viable, pero su modelo de programación API no es tan divertido / fácil de trabajar).

Si necesita que los datos originales se mantengan perezosos, debe usar un LazyList (en el F # PowerPack). Si no necesita la pereza, entonces debe usar un tipo de datos concreto como "lista", al que puede "seguir" en O (1).

(También debe consultar Evitar el desbordamiento de pila (con F # secuencias de secuencias infinitas) como un FYI, aunque solo es aplicable tangencialmente a este problema).

Answer 2

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
  }