एक निश्चित समय में जितनी संभव हो सके उतनी सूची की गणना करें

Question

मैं एक ऐसा फ़ंक्शन लिखना चाहता हूं जिसमें समय सीमा (सेकंड में) और एक सूची हो, और समय सीमा के भीतर जितनी संभव हो सके सूची के कई तत्वों की गणना करें।

मेरा पहला प्रयास पहले निम्नलिखित समारोह, जो कई बार एक शुद्ध गणना लिखने के लिए था और समय परिणाम के साथ गुजरे रिटर्न:

import Control.DeepSeq 
import System.CPUTime 

type Time = Double 

timed :: (NFData a) => a -> IO (a, Time) 
timed x = do t1 <- getCPUTime 
      r <- return $!! x 
      t2 <- getCPUTime 
      let diff = fromIntegral (t2 - t1)/10^12 
      return (r, diff) 

मैं तो समारोह मैं इस के मामले में चाहते हैं परिभाषित कर सकते हैं:

timeLimited :: (NFData a) => Time -> [a] -> IO [a] 
timeLimited remaining []  = return [] 
timeLimited remaining (x:xs) = if remaining < 0 
    then return [] 
    else do 
     (y,t) <- timed x 
     ys <- timeLimited (remaining - t) xs 
     return (y:ys) 

हालांकि यह बिल्कुल सही नहीं है। समय त्रुटियों और फ़्लोटिंग पॉइंट त्रुटियों को अनदेखा करने के बावजूद, यह दृष्टिकोण कभी भी शुरू होने के बाद सूची के तत्व की गणना को रोकता नहीं है, जिसका अर्थ यह है कि यह (और वास्तव में, सामान्य रूप से) अपनी समय सीमा को खत्म कर सकता है।

, तो इसके बजाय मैं एक समारोह है कि सकता है शॉर्ट सर्किट मूल्यांकन करता है, तो यह बहुत लंबा ले लिया था था:

timeLimited' :: Time -> [a] -> IO [a] 
timeLimited' remaining []  = return [] 
timeLimited' remaining (x:xs) = do 
    result <- timeOut remaining x 
    case result of 
     Nothing -> return [] 
     Just (y,t) -> do 
      ys <- timeLimited' (remaining - t) xs 
      return (y:ys) 

:

timeOut :: Time -> a -> IO (Maybe (a,t)) 
timeOut = undefined 

तो मैं समारोह है कि मैं वास्तव में चाहते लिख सकता है मेरे प्रश्न हैं:

1. मैं timeOut कैसे लिखूं?
2. क्या timeLimited फ़ंक्शन लिखने का कोई बेहतर तरीका है, उदाहरण के लिए, जो एक बार फ़्लोटिंग पॉइंट त्रुटि से संचित फ्लोटिंग पॉइंट त्रुटि से पीड़ित नहीं होता है?

Answer 1

यहां एक उदाहरण है कि मैं ऊपर दिए गए कुछ सुझावों का उपयोग करके पका सकता हूं। टाइमर खत्म होने पर काम को ठीक से बंद करने के लिए मैंने परीक्षण की भारी मात्रा में नहीं किया है, लेकिन timeout के लिए दस्तावेज़ों के आधार पर, यह सभी चीजों के लिए काम करना चाहिए जो एफएफआई का उपयोग नहीं करते हैं।

import Control.Concurrent.STM 
import Control.DeepSeq 
import System.Timeout 

type Time = Int 

-- | Compute as many items of a list in given timeframe (microseconds) 
-- This is done by running a function that computes (with `force`) 
-- list items and pushed them onto a `TVar [a]`. When the requested time 
-- expires, ghc will terminate the execution of `forceIntoTVar`, and we'll 
-- return what has been pushed onto the tvar. 
timeLimited :: (NFData a) => Time -> [a] -> IO [a] 
timeLimited t xs = do 
    v <- newTVarIO [] 
    _ <- timeout t (forceIntoTVar xs v) 
    readTVarIO v 

-- | Force computed values into given tvar 
forceIntoTVar :: (NFData a) => [a] -> TVar [a] -> IO [()] 
forceIntoTVar xs v = mapM (atomically . modifyTVar v . forceCons) xs 

-- | Returns function that does actual computation and cons' to tvar value 
forceCons :: (NFData a) => a -> [a] -> [a] 
forceCons x = (force x:) 

अब यह कुछ महंगा पर कोशिश करते हैं:

main = do 
    xs <- timeLimited 100000 expensiveThing -- run for 100 milliseconds 
    print $ length $ xs -- how many did we get? 

-- | Some high-cost computation 
expensiveThing :: [Integer] 
expensiveThing = sieve [2..] 
    where 
     sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0] 

संकलित और time साथ चलाने के लिए, यह काम करने के लिए (जाहिर है वहाँ समय भाग के बाहर कुछ भूमि के ऊपर है लगता है, लेकिन मैं मोटे तौर पर 100ms हूँ :

$ time ./timeLimited 
1234 
./timeLimited 0.10s user 0.01s system 97% cpu 0.112 total 

इसके अलावा, इस दृष्टिकोण के बारे में नोट करने के लिए कुछ, के बाद से मैं संगणना चल रहा है और करने के लिए एक कॉल के अंदर tvar पर उन्हें धक्का के पूरे ऑपरेशन संलग्न कर रहा हूँ timeout, यहां कुछ समय वापसी की संरचना बनाने में खो गया है, हालांकि मैं मान रहा हूं (यदि आपकी गणना महंगा है) तो यह आपके खाते का अधिक समय या अधिक नहीं होगा।

अद्यतन

अब जब कि मैं हास्केल के आलस्य के कारण, कुछ समय इसके बारे में सोचने के लिए मिला है, मैं 100% सकारात्मक नहीं टिप्पणी ऊपर (के बारे में वापसी संरचना का निर्माण समय बिताया) है कर रहा हूँ सही बात; किसी भी तरह से, मुझे बताएं कि क्या यह पूरा करने के लिए आप जो कुछ भी करने की कोशिश कर रहे हैं उसके लिए पर्याप्त सटीक नहीं है।

Answer 2

आप प्रकार आप timeout और evaluate का उपयोग कर दिया साथ timeOut लागू कर सकते हैं। यह (मैं भाग की गणना करता है कि कितना समय बचा है हटा दिया है - getCurrentTime का उपयोग करें या उस के लिए समान) इस तरह दिखता है:

timeoutPure :: Int -> a -> IO (Maybe a) 
timeoutPure t a = timeout t (evaluate a) 

आप अधिक सिर्फ कमजोर सिर सामान्य रूप से मजबूर कर चाहते हैं, आप इसे पहले से ही seq'd तर्क के साथ कॉल कर सकते हैं, उदाहरण के लिए timeoutPure v के बजाय।

Answer 3

मैं दो धागे एक साथ TVars साथ उपयोग करें और एक अपवाद बढ़ा गणना सूत्र में जब समय समाप्ति तक पहुँच गया है (यह है कि हर चल रही लेन-देन वापस लुढ़का जा करने के लिए कारण बनता है) होगा: (इस उदाहरण आप में

forceIntoTVar :: (NFData a) => [a] -> TVar [a] -> IO [()] 
forceIntoTVar xs v = mapM (atomically . modifyTVar v . forceCons) xs 

-- | Returns function that does actual computation and cons' to tvar value 
forceCons :: (NFData a) => a -> [a] -> [a] 
forceCons x = (force x:) 

main = do 

    v <- newTVarIO [] 
    tID <- forkIO $ forceIntoTVar args v 
    threadDelay 200 
    killThread tID 
    readTVarIO v 

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

किसी भी मामले में, जब अपवाद चल रही लेन-देन के लिए उठाया है वापस लुढ़का हुआ है या परिणाम से पहले सूची में consed है चल रही गणना बंद कर दिया जाता है और कि तुम क्या चाहते है।

क्या आप विचार करने की जरूरत है कि जब व्यक्ति संगणना उच्च आवृत्ति के साथ एक नोड रन तैयार करने के लिए तो इस उदाहरण शायद बहुत महंगा एसटीएम का उपयोग नहीं की तुलना में है।