Perché in questo esempio si utilizza una sequenza molto più lenta dell'utilizzo di un elenco

Question

Contesto: Ho una sequenza di dati contigui e con data e ora. La sequenza di dati presenta dei buchi, alcuni grandi, altri solo un singolo valore mancante.
Ogni volta che il foro è solo un singolo valore mancante, voglio applicare una patch ai buchi usando un valore fittizio (i fori più grandi saranno ignorati).

Mi piacerebbe utilizzare la generazione lenta della sequenza patchata e sto quindi utilizzando Seq.unfold.

Ho creato due versioni del metodo per correggere i buchi nei dati.

consuma La prima sequenza dei dati forata e produce la patch sequenza. Questo è quello che voglio, ma i metodi sono orribilmente lenti quando il numero di elementi nella sequenza di input supera 1000 e peggiora progressivamente più elementi contiene la sequenza di input.

Il secondo metodo consuma una elenco dei dati con fori e produce la patch sequenza e corre veloce. Questo tuttavia non è ciò che voglio, poiché ciò impone l'istanziazione dell'intero elenco di input in memoria.

Vorrei utilizzare il metodo (sequenza -> sequenza) piuttosto che il metodo (lista -> sequenza), per evitare di avere contemporaneamente l'intera lista di input in memoria.

Domande:

1) Perché è il primo metodo in modo lento (progressivamente sempre peggio con liste di input più grandi) (sto sospettando che ha a che fare con la creazione di nuove sequenze più volte con Seq.skip 1, ma io non sono sicuro)

2) Come posso fare il patching dei fori nei dati veloci, mentre si utilizza un ingresso sequenza piuttosto che un ingresso lista?

Il codice:

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 costruisce una nuova sequenza. Penso che sia il motivo per cui il tuo approccio originale è lento.

La mia prima inclinazione è usare un'espressione di sequenza e Seq.pairwise. Questo è veloce e facile da leggere.

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

Ogni volta che si rompe a parte un ss utilizzando Seq.hd e Seq.skip 1 si è quasi sicuramente cadere nella trappola di andare O (N^2). IEnumerable<T> è un tipo terribile per gli algoritmi ricorsivi (incluso ad esempio Seq.unfold), poiché questi algoritmi hanno quasi sempre la struttura di "primo elemento" e "resto di elementi" e non esiste un modo efficiente per creare un nuovo IEnumerable che rappresenta il resto di elementi '. (IEnumerator<T> è praticabile, ma il suo modello di programmazione API non è così divertente/facile da usare.)

Se i dati originali sono "pigri", è necessario utilizzare LazyList (nel F # PowerPack). Se non hai bisogno della pigrizia, allora dovresti usare un tipo di dati concreto come 'lista', che puoi 'inserire' in O (1).

(Si dovrebbe anche controllare Avoiding stack overflow (with F# infinite sequences of sequences) come un FYI, se è solo tangenzialmente applicabile a questo problema.)