Pourquoi utilise une séquence beaucoup plus lente que d'une liste dans cet exemple

Question

Arrière-plan: I ont une séquence de données contiguës, horodatés. La séquence de données a des trous dans, certains grands, d'autres une seule valeur manquante.
Chaque fois que le trou est juste une seule valeur manquante, je veux les trous à l'aide patcher une valeur factice (des trous plus grands seront ignorés).

Je voudrais utiliser la génération paresseuse de la séquence patché, et je suis donc en utilisant Seq.unfold.

Je l'ai fait deux versions de la méthode pour patcher les trous dans les données.

Le premier consomme la séquence de données avec des trous et produit la séquence corrigée . C'est ce que je veux, mais les méthodes fonctionne horriblement lent lorsque le nombre d'éléments dans la séquence d'entrée dépasse 1000, et il se détériore progressivement les éléments les plus la séquence d'entrée contient.

La seconde méthode consume Liste des données avec des trous et produit la patché séquence et il court vite. Ceci est cependant pas ce que je veux, puisque cela force l'instanciation de l'ensemble des entrées-liste en mémoire.

Je souhaite utiliser la (séquence -> Séquence) Méthode plutôt que la (liste -> séquence). Procédé, pour éviter d'avoir l'ensemble d'entrée-liste en mémoire en même temps

Questions:

1) Pourquoi est la première méthode si lent (devient progressivement pire des listes d'entrée plus grandes) (Je suspecte qu'il a à voir avec la création de nouvelles séquences à plusieurs reprises avec Seq.skip 1, mais je ne suis pas sûr)

2) Comment puis-je faire le rapiéçage des trous dans les données rapide, tout en utilisant une entrée de séquence plutôt que d'une entrée Liste

Le code:

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 construit une nouvelle séquence. Je pense que la raison pour laquelle est votre approche originale est lente.

Ma première inclinaison est d'utiliser une expression de la séquence et Seq.pairwise. C'est rapide et facile à lire.

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

Chaque fois que vous séparez un seq en utilisant Seq.hd et Seq.skip 1 vous tombez presque sûrement dans le piège d'aller O (N ^ 2). IEnumerable<T> est un type terrible pour les algorithmes récursifs (y compris par exemple Seq.unfold), étant donné que ces algorithmes ont presque toujours la structure de « premier élément » et « reste des éléments », et il n'y a aucun moyen efficace de créer une nouvelle IEnumerable qui représente le « reste des éléments. (IEnumerator<T> est réalisable, mais son modèle de programmation API est pas amusant / facile à travailler.)

Si vous avez besoin des données originales à « rester paresseux », alors vous devez utiliser un LazyList (dans le F # PowerPack). Si vous n'avez pas besoin de la paresse, vous devez utiliser un type de données concrètes comme « liste », que vous pouvez « queue » en O (1).

(Vous devriez également consulter éviter un débordement de pile (avec F # séquences infinies de séquences) comme FYI, mais il est qu'accessoirement applicable à ce problème.)