代码之家 › 专栏 › 技术社区 › fuz

如何在恒定内存中获取make stats

lazy-evaluation memory-management statistics random haskell

fuz · 技术社区 · 14 年前

我有一个函数,它产生一些随机的数值结果。我知道,结果是a(小,a-b约50)范围内的整数 a、乙

values :: [Int]
values = doFunctionNtimes myRandom 1000000
results = map (\x ->length . filter (x==) $ values) [a..b]

有人想这么做吗?

我想我把问题解释错了,对不起。我有一个函数,它-取决于一个随机生成-给出一些小的int值。为了统计,我想知道结果出现的频率。因为我想统计1000000次的尝试次数,所以我需要在尝试次数上保持恒定的内存。

4 回复 | 直到 14 年前

luqui 14 年前

import qualified Data.Map as Map
import Data.List (foldl')          -- ' (to fix SO syntax highlighting)

histogram :: (Ord a) => [a] -> Map.Map a Int
histogram = foldl' (\m x -> Map.insertWith' (+) x 1 m) Map.empty

为什么这样做和为什么它优于特拉维斯·布朗的解决方案的解释是相当技术性的,需要一些耐心才能完全理解。

(4, 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1)

对数字19的一种非常低效的表示。只有当你在地图上要求这个元素时,才会计算出巨大的总和。这些“thunks”(延迟计算表达式)将随着输入的大小线性增长。

为了防止这种情况,我们使用 insertWith' ,它应用函数 严格地 ,也就是说,它在将结果放入映射之前对其求值。因此,如果你在上面的地图中插入4,它将评估重击,你将得到一个很好的整洁:

(4, 20)

另一个将在添加之前对其进行评估,这样您将得到:

(4, 21)

所以现在至少地图的值是常数空间。

我们需要做的最后一件事是将右折叠改为左折叠,因为Map.insert在第二个参数中是严格的。下面演示右折叠的含义。

iw x m = Map.insertWith' (+) x 1 m    -- '

foldr iw Map.empty [1,2,1,3,2,1]
    = iw 1 (iw 2 (iw 1 (iw 3 (iw 2 (iw 1 Map.empty)))))

使用 iw 作为一个简单的速记。 Map.insert 严格执行第二个参数意味着您需要在insert可以执行任何操作之前计算要插入的映射。我会用符号 { k1 -> v1, k2 -> v2, ... } 作为地图的速记。您的评估顺序如下:

foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

foldr iw {} [1,2,1,3,2,1]
iw 1 (foldr iw {} [2,1,3,2,1])
iw 1 (iw 2 (foldr iw {} [1,3,2,1]))
iw 1 (iw 2 (iw 1 (foldr iw {} [3,2,1])))
iw 1 (iw 2 (iw 1 (iw 3 (foldr iw {} [2,1]))))
iw 1 (iw 2 (iw 1 (iw 3 (iw 2 (foldr iw {} [1])))))
iw 1 (iw 2 (iw 1 (iw 3 (iw 2 (iw 1 (foldr iw {} []))))))
iw 1 (iw 2 (iw 1 (iw 3 (iw 2 (iw 1 {}))))))
iw 1 (iw 2 (iw 1 (iw 3 (iw 2 {1 -> 1}))))
iw 1 (iw 2 (iw 1 (iw 3 {1 -> 1, 2 -> 1})))
iw 1 (iw 2 (iw 1 {1 -> 1, 2 -> 1, 3 -> 1}))
iw 1 (iw 2 {1 -> 2, 2 -> 1, 3 -> 1})
iw 1 {1 -> 2, 2 -> 2, 3 -> 1}
{1 -> 3, 2 -> 2, 3 -> 1}

因此,如果有一个1000000元素数组,我们必须一直到第1000000个元素开始插入,因此我们需要将前面的999999个元素保留在内存中,以便知道接下来要做什么。左折可以解决这个问题:

-- definition of left fold
foldl' f z xs = go z xs             -- '
    where 
    go accum [] = z
    go accum (x:xs) = accum `seq` go (f accum x) xs

foldl' (flip iw) Map.empty [1,2,1,3,2,1]  -- needed to flip arg order to appease foldl'
go {} [1,2,1,3,2,1]
go (iw 1 {}) [2,1,3,2,1]
go (iw 2 {1 -> 1}) [1,3,2,1]
go (iw 1 {1 -> 1, 2 -> 1}) [3,2,1]
go (iw 3 {1 -> 2, 2 -> 1}) [2,1]
go (iw 2 {1 -> 2, 2 -> 1, 3 -> 1}) [1]
go (iw 1 {1 -> 2, 2 -> 2, 3 -> 1}) []
iw 1 {1 -> 2, 2 -> 2, 3 -> 1}
{1 -> 3, 2 -> 2, 3 -> 1}

Jouni K. Seppänen 14 年前

因此,您有无限数量的可能结果,并希望计算每个结果在常量内存中出现的次数。这显然是不可能做到的,但是数据结构称为 count-min sketch 可以用来做一个很好的近似。在您的示例中,将结果存储在count min草图中,同时分别跟踪最小值和最大值,并在最后查询从最小到最大的每个整数的count min草图。

Community Egal 7 年前

我通常处理这类问题的方法是跟踪地图上的计数。 Data.IntMap

import qualified Data.IntMap as I

results :: [Int] -> I.IntMap Int
results = foldr (\x -> I.insertWith (+) x 1) I.empty

此时,您可以请求范围的端点( I.findMin I.findMax )或者在O(log n)中查找特定值的计数。为了更快的查找,将所有内容都列在一个数组中也是非常容易的。

luqui's answer 为了得到更好的代码版本。

HaskellElephant jeni 14 年前

正如Jouni已经提到的,持续记忆是不可能的,但是这个CountMin草图听起来像炸弹!(虽然我以前没听说过)。但我想你可能需要的是将它存储在一个数组中,并且只更新每个频率。这可以在haskell中用可变数组实现。下面是一个例子:

main = do gen <- newStdGen
          n <- liftM (read . head) getArgs
          arr  <- (newArray (a,b) 0) :: IO (IOUArray Int Int)
          replicateM_ n $ do 
               result <- myRand
               x <- readArray arr result
               writeArray arr result (x+1)
          (getAssocs arr :: IO [(Int,Int)]) >>= print

用+RTS-s运行程序,输入1000000我们得到输出

787,874,256 bytes allocated in the heap
         364,536 bytes copied during GC
           5,984 bytes maximum residency (1 sample(s))
          17,928 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

...
  Total time    0.29s  (  0.30s elapsed)
...
  %GC time       0.3%  (2.1% elapsed)