25

制限時間 (秒単位) とリストを取り、制限時間内にリストの要素をできるだけ多く計算する関数を作成したいと考えています。

私の最初の試みは、最初に次の関数を作成することでした。この関数は、純粋な計算の時間を計測し、結果とともに経過時間を返します。

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)

ただし、これは正しくありません。タイミング エラーや浮動小数点エラーを無視しても、このアプローチではリストの要素の計算が開始されると停止することはありません。

代わりに、時間がかかりすぎた場合に評価を短絡できる関数があったとします。

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

次に、本当に必要な関数を記述できます。

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)

私の質問は次のとおりです。

  1. どうやって書くのtimeOut？
  2. 関数を記述するためのより良い方法はありtimeLimitedますか?たとえば、時間差を複数回追加することによる浮動小数点エラーの蓄積に悩まされない方法はありますか?
4

3 に答える 3

13

上記の提案のいくつかを使用して調理できた例を次に示します。タイマーが切れたときに作業が正確に中断されるようにするための大量のテストは行っていませんが、 のドキュメントに基づいてtimeout、これは 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:)

それでは、コストのかかるもので試してみましょう。

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、動作するようです (明らかに、時間指定部分以外にいくらかのオーバーヘッドがありますが、私は約 100 ミリ秒です:

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

また、このアプローチについて注意すべき点があります。計算を実行してそれらを tvar にプッシュする操作全体を への 1 回の呼び出しで囲んでいるためtimeout、(計算にコストがかかる場合) ' t アカウントまたは全体の時間の多く。

アップデート

Haskell の怠惰のせいで、それについて考える時間ができたので、上記のメモ (戻り構造の作成に費やされた時間について) が 100% 正しいとは言えません。いずれにせよ、これがあなたが達成しようとしていることに対して十分に正確でない場合はお知らせください。

于 2012-07-04T03:46:20.687 に答える
4

andtimeOutを使用して指定したタイプで実装できます。これは次のようになります (残り時間を計算する部分は省略しました。これには useなどを使用します)。timeoutevaluategetCurrentTime

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

弱いヘッドの正規形だけでなく、より多くの強制が必要な場合は、既に seq された引数でこれを呼び出すことができtimeoutPure (deepseq v)ますtimeoutPure v。

于 2012-07-04T01:13:10.850 に答える
2

TVarsと一緒に2つのスレッドを使用し、タイムアウトに達したときに計算スレッドで例外を発生させます（これにより、進行中のすべてのトランザクションがロールバックされます）。

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

この例では、forceIntoTVarを少し調整して、たとえばリストノードがアトミックトランザクション内で計算されないようにする必要がありますが、最初に計算されてからアトミックトランザクションが開始されてリストに追加されます。

いずれの場合も、例外が発生すると、進行中のトランザクションがロールバックされるか、進行中の計算が停止されてから、結果がリストに反映されます。

考慮する必要があるのは、ノードを準備するための個々の計算が高頻度で実行される場合、この例はSTMを使用しない場合と比較しておそらく非常にコストがかかるということです。

于 2012-07-04T07:35:33.943 に答える