Haskell：如何在主要功能中使用HashMap

Question

恳请您的帮助，加快以下程序的速度：

main = do
  jobsToProcess <- fmap read getLine
  forM_ [1..jobsToProcess] $ \_ -> do
    [r, k] <- fmap (map read . words) getLine :: IO [Int]
    putStrLn $ doSomeReallyLongWorkingJob r k

可能有很多相同的工作要做，但是这不是我修改输入的决定，因此我尝试Data.HashMap用于备份已处理的工作。我已经在doSomeReallyLongWorkingJob函数中优化了算法，但是现在看来，它和C一样快。

但不幸的是，我似乎无法实现简单的缓存而不会产生很多错误。我需要一个简单的Type缓存HashMap (Int, Int) Int，但是每次括号太多或太少时。而且，如果我设法定义缓存，那么我就会陷入将数据放入缓存或从缓存中检索数据的问题，这会导致很多错误。

我已经在Google上搜索了几个小时，但似乎被卡住了。BTW：的结果longrunner是Int也。

Answer 1

进行缓存操作的有状态操作非常简单。首先一些样板：

{-# LANGUAGE FlexibleContexts #-}
import Control.Monad.State
import Data.Map (Map)
import qualified Data.Map as M
import Debug.Trace

我将使用Data.Map，但是您当然可以在哈希映射或任何类似的数据结构中替换，而不会遇到太多麻烦。我长时间运行的计算只会将其参数加起来。我将trace显示执行此计算的时间。trace当我们输入重复的输入时，我们希望不要看到的输出。

reallyLongRunningComputation :: [Int] -> Int
reallyLongRunningComputation args = traceShow args $ sum args

现在，缓存操作将只是查询我们之前是否已经看到过给定的输入。如果有，我们将返回预先计算出的答案；否则，我们现在将计算出答案并将其存储。

cache :: (MonadState (Map a b) m, Ord a) => (a -> b) -> a -> m b
cache f x = do
    mCached <- gets (M.lookup x)
    case mCached of
        -- depending on your goals, you may wish to force `result` here
        Nothing -> modify (M.insert x result) >> return result
        Just cached -> return cached
    where
    result = f x

main现在，该功能仅包括调用cache reallyLongRunningComputation适当的输入。

main = do
    iterations <- readLn
    flip evalStateT M.empty . replicateM_ iterations
        $   liftIO getLine
        >>= liftIO . mapM readIO . words
        >>= cache reallyLongRunningComputation
        >>= liftIO . print

让我们在ghci中尝试一下！

> main
5
1 2 3
[1,2,3]
6
4 5
[4,5]
9
1 2
[1,2]
3
1 2
3
1 2 3
6

如您在括号内的输出中所见，这reallyLongRunningComputation是我们第一次输入1 2 3和我们第一次输入的名称1 2，但不是我们第二次输入这些输入的名称。