Por que está usando uma sequência muito mais lenta do que usar uma lista neste exemplo
-
19-09-2019 - |
Pergunta
Antecedentes: Eu tenho uma sequência de dados contíguos e estampados no tempo. A sequência de dados tem orifícios, alguns grandes, outros apenas um único valor ausente.
Sempre que o orifício é apenas um único valor ausente, quero corrigir os orifícios usando um valor dummy (orifícios maiores serão ignorados).
Eu gostaria de usar geração preguiçosa da sequência corrigida e, assim, estou usando o seq.unfold.
Fiz duas versões do método para corrigir os orifícios nos dados.
O primeiro consome o seqüência de dados com orifícios e produz o remendado seqüência. É isso que eu quero, mas os métodos são terrivelmente lentos quando o número de elementos na sequência de entrada aumenta acima de 1000 e fica progressivamente pior quanto mais elementos a sequência de entrada contém.
O segundo método consome um Lista dos dados com buracos e produz o remendado seqüência E funciona rápido. No entanto, isso não é o que eu quero, já que isso força a instanciação de toda a lista de entrada na memória.
Eu gostaria de usar o método (sequência -> sequência) em vez do método (LIST -> Sequence), para evitar ter toda a lista de entrada na memória ao mesmo tempo.
Perguntas:
1) Por que o primeiro método é tão lento (ficando progressivamente pior com listas de entrada maiores) (suspeito que isso tenha a ver com a criação repetidamente de novas sequências com seq.skip 1, mas não tenho certeza)
2) Como posso fazer o patch de orifícios nos dados rapidamente, enquanto estiver usando uma entrada seqüência Em vez de uma entrada Lista?
O 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()))
Solução
Seq.skip constrói uma nova sequência. Eu acho que é por isso que sua abordagem original é lenta.
Minha primeira inclinação é usar uma expressão de sequência e seq.pairwise. Isso é rápido e fácil de ler.
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
}
Outras dicas
Sempre que você separa uma seq usando Seq.hd
e Seq.skip 1
Você está quase certamente caindo na armadilha de ir o (n^2). IEnumerable<T>
é um tipo horrível para algoritmos recursivos (incluindo por exemplo Seq.unfold
), como esses algoritmos quase sempre têm a estrutura de 'primeiro elemento' e 'restante de elementos', e não há uma maneira eficiente de criar um novo IEnumerable
Isso representa o 'restante dos elementos'. (IEnumerator<T>
é viável, mas seu modelo de programação de API não é tão divertido/fácil de trabalhar.)
Se você precisar dos dados originais para 'ficar preguiçoso', use um lazylist (no PowerPack F#). Se você não precisar da preguiça, use um tipo de dados concreto, como 'Lista', no qual você pode 'fazer' em O (1).
(Você também deve conferir Evitando o transbordamento da pilha (com sequências infinitas de F#) Como FYI, embora seja apenas tangencialmente aplicável a esse problema.)