时间戳

首页 > 解决方案 > Haskell QuickCheck 运行缓慢

haskell - Haskell QuickCheck 运行缓慢

问题描述

我正在学习 Haskell，最近在一个小项目上工作，以模仿人类的方式来模拟算术，最终我可以保留尽可能多的小数位，并且计算结果不受浮点精度问题的影响。我也尝试用它QuickCheck来测试我的程序。我遇到的问题是，当我运行 QuickCheck 时，有时它会变得很慢，运行时间很长，并且会消耗大量 CPU 资源。

该程序现在真的很长，所以我将尝试选择最相关的行并在下面重新排列：

data D 
  = D0 | D1 | D2 | D3 | D4 | D5 | D6 | D7 | D8 | D9
  deriving (Enum, Bounded, Eq, Ord, Show)

newtype N = N { getDs :: [D] }

nFromList :: [D] -> N
-- drops leading zeros and make an N value

instance Enum N where
  -- implementation omitted here --

instance Eq N where
  -- implementation omitted here --

instance Ord N where
  -- implementation omitted here --

instance Num N where 
  -- implementation omitted here --

-- this is a fraction data, numerator/denominator/sign
data F = F N N Bool 

getDenom :: F -> N 
getDenom (F _ d _) = d 
-- I can make data F a record but this was written long ago. 
-- And the test case for this runs slowly. 

instance Arbitrary D where
  arbitrary = elements [minBound .. maxBound]

instance Arbitrary N where
  arbitrary = do
    l <- getSize   ---------- impl#1 fast QuickCheck run
    -- l <- choose (0, 10) :: Get Int --------- impl#2 slow QuickCheck run
    ds <- replicateM l arbitrary
    return $ nFromList ds

instance Arbitrary F where
  arbitrary = do
    num <- arbitrary
    denom <- arbitrary
    sign <- arbitrary
    let denom' = max denom 1
    return $ constructF num denom' sign

constructF :: N -> N -> Bool -> F
-- it does some validation on denominator and also reduce the fraction etc.

prop_PosDenom :: F -> Bool
prop_PosDenom f = (getDenom f) > 0

main = do 
  quickCheck prop_PosDenom

问题是，在instance Aribtrary N定义上，如果我使用 impl#1，一切都会很好。测试用例的运行时间不到 1 秒。但是如果我使用 impl#2，它会在不同的点随机挂起，并且运行需要很长时间，该内核的 CPU 使用率为 100%。

我尝试在Debug.Trace任何地方使用和使用它，但它看起来不像在我的代码中的某个地方。似乎 quickCheck 以某种方式生成了两个任意F值，但调用 prop_PosDenom 存在延迟。

提前感谢您的任何建议。

标签： haskellquickcheck

解决方案

我找到了它慢的原因。这是我的代码。没有理由怀疑 QuickCheck。

在我开始研究更多细节之前，因为很多东西都是不久前写的，我假设更简单/更短的输入会比更大/更长的输入运行得更快。这就是为什么我认为getSize可能会以更长的运行时间结束。事实上，在我的代码中，触发一些违规计算的是短数字。

我必须为用于减少分数gcd的类型定义一个函数。N我使用Euclid's Algorithm定义了它，如下所示：

gcdN :: N -> N -> N 
gcdN n m
  | n == 0 || m == 0 = 0
  | n == m = n
  | n > m = gcdN (subN n m) n
  | otherwise = gcdN (subN m n) n

该算法在n >> m或时很慢m >> n，情况正是如此。我的样本测试之一

gcdN (N [D4]) (N [D2, D8, D8, D7, D4, D7, D6, D8, D1, D2])

永远。

在我用Euclidean Algorithm替换它之后，它立即返回。

gcdN :: N -> N -> N
gcdN n m
  | n == 0 = m
  | m == 0 = n
  | m == n = n
  | n > m = case divModN n m of --using my divModN :: N -> N -> Maybe (N, N)
    Nothing -> n -- when m is 0
    Just (q, r) -> gcdN m r
  | otherwise = gcdN m n

我想我从此对 QuickCheck 有了极大的信心。

最大公约数维基页面

推荐阅读