क्यों एक दृश्य इतना इस उदाहरण में

Question

पृष्ठभूमि एक सूची का उपयोग कर की तुलना में धीमी उपयोग कर रहा है: मैं सन्निहित, समय स्टैंप्ड डेटा का एक क्रम है। डेटा-अनुक्रम में इसमें छेद हैं, कुछ बड़े, दूसरों को केवल एक लापता मूल्य है।
जब भी छेद केवल एक गुम मूल्य होता है, तो मैं एक डमी-वैल्यू का उपयोग करके छेद को पैच करना चाहता हूं (बड़े छेद को अनदेखा कर दिया जाएगा)।

मैं समझौता अनुक्रम के आलसी पीढ़ी उपयोग करना चाहते हैं, और मैं इस प्रकार Seq.unfold उपयोग कर रहा हूँ।

मैं डेटा में छेद पैच करने के लिए विधि के दो संस्करण बना दिया है।

पहले यह में छेद के साथ डेटा के अनुक्रम खपत और समझौता अनुक्रम पैदा करता है। यह वही है जो मैं चाहता हूं, लेकिन जब इनपुट अनुक्रम में तत्वों की संख्या 1000 से ऊपर हो जाती है, तो यह विधियां बहुत धीमी गति से चलती हैं, और यह इनपुट अनुक्रम में अधिक तत्वों के क्रमशः खराब हो जाती है।

दूसरी विधि छेद के साथ डेटा की एक सूची खपत और समझौता अनुक्रम पैदा करता है और यह तेजी से चलाता है। हालांकि यह वही नहीं है जो मैं चाहता हूं, क्योंकि यह स्मृति में पूरी इनपुट-सूची का तात्कालिकता को मजबूर करता है। विधि के बजाय (सूची -> अनुक्रम) विधि, एक ही समय में स्मृति में पूरे इनपुट-सूची होने से बचाने के -

मैं (> अनुक्रम अनुक्रम) का उपयोग करना चाहते हैं।

सवाल:

1) क्यों है पहली विधि इतनी धीमी गति से (बड़ा इनपुट सूचियों के साथ उत्तरोत्तर बदतर हो रही) (मैं, पर शक कर रहा हूँ इसे बार-बार Seq.skip 1 के साथ नए दृश्यों बनाने के साथ क्या करना है लेकिन मुझे यकीन है कि नहीं कर रहा हूँ)

2) मैं कैसे, डेटा तेजी में छेद की पैचिंग बनाने के एक इनपुट सूची से अनुक्रम एक इनपुट का उपयोग करते समय बल्कि कर सकते हैं?

कोड:

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 एक नया अनुक्रम निर्माण करती है। मुझे लगता है कि यही कारण है कि आपका मूल दृष्टिकोण धीमा है।

मेरा पहला झुकाव अनुक्रम अभिव्यक्ति और Seq.pairwise का उपयोग करना है। यह पढ़ने के लिए तेज़ और आसान है।

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

किसी भी समय आप एक seq तोड़ Seq.hd का उपयोग करने और Seq.skip 1 आप लगभग निश्चित रूप से हे (एन^2) जा रहा के जाल में गिर रहे हैं। के बाद से इन एल्गोरिदम लगभग हमेशा 'पहला तत्व' और 'तत्वों के शेष' की संरचना है IEnumerable<T>, (जैसे Seq.unfold सहित) पुनरावर्ती एल्गोरिदम के लिए एक भयानक प्रकार है, और वहाँ कोई कारगर तरीका एक नया IEnumerable कि 'शेष का प्रतिनिधित्व करता है बनाने के लिए है तत्वों के '। (IEnumerator<T> काम करने योग्य है, लेकिन इसके एपीआई प्रोग्रामिंग मॉडल के साथ काम करने में इतना मजेदार/आसान नहीं है।)

यदि आपको 'आलसी रहने' के लिए मूल डेटा की आवश्यकता है, तो आपको एक LazyList (F # PowerPack में) का उपयोग करना चाहिए। यदि आपको आलस्य की आवश्यकता नहीं है, तो आपको एक ठोस डेटा प्रकार जैसे 'सूची' का उपयोग करना चाहिए, जिसे आप ओ (1) में 'पूंछ' में डाल सकते हैं।

(आप भी एक FYI करें के रूप में Avoiding stack overflow (with F# infinite sequences of sequences) की जांच करनी चाहिए यह केवल ऊपरी तौर पर इस समस्या के लिए लागू है, हालांकि।)