Bu örnekte neden bir diziyi kullanmaktan çok daha yavaş kullanıyorsunuz

Question

Arka plan: Bir dizi bitişik, zaman damgalı veriye sahibim. Veri dizisinde, içinde delikler, bazıları büyük, diğerleri sadece tek bir eksik değer var.
Delik sadece tek bir eksik değer olduğunda, delikleri bir taklit değeriyle yamalamak istiyorum (daha büyük delikler dikkate alınmayacaktır).

Yamalı dizinin tembel neslini kullanmak istiyorum ve bu nedenle Seq.unfold kullanıyorum.

Verilerin deliklerini yamalamak için iki yöntem sürümü yaptım.

ilk olarak içinde delikler olan veri dizisini tüketir ve yamalı sekansı üretir. İstediğim şey buydu, ama giriş dizisindeki elemanların sayısı 1000'in üzerine çıktığında, yöntemler korkunç bir şekilde yavaşlar ve giriş dizisinin içerdiği daha fazla elementi gittikçe daha da kötüleştirir.

ikinci yöntem, delikli bir veri listesini tüketir ve yamalı sekansı üretir ve hızlı çalışır. Ancak bu, istediğim şey değil, çünkü bu, tüm giriş listesinin belleğe alınmasını zorlar.

Tüm giriş listesini aynı anda bellekte bulundurmaktan kaçınmak için (liste -> sıra) yöntemi yerine (dizi -> dizi) yöntemini kullanmak istiyorum.

Sorular:

1) Neden ilk yöntem (Ben, bu art arda Seq.skip 1 ile yeni dizileri oluştururken ile ilgisi var şüphelenen) büyük girdi listeleri ile giderek kötüleşiyor (çok yavaş ama Ben bir giriş kullanırken dizisi ziyade bir giriş listeye daha

2) Nasıl hızlı veri deliklerin yama yapabilirsiniz) emin değilim?

kodu:

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 yeni dizisi oluşturur. Bence bu, orijinal yaklaşımınızın yavaş olmasının nedeni.

İlk eğim, sıralı bir ifade ve Sıralı olarak kullanmaktır. Bu hızlı ve okunması kolay.

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

bir seq parçalanmak herhangi bir zaman Seq.hd kullanarak Seq.skip 1 neredeyse mutlaka O (N^2) olacak tuzağına düşer. IEnumerable<T>, yinelemeli algoritmalar için korkunç bir türdür (örneğin, Seq.unfold), çünkü bu algoritmalar hemen hemen her zaman 'birinci öğe' ve 'öğelerin geri kalanı' yapısına sahiptir ve kalanını temsil eden yeni bir IEnumerable oluşturmak için etkili bir yol yoktur. elemanların (IEnumerator<T> uygulanabilir, ancak API programlama modeli ile çalışmak çok kolay değil.)

Orijinal verileri 'tembel kalmak' için gerekiyorsa, o zaman bir LazyList kullanmalısınız (F # PowerPack'de). Tembelliğe ihtiyacınız yoksa, O (1) 'in içine girebileceğiniz' liste 'gibi somut bir veri türü kullanmalısınız.

(Bu sadece yüzeysel bu soruna uygulanabilir olsa da, bir Bilginize olarak Avoiding stack overflow (with F# infinite sequences of sequences) kontrol etmeliyiz.)