Производительность “всех” в haskell
Я не получил почти знания haskell и попытался решить некоторые Euler проблемы Проекта. При решении Номера 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 ответа
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
Вы предполагаете, что и не замыкаются. и остановят выполнение при первом ложном результате, которое он увидит, поэтому он будет «быстрым», как и следовало ожидать.
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] в простой безотказный цикл*, поэтому я не думаю, что вы сможете сильно улучшить ситуацию, изменив all.
*. Упрощенный код должен выглядеть так:
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#
Это хорошая программа для оптимизации слияния, поскольку все ваши циклы выражены как плавкие комбинаторы. Таким образом, вы можете написать его, например, Data.Vector и получите лучшую производительность, чем со списками.
От N = 20, со списками, как в вашей программе:
- 52.484s
Также используйте rem вместо mod .
- 15.712s
Где функции списка становятся векторными операциями:
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