在固定时间内尽可能多地计算列表 [英] Compute as much of a list as possible in a fixed time

问题描述

我想编写一个函数，它需要一个时间限制（以秒为单位）和一个列表，并且在时间限制内计算尽可能多的列表元素。

我的第一次尝试是先写下面的函数，它是纯计算的结果，并返回结果的时间：

  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）
  pre> 
 
 
然后我可以根据这个定义我想要的函数： 
 
 
  timeLimited ::（NFData a）=>时间 - > [a]  - > IO [a] 
 timeLimited remaining [] = return [] 
 timeLimited其余（x：xs）=如果剩余< 0 
然后返回[] 
 else 
（y，t）<  -  timed x 
 ys<  -  timeLimited（remaining -t）xs 
 return y：ys）
  
虽然这并不完全正确。即使忽略定时错误和浮点错误，这种方法一旦启动就不会停止列表元素的计算，这意味着它可以（并且实际上通常会）超出其时间限制。
 
 
 
如果我有一个功能可以在评估时间过长时进行短路评估： 
 
 
  timeOut :: Time  - > a  - > IO（Maybe（a，t））
 timeOut = undefined 
  
然后我可以写函数，我真的想要：
  timeLimited':: Time  - > [a]  - > IO [a] 
 timeLimited'remaining [] = return [] 
 timeLimited'剩余（x：xs）= do 
结果<  -  timeOut剩余x 
结果
 Nothing  - > return [] 
 Just（y，t） - > 
 ys < -  timeLimited'（remaining -t）xs 
 return（y：ys）
  
我的问题是： 
 
 
 
 
如何写 timeOut  ？
 
 
是否有更好的方法来编写函数 timeLimited ，例如，不会遇到累积浮点错误从多少次添加时间差？
 
 
 
 
解决方案
这是我能够做出的一个例子使用上面的一些建议。我没有做过大量的测试，以确保工作在计时器用完时切断，但基于文档  timeout  ，这应该适用于所有不使用FFI的东西。
  import Control.Concurrent.STM 
 import Control.DeepSeq 
 import System.Timeout 
 
 type Time = Int 
 
  -  |在给定的时间范围内计算一个列表的项目（微秒）
  - 这是通过运行一个函数来计算的（使用`force`）
  - 列表项并将它们推送到一个`TVar [一]`。当请求的时间
  - 到期时，ghc将终止`forceIntoTVar`的执行，并且我们将
  - 返回已经被推入tvar的内容。 
 timeLimited ::（NFData a）=>时间 - > [a]  - > IO [a] 
 timeLimited t xs = do 
v < -  newTVarIO [] 
 _<  - 超时t（forceIntoTVar xs v）
 readTVarIO v 
 
  -  |将计算值强制为给定的tvar 
 forceIntoTVar ::（NFData a）=> [a]  - > TVar [a]  - > IO [（）] 
 forceIntoTVar xs v = mapM（atomically。modifyTVar v。forceCons）xs 
 
  -  |返回执行实际计算和cons'to tvar值的函数
 forceCons ::（NFData a）=> a  - > [a]  - > [a] 
 forceCons x =（force x :) 
  
现在让我们尝试一下昂贵：
 
 
  main = do 
 xs < -  timeLimited 100000 expensiveThing  - 运行100毫秒
打印$ length $ xs  - 我们获得了多少？ 
 
  -  |一些高成本计算
 expensiveThing :: [Integer] 
 expensiveThing = sieve [2 ..] 
其中
 sieve（p：xs）= p：sieve [x | x <  -  xs，x`mod` p> 0] 
  
编译并使用时间运行，它似乎工作（显然有一些额外的时间部分的开销，但我在大约100毫秒：
  $时间。 / timeLimited 
 1234 
 ./timeLimited 0.10s用户0.01s系统97％cpu 0.112总额
  
 
 $ b $另外，关于这种方法还有一些值得注意的地方;因为我将一个调用运行计算并将它们推送到tvar的整个操作中，在 timeout 的调用中，有些时候这里可能会造成创建返回结构，尽管我假设（如果您的计算成本高昂），它不会占您的总体时间。
 
 
 
 更新 
 
 
 
现在我已经有了一些时间来考虑它了，由于Haskell的懒惰，我不是100％注意上面（关于创建返回结构的时间）是正确的;无论哪种方式，让我知道如果这不够精确的哟你正试图完成。
 
I want to write a function that takes a time limit (in seconds) and a list, and computes as many elements of the list as possible within the time limit.

My first attempt was to first write the following function, which times a pure computation and returns the time elapsed along with the result:
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)
I can then define the function I want in terms of this:
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)
This isn't quite right though. Even ignoring timing errors and floating point errors, this approach never stops the computation of an element of the list once it has started, which means that it can (and in fact, normally will) overrun its time limit.

If instead I had a function that could short-circuit evaluation if it had taken too long:
timeOut :: Time -> a -> IO (Maybe (a,t))
timeOut = undefined
then I could write the function that I really want:
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)
My questions are:

How do I write timeOut?
Is there a better way to write the function timeLimited, for example, one that doesn't suffer from accumulated floating point error from adding up time differences multiple times?

解决方案
Here's an example I was able to cook up using some of the suggestions above.  I've not done huge amounts of testing to ensure work is cut off exactly when the timer runs out, but based on the docs for timeout, this should work for all things not using FFI.
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:)
Now let's try it on something costly:
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]
Compiled and run with time, it seems to work (obviously there is some overhead outside the timed portion, but I'm at roughly 100ms:
$ time ./timeLimited
1234
./timeLimited  0.10s user 0.01s system 97% cpu 0.112 total
Also, something to note about this approach; since I'm enclosing the entire operation of running the computations and pushing them onto the tvar inside one call to timeout, some time here is likely lost in creating the return structure, though I'm assuming (if your computations are costly) it won't account or much of your overall time.

Update

Now that I've had some time to think about it, due to Haskell's laziness, I'm not 100% positive the note above (about time-spent creating the return structure) is correct; either way, let me know if this is not precise enough for what you are trying to accomplish.

                        
这篇关于在固定时间内尽可能多地计算列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！