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

哈斯克尔的“全部”表演

haskell

7

theomega · 技术社区 · 16 年前

我几乎不了解哈斯克尔,试图解决一些项目欧拉问题。解决的同时 Number 5 我写了这个解决方案(1.10)

--Check if n can be divided by 1..max
canDivAll :: Integer -> Integer -> Bool 
canDivAll max n = all (\x ->  n `mod` x == 0) [1..max]

main = print $ head $ filter (canDivAll 10) [1..]

现在我发现了 all 实现方式如下:

all p            =  and . map p

这不意味着每个元素都要检查条件吗?在这种情况的第一个错误结果上突破不是更快吗?这将加快上面代码的执行速度。

谢谢

4 回复 | 直到 11 年前

1

20

viraptor 16 年前

and 它本身是短路的,因为两者都是 map 和 all 评估是懒惰的,您只会得到所需的元素,而不是更多。

您可以使用 GHCi 会议:

Prelude Debug.Trace> and [(trace "first" True), (trace "second" True)]
first
second
True
Prelude Debug.Trace> and [(trace "first" False), (trace "second" False)]
first
False

2

4

kennytm 16 年前

map 之前不计算其所有参数 and 执行。和 和 短路。

注意在GHC中 all 不是这样定义的。

-- | Applied to a predicate and a list, 'all' determines if all elements
-- of the list satisfy the predicate.
all                     :: (a -> Bool) -> [a] -> Bool
#ifdef USE_REPORT_PRELUDE
all p                   =  and . map p
#else
all _ []        =  True
all p (x:xs)    =  p x && all p xs
{-# RULES
"all/build"     forall p (g::forall b.(a->b->b)->b->b) . 
                all p (build g) = g ((&&) . p) True
 #-}
#endif

我们看到了 all p (x:xs) = p x && all p xs 所以,无论何时 p x 如果为假,则评估将停止。

此外,还有一个简化规则 all/build 从而有效地改变 all p [1..max] 进入一个简单的快速失败循环*,所以我认为你不能从修改中得到很多改进。 全部的 .

^{*简化的代码应该如下所示:}

eftIntFB c n x0 y | x0 ># y    = n        
                  | otherwise = go x0
                 where
                   go x = I# x `c` if x ==# y then n else go (x +# 1#)

eftIntFB ((&&) . p) True 1# max#

3

4

Don Stewart 16 年前

这是一个很好的融合优化程序,因为您的所有循环都表示为可融合组合器。因此,您可以使用data.vector等编写它,并比使用列表获得更好的性能。

从n=20开始,在程序中列出:

52.48

此外,使用 rem 而不是 mod .

15712秒

当列表函数变成向量运算时:

import qualified Data.Vector.Unboxed as V

canDivAll :: Int -> Int -> Bool
canDivAll max n = V.all (\x ->  n `rem` x == 0) (V.enumFromN 1 max)

main = print . V.head $ V.filter (canDivAll 20) $ V.unfoldr (\a -> Just (a, a+1)) 1

4

1

Mark Rushakoff 16 年前

你是这么想的 and 不短路。 和 第一次停止执行 false 结果它看到了,所以它是“快速”的,正如人们所预期的。