如何在常量内存中获取make stats

Question

我有一个函数,它创建一些随机数值结果.我知道,结果将是a(小,a - b约50)范围a,b的整数.我想创建一个执行上述函数的函数,比方说1000000次并计算每个结果出现的频率.(该函数采用随机生成器来生成结果.)问题是,我不知道如何在常量内存中执行此操作而不对范围的长度进行硬编码.我的(坏)方法是这样的:

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

有人想做这个吗？

编辑:

我想我错了解释了这个问题,对不起.我有一个函数,它取决于一个随机的gen - 给出一些小的int值.为了统计,我想知道结果出现的频率.因为我想制作统计数据让我们说1000000次尝试,我需要在尝试次数上保持不变的记忆.

Answer 1

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

解释为什么这种方法以及为什么它优于Travis Brown的解决方案是非常技术性的,需要一些耐心才能完全理解.

如果列表中可能只出现有限数量的值,那么它将在常量内存中运行.特拉维斯的解决方案有一个微妙的错误,其中生成的地图条目将如下所示:

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

数字19的效率非常低.只有当您在地图中要求该元素时,才会计算出巨大的总和.这些"thunk"(延迟评估表达式)将随输入的大小线性增长.

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

(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在第二个参数中严格意味着您需要在插入可以执行任何工作之前评估要插入的映射.我将使用符号{ 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}

所以,如果你有1,000,000元素的数组,我们必须向下走一路到1,000,000元,开始插入,因此,我们需要在内存中保存先前的999,999元,所以我们可以知道下一步该怎么做.左折叠解决了这个问题:

-- 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}

现在我们可以看到,最后,如果地图中的条目数是有界的,那么它将以恒定的空间和线性时间运行.