Я написал универсальные функции квантификации exists
, forall
и none
для встроенного в Haskell []
тип данных списка. В нескольких случаях они оказались намного эффективнее, чем Prelude
/Data.List
s any
и all
. Я наивно подозреваю, что эта производительность обусловлена any
и all
реализована с использованием сгибов Θ (n). Поскольку я относительно новичок в Haskell и абстрактные автоматические манипуляторы символов вообще, я думаю, что я должен ошибаться или что это будет веская причина для этого явления.Производительность Haskell/GHC `any` /` all`
От Data.Foldable
:
-- | Determines whether any element of the structure satisfies the predicate.
any :: Foldable t => (a -> Bool) -> t a -> Bool
any p = getAny #. foldMap (Any #. p)
-- | Determines whether all elements of the structure satisfy the predicate.
all :: Foldable t => (a -> Bool) -> t a -> Bool
all p = getAll #. foldMap (All #. p)
Мои реализации:
exists :: (a -> Bool) -> [a] -> Bool
exists _ [] = False
exists pred (x : xs) | pred x = True
| otherwise = exists pred xs
resultive
forall pred = not . exists (not . pred)
none pred = not . exists pred = forall (not . pred)
Устранение булевы инверсиями:
forall, none :: (a -> Bool) -> [a] -> Bool
forall _ [] = True
forall pred (x : xs) | pred x = forall pred xs
| otherwise = False
none _ [] = True
none pred (x : xs) | pred x = False
| otherwise = none pred xs
all
:
time 327.8 μs (322.4 μs .. 333.0 μs)
0.997 R² (0.996 R² .. 0.998 R²)
mean 328.7 μs (324.1 μs .. 334.2 μs)
std dev 16.95 μs (14.63 μs .. 22.02 μs)
и forall
:
time 113.2 μs (111.2 μs .. 115.0 μs)
0.997 R² (0.996 R² .. 0.998 R²)
mean 112.0 μs (110.0 μs .. 113.9 μs)
std dev 6.333 μs (5.127 μs .. 7.896 μs)
Производительность измерялась с использованием критерия-х nf
.
Как и ожидалось, я не изобретал сгиб, но недооценивал флаги компилятора.
Я наивно не ожидал, что -O2
сделает такую резкую общую разницу по сравнению с производительностью уровня оптимизации по умолчанию, а также неравномерность эффективности оптимизации между индивидуальными составами на заказ и библиотекой. Многие высокоэффективные специализированные стандартные функции оптимизации, очевидно, срабатывают только при явной активации.
Раздел «Производительность» информации тега Haskell подчеркивает важность флагов компилятора уровня оптимизации при проверке эффективности кода. Обычно рекомендуется доверять сложности реализации библиотечных функций и вместо того, чтобы перерабатывать прагмы или переформулировать основные формы, чтобы попытаться использовать уже культивируемый потенциал оптимизации.
Если вы хотите узнать о производительности кода на этом уровне, вы, вероятно, должны посмотреть на ядро. Разница в производительности не имеет ничего общего с асимптотикой (как это может быть?), Ваши функции явно O (n)), - думаю, это связано с отсутствием вложения в функции «Складные». Все ваши функции эквивалентны 'foldr f z' для' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' ''. – user2407038
Не могли бы вы поделиться своими ориентирами? –
Я не могу воспроизвести это с помощью простого 'all' /' forall'. Неудивительно, что там, где задействованы плавкие операции, это не конкурс: http://sprunge.us/RQdO Конечно, вы можете написать правила слияния для 'forall' и компании. – Michael