तो, मैंने कुछ खोदने लगा, और मैं निम्नलिखित के साथ आया।
संपादित करें: Gist उन लोगों के लिए जो एसओ स्वरूपण को पसंद करेंगे।
पहले, मतलब
module Means where
import Data.List
import Control.Applicative
mean :: (Fractional a1, Real a, Foldable t) => t a -> a1
mean xs = realToFrac (sum xs)/realToFrac (length xs)
mean' :: (Foldable f, Fractional a) => f a -> a
mean' = liftA2 (/) sum (fromIntegral . length)
data Pair = Pair {-# UNPACK #-}!Int {-# UNPACK #-}!Double
mean'' :: [Double] -> Double
mean'' xs = s/fromIntegral n
where
Pair n s = foldl' k (Pair 0 0) xs
k (Pair n s) x = Pair (n+1) (s+x)
पिछले एक के कुछ ही कार्यान्वयन एक स्पष्ट सख्त जोड़ी निर्माता का उपयोग करता है। आईआईआरसी, (,) आलसी है, इसलिए यह हमें बेहतर प्रदर्शन विशेषताओं देना चाहिए।
module Covariance where
import Means
covariance :: (Fractional a, Real a1) => [a1] -> [a1] -> a
covariance xs ys = mean (zipWith (*) xs ys) - mean xs * mean ys
covariance' :: Fractional a => [a] -> [a] -> a
covariance' xs ys = mean' (zipWith (*) xs ys) - mean' xs * mean' ys
covariance'' :: [Double] -> [Double] -> Double
covariance'' xs ys = mean'' (zipWith (*) xs ys) - mean'' xs * mean'' ys
covariance''' :: [Double] -> [Double] -> Double
covariance''' xs ys =
let mx = mean'' xs
my = mean'' ys
in
sum (zipWith (\x y -> (x - mx) * (y - my)) xs ys)/fromIntegral (length xs)
मैं अलग मतलब विकल्पों में से प्रत्येक का उपयोग कर अपने cov के कुछ संस्करणों की कोशिश की, तो एक भद्दा "प्रदर्शन" संस्करण।
मैंने परीक्षण के लिए कुछ हार्डकोडेड सूचियों के साथ एक साधारण Main को एक साथ फेंक दिया।
module Main where
import Means
import Covariance
v1 = [1000000..2000000]
v2 = [2000000..3000000]
main :: IO()
main = do
-- let cov = covariance v1 v2
-- let cov = covariance' v1 v2
-- let cov = covariance'' v1 v2
let cov = covariance''' v1 v2
print cov
-rtsopts साथ संकलन और +RTS -s के साथ चल रहा है, मैं निम्नलिखित आवंटन जानकारी मिल गया।
covariance:
8.33335e10
531,816,984 bytes allocated in the heap
890,566,720 bytes copied during GC
148,609,912 bytes maximum residency (11 sample(s))
15,649,528 bytes maximum slop
374 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 981 colls, 0 par 0.385s 0.389s 0.0004s 0.0012s
Gen 1 11 colls, 0 par 0.445s 0.584s 0.0531s 0.2084s
INIT time 0.000s ( 0.002s elapsed)
MUT time 0.194s ( 0.168s elapsed)
GC time 0.830s ( 0.973s elapsed)
EXIT time 0.001s ( 0.029s elapsed)
module Main where
Total time 1.027s ( 1.172s elapsed)
%GC time 80.9% (83.0% elapsed)
Alloc rate 2,741,140,975 bytes per MUT second
Productivity 19.1% of total user, 16.8% of total elapsed
covariance':
8.333350000320508e10
723,822,456 bytes allocated in the heap
891,626,240 bytes copied during GC
185,629,664 bytes maximum residency (11 sample(s))
3,693,296 bytes maximum slop
435 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 1372 colls, 0 par 0.388s 0.392s 0.0003s 0.0010s
Gen 1 11 colls, 0 par 0.388s 0.551s 0.0501s 0.1961s
INIT time 0.000s ( 0.002s elapsed)
MUT time 0.227s ( 0.202s elapsed)
GC time 0.777s ( 0.943s elapsed)
EXIT time 0.001s ( 0.029s elapsed)
Total time 1.006s ( 1.176s elapsed)
%GC time 77.2% (80.2% elapsed)
Alloc rate 3,195,430,190 bytes per MUT second
Productivity 22.8% of total user, 19.6% of total elapsed
covariance'':
8.333350000320508e10
456,108,392 bytes allocated in the heap
394,432,096 bytes copied during GC
79,295,648 bytes maximum residency (15 sample(s))
21,161,776 bytes maximum slop
201 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 861 colls, 0 par 0.085s 0.089s 0.0001s 0.0005s
Gen 1 15 colls, 0 par 0.196s 0.274s 0.0182s 0.0681s
INIT time 0.000s ( 0.002s elapsed)
MUT time 0.124s ( 0.106s elapsed)
GC time 0.282s ( 0.362s elapsed)
EXIT time 0.001s ( 0.021s elapsed)
Total time 0.408s ( 0.491s elapsed)
%GC time 69.1% (73.7% elapsed)
Alloc rate 3,681,440,521 bytes per MUT second
Productivity 30.9% of total user, 25.9% of total elapsed
covariance''':
8.333349999886264e10
336,108,336 bytes allocated in the heap
202,943,312 bytes copied during GC
47,493,864 bytes maximum residency (10 sample(s))
13,578,520 bytes maximum slop
115 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 633 colls, 0 par 0.053s 0.055s 0.0001s 0.0002s
Gen 1 10 colls, 0 par 0.089s 0.131s 0.0131s 0.0472s
INIT time 0.000s ( 0.002s elapsed)
MUT time 0.095s ( 0.086s elapsed)
GC time 0.142s ( 0.186s elapsed)
EXIT time 0.001s ( 0.011s elapsed)
Total time 0.240s ( 0.286s elapsed)
%GC time 59.2% (65.1% elapsed)
Alloc rate 3,522,631,228 bytes per MUT second
Productivity 40.8% of total user, 34.1% of total elapsed
जैसा कि आप देख सकते हैं, बहुत से आवंटन उस माध्यम पर निर्भर हैं जिसका हम साथ जाते हैं। हम सख्त जोड़ी कन्स्ट्रक्टर के साथ mean'' का उपयोग करके सबसे बड़ा बढ़ावा प्राप्त करते हैं, यहां तक कि बेवकूफ zipWith कार्यान्वयन के साथ भी।
मैं weigh के साथ कार्यान्वयन को तारों पर काम कर रहा हूं, इसलिए मेरे पास कुछ और डेटा हो सकता है।
घटक कार्यों को ट्यून करने से परे, मुझे covmat से निपटने का एक और अधिक प्रदर्शन करने वाला तरीका नहीं पता है, लेकिन सख्त जोड़ी कन्स्ट्रक्टर कम से कम आपके स्पेस विशेषताओं को बेहतर बनाना चाहिए चाहे आप और क्या करते हैं।
संपादित करें: weigh परिणाम
Case Allocated GCs
naive mean 723,716,168 1,382
applicative mean 723,714,736 1,382
optimized mean, naive zipWith 456,000,688 875
optimized mean, hand-tuned zipWith 336,000,672 642
दूसरा संपादित करें:
मैं पकड़ा गेब्रियल के भयानक foldl प्रदर्शन किस तरह हम हाथ से धुन पर स्पष्ट सख्त जोड़ी के साथ मतलब बिना प्राप्त कर सकते हैं देखने के लिए।
import qualified Control.Foldl as L
mean''' :: [Double] -> Double
mean''' = L.fold (liftA2 (/) L.sum L.genericLength)
covariance'''' :: [Double] -> [Double] -> Double
covariance'''' xs ys = mean''' (zipWith (*) xs ys) - mean''' xs * mean''' ys
covariance''''' :: [Double] -> [Double] -> Double
covariance''''' xs ys = let mx = mean''' xs
my = mean''' ys
in
mean''' (zipWith (\x y -> (x - mx) * (y - my)) xs ys)
आवंटन परिणाम:
covariance'''':
8.333350000320508e10
336,108,272 bytes allocated in the heap
222,635,752 bytes copied during GC
61,198,528 bytes maximum residency (10 sample(s))
13,627,544 bytes maximum slop
140 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 633 colls, 0 par 0.052s 0.054s 0.0001s 0.0003s
Gen 1 10 colls, 0 par 0.105s 0.155s 0.0155s 0.0592s
INIT time 0.000s ( 0.002s elapsed)
MUT time 0.110s ( 0.099s elapsed)
GC time 0.156s ( 0.209s elapsed)
EXIT time 0.001s ( 0.014s elapsed)
Total time 0.269s ( 0.323s elapsed)
%GC time 58.1% (64.5% elapsed)
Alloc rate 3,054,641,122 bytes per MUT second
Productivity 41.8% of total user, 34.9% of total elapsed
covariance''''':
8.333349999886264e10
336,108,232 bytes allocated in the heap
202,942,400 bytes copied during GC
47,493,816 bytes maximum residency (10 sample(s))
13,578,568 bytes maximum slop
115 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 633 colls, 0 par 0.057s 0.059s 0.0001s 0.0003s
Gen 1 10 colls, 0 par 0.086s 0.126s 0.0126s 0.0426s
INIT time 0.000s ( 0.002s elapsed)
MUT time 0.096s ( 0.087s elapsed)
GC time 0.143s ( 0.184s elapsed)
EXIT time 0.001s ( 0.011s elapsed)
Total time 0.241s ( 0.285s elapsed)
%GC time 59.2% (64.7% elapsed)
Alloc rate 3,504,449,342 bytes per MUT second
Productivity 40.8% of total user, 34.5% of total elapsed
और weigh परिणाम:
foldl mean 336,000,568 642
foldl mean, tuned zipWith 336,000,568 642
संक्षेप में, ऐसा लगता है कि foldl कार्यान्वयन आपकी सर्वोत्तम शर्त है। यह क्या कर रहा है इसके बारे में यह बेहद स्पष्ट है, और हमारे हाथ-ट्यूनिंग के परिणाम को कुशलतापूर्वक, मीटिंग या उससे अधिक इनपुट इनपुट करने के लिए कुछ वाकई फैंसी चाल खींचता है। आप संभवतः किसी अन्य डेटा संरचना का उपयोग करके कुछ अतिरिक्त रस निकाल सकते हैं, लेकिन विनम्र सूची के लिए यह बहुत अच्छा प्रदर्शन है। : डी
तीसरा संपादित करें:
मैंने पहले एडवर्ड folds का उपयोग किया है कभी नहीं, इसलिए मैं बहुत बेवकूफ कुछ कर रही हो सकता है, लेकिन मैं यह भी उन का उपयोग कर एक कार्यान्वयन बाहर की कोशिश की।
import qualified Data.Fold as F
sumL :: Num a => F.L a a
sumL = F.L id (+) 0
lengthL :: Num b => F.L a b
lengthL = F.L id (const . (+1)) 0
mean'''' :: [Double] -> Double
mean'''' = flip F.run (liftA2 (/) sumL lengthL)
covariance'''''' :: [Double] -> [Double] -> Double
covariance'''''' xs ys = mean'''' (zipWith (*) xs ys) - mean'''' xs * mean'''' ys
covariance''''''' :: [Double] -> [Double] -> Double
covariance''''''' xs ys = let mx = mean'''' xs
my = mean'''' ys
in
mean'''' (zipWith (\x y -> (x - mx) * (y - my)) xs ys)
आवंटन परिणाम:
covariance'''''':
8.333350000320508e10
456,108,488 bytes allocated in the heap
394,432,096 bytes copied during GC
79,295,648 bytes maximum residency (15 sample(s))
21,161,776 bytes maximum slop
201 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 861 colls, 0 par 0.089s 0.092s 0.0001s 0.0003s
Gen 1 15 colls, 0 par 0.198s 0.276s 0.0184s 0.0720s
INIT time 0.000s ( 0.002s elapsed)
MUT time 0.135s ( 0.119s elapsed)
GC time 0.287s ( 0.367s elapsed)
EXIT time 0.001s ( 0.019s elapsed)
Total time 0.425s ( 0.506s elapsed)
%GC time 67.6% (72.5% elapsed)
Alloc rate 3,388,218,993 bytes per MUT second
Productivity 32.3% of total user, 27.1% of total elapsed
covariance''''''':
8.333349999886264e10
456,108,552 bytes allocated in the heap
291,275,200 bytes copied during GC
62,670,040 bytes maximum residency (11 sample(s))
15,029,432 bytes maximum slop
172 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 862 colls, 0 par 0.068s 0.070s 0.0001s 0.0003s
Gen 1 11 colls, 0 par 0.149s 0.210s 0.0191s 0.0570s
INIT time 0.000s ( 0.002s elapsed)
MUT time 0.118s ( 0.104s elapsed)
GC time 0.217s ( 0.280s elapsed)
EXIT time 0.001s ( 0.016s elapsed)
Total time 0.337s ( 0.403s elapsed)
%GC time 64.3% (69.6% elapsed)
Alloc rate 3,870,870,585 bytes per MUT second
Productivity 35.7% of total user, 29.9% of total elapsed
और weigh परिणाम:
folds mean 456,000,784 875
folds mean, tuned zipWith 456,000,888 871
एक और संपादन: मैंने folds विकल्प L' का उपयोग L के बजाय भी किया, लेकिन परिणाम समान थे।
इस समस्या का काफी अध्ययन किया गया है। [यह] देखें (http://squing.blogspot.com/2008/11/beautiful-folding.html) और [यह] (https://hackage.haskell.org/package/folds) (और इसमें लिंक पैकेज विवरण) – luqui
मुझे गेब्रियल के सुंदर फ़ोल्डरों का संस्करण अधिक पसंद है: [वीडियो] (https://www.youtube.com/watch?v=6a5Ti0r8Q2s) और [लाइब्रेरी] (https://hackage.haskell.org/package/ foldl)। वीडियो वास्तव में स्पष्ट और समझ में आता है। Kmett के पुस्तकालयों के बारे में निश्चित नहीं है ... 'फ़ोल्ड्स' के बारे में भी अच्छे ट्यूटोरियल नहीं मिला :( – Shersh
गणना करने के लिए संख्यात्मक रूप से स्थिर ऑनलाइन एल्गोरिदम के लिए https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Covariance पर एक नज़र डालें covariance (online_covariance का उपयोग करें) –