हास्केल

Question

में एक कुशल फिसलने खिड़की एल्गोरिथ्म को लागू करने मैं हास्केल में एक कुशल फिसलने खिड़की समारोह की जरूरत है, तो मैं निम्नलिखित लिखा है:

windows n xz@(x:xs) 
    | length v < n = [] 
    | otherwise = v : windows n xs 
    where 
    v = take n xz 

इस के साथ मेरी समस्या मुझे लगता है कि जटिलता हे है (एन * मी) जहां एम सूची की लंबाई है और एन खिड़की का आकार है। आप take के लिए एक बार सूची को गिनते हैं, length के लिए एक और बार, और आप अनिवार्य रूप से एम-एन बार की सूची को नीचे करते हैं। ऐसा लगता है कि यह इससे अधिक कुशल हो सकता है, लेकिन मैं इसे और अधिक रैखिक बनाने के लिए एक नुकसान में हूं। कोई लेने वाला?

Answer 1

यदि आप ओ (1) लंबाई चाहते हैं तो ओ (1) लंबाई प्रदान करने वाली संरचना का उपयोग क्यों न करें? एक सूची के लिए एक वेक्टर से, आप कुछ काट सकता है प्रत्येक विंडो के

import qualified Data.Vector as V 
import Data.Vector (Vector) 
import Data.List(unfoldr) 

windows :: Int -> [a] -> [[a]] 
windows n = map V.toList . unfoldr go . V.fromList 
where      
    go xs | V.length xs < n = Nothing 
     | otherwise = 
      let (a,b) = V.splitAt n xs 
      in Just (a,b) 

वार्तालाप मैं वहाँ एक आशावादी अनुमान खतरे नहीं होगा, लेकिन मैं: मान लें कि आप एक अनंत सूची से खिड़कियों के लिए नहीं देख रहे हैं, प्रयोग करने पर विचार शर्त लगाएगी कि प्रदर्शन केवल सूची संस्करण से बेहतर है।

Answer 2

आप SeqData.Sequence, जो हे है (1) को कतारबद्ध और दोनों सिरों पर विपंक्ति से उपयोग कर सकते हैं:

import Data.Foldable (toList) 
import qualified Data.Sequence as Seq 
import Data.Sequence ((|>)) 

windows :: Int -> [a] -> [[a]] 
windows n0 = go 0 Seq.empty 
    where 
    go n s (a:as) | n' < n0 =    go n' s' as 
        | n' == n0 = toList s' : go n' s' as 
        | otherwise = toList s'' : go n s'' as 
     where 
     n' = n + 1   -- O(1) 
     s' = s |> a  -- O(1) 
     s'' = Seq.drop 1 s' -- O(1) 
    go _ _ [] = [] 

ध्यान दें कि यदि आप पूरे परिणाम अमल में लाना अपने एल्गोरिथ्म के बाद से जरूरी हे (एन * एम) है यह आपके परिणाम का आकार है। Seq का उपयोग करके निरंतर कारक द्वारा प्रदर्शन में सुधार होता है।

उदाहरण उपयोग:

>>> windows [1..5] 
[[1,2,3],[2,3,4],[3,4,5]] 

Answer 3

पहले के अंत में कम लोगों के बारे में चिंता किए बिना खिड़कियों मिलता है:

import Data.List (tails) 

windows' :: Int -> [a] -> [[a]] 
windows' n = map (take n) . tails 

> windows' 3 [1..5] 
[[1,2,3],[2,3,4],[3,4,5],[4,5],[5],[]] 

अब हम कम लोगों से छुटकारा पाने के लिए चाहते हैं लंबाई की जाँच के बिना हर एक का।

जब से हम जानते हैं कि वे अंत में कर रहे हैं, हम उन्हें इस तरह खो सकता है:

windows n xs = take (length xs - n + 1) (windows' n xs) 

लेकिन उस महान के बाद से हम अभी भी एक अतिरिक्त समय इसकी लंबाई प्राप्त करने के लिए XS के माध्यम से जाना नहीं है। यह अनंत सूचियों पर भी काम नहीं करता है, जो आपके मूल समाधान ने किया था। भी

windows :: Int -> [a] -> [[a]] 
windows n xs = takeLengthOf (drop (n-1) xs) (windows' n xs) 

> windows 3 [1..5] 
[[1,2,3],[2,3,4],[3,4,5]] 

वर्क्स पर अनंत सूचियां:

इसके बजाय चलो एक शासक के रूप में एक सूची का उपयोग मात्रा को मापने के लिए एक और से के लिए एक समारोह लिखें:

takeLengthOf :: [a] -> [b] -> [b] 
takeLengthOf = zipWith (flip const) 

> takeLengthOf ["elements", "get", "ignored"] [1..10] 
[1,2,3] 

अब हम यह लिख सकते हैं :

> take 5 (windows 3 [1..]) 
[[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7]] 

जैसा कि गेब्रियल गोंजालेज कहते हैं, समय जटिलता बेहतर नहीं है यदि आप चाहते हैं पूरे परिणाम का प्रयोग करें। लेकिन अगर आप केवल कुछ खिड़कियों का उपयोग करते हैं, तो अब हम take और length के काम करने से बचने के लिए प्रबंधन करते हैं।

Answer 4

आप ओ (एम * एन) से बेहतर नहीं हो सकते हैं, क्योंकि यह आउटपुट डेटा संरचना का आकार है।

लेकिन यदि आप संचालन के क्रम को उलटते हैं तो आप खिड़कियों की लंबाई की जांच से बच सकते हैं: पहले n सूचियों को स्थानांतरित करें और फिर उन्हें एक साथ ज़िप करें। ज़िपिंग उन लोगों से छुटकारा पायेगा जिनके पास पर्याप्त तत्व नहीं हैं।

import Control.Applicative 
import Data.Traversable (sequenceA) 
import Data.List (tails) 

transpose' :: [[a]] -> [[a]] 
transpose' = getZipList . sequenceA . map ZipList 

सूचियों की एक सूची ज़िप किया जा रहा सिर्फ एक transposition है, लेकिन transposeData.List से विपरीत यह आउटपुट कम से कम n तत्वों होगा फेंक देता है।

अब यह खिड़की समारोह बनाने के लिए आसान है: मीटर सूचियां 1 से स्थानांतरित कर दिया ले लो, और सिर्फ उन्हें ज़िप:

windows :: Int -> [a] -> [[a]] 
windows m = transpose' . take m . tails 

अनंत सूचियों के लिए भी काम करता है।

Answer 5

स्लाइडिंग विंडो के लिए मैंने लम्बाई, ले, ड्रॉप और साथ ही विभाजन के रूप में अनबॉक्स किए गए Vetors का भी उपयोग किया है ओ (1) संचालन हैं।

थॉमस एम। डुबुइसन का कोड एक एन एन एन खिड़की वाली खिड़की है, एक स्लाइडिंग नहीं, अगर एन = 1 को छोड़कर। इसलिए एक (++) गुम है, हालांकि इसकी ओ (एन + एम) की लागत है। इसलिए सावधान, जहां आप इसे डालते हैं।

import qualified Data.Vector.Unboxed as V 
import Data.Vector.Unboxed (Vector) 
import Data.List 

windows :: Int -> Vector Double -> [[Int]] 
windows n = (unfoldr go) 
    where      
    go !xs | V.length xs < n = Nothing 
      | otherwise = 
      let (a,b) = V.splitAt 1 xs 
        c= (V.toList a ++V.toList (V.take (n-1) b)) 
      in (c,b) 

मैं इसे +RTS -sstderr के साथ बाहर की कोशिश की और:

putStrLn $ show (L.sum $ L.concat $ windows 10 (U.fromList $ [1..1000000])) 

और वास्तविक समय 1.051s और 96.9% उपयोग है, याद रखें कि इस रपट खिड़की के बाद दो हे (एम) के संचालन प्रदर्शन कर रहे हैं।