Блог

Главная - Вопросы по программированию - Почему быстрая проверка занимает много времени при тестировании экземпляра функтора с сигнатурой определенного типа?

Почему быстрая проверка занимает много времени при тестировании экземпляра функтора с сигнатурой определенного типа?

#performance #haskell #quickcheck

#Производительность #haskell #быстрая проверка

Вопрос:

Я работаю над замечательной книгой Haskell. Решая некоторые упражнения, я запустил тест QuickCheck, выполнение которого заняло относительно много времени, и я не могу понять, почему.

Упражнение, которое я решаю, находится в главе 16 — мне нужно написать Functor экземпляр для

 data Parappa f g a = 
  DaWrappa (f a) (g a)

Вот ссылка на полный код моего решения. Часть, которую я считаю актуальной, заключается в следующем:

 functorCompose' :: (Eq (f c), Functor f) 
                => Fun a b -> Fun b c -> f a -> Bool
functorCompose' fab gbc x =
  (fmap g (fmap f x)) == (fmap (g . f) x)
  where f = applyFun fab
        g = applyFun gbc

type ParappaComp = 
     Fun Integer String 
  -> Fun String [Bool] 
  -> Parappa [] Maybe Integer
  -- -> Parappa (Either Char) Maybe Integer
  -> Bool


main :: IO ()
main = do
  quickCheck (functorCompose' :: ParappaComp)

Когда я запускаю это в REPL, для завершения требуется ~ 6 секунд. Если я переключусь ParappaComp на использование Either Char вместо [] (см. Комментарий в коде), он завершается мгновенно, как я привык видеть во всех других упражнениях.

Я подозреваю, что, возможно, QuickCheck использует очень длинные списки, из-за чего тест занимает много времени, но я недостаточно знаком со средой, чтобы отлаживать это или проверять эту гипотезу.

  1. Почему это занимает так много времени?
  2. Как мне следует приступить к отладке этого?

Комментарии:

1. [] это список . Произвольный список может содержать произвольное количество элементов, что означает, что для выполнения сопоставления по всему списку может потребоваться некоторое время. Для an Either это один элемент.

2. Также похоже, что произвольные Fun s, которые принимают списки, включая String s, работают очень медленно. Переключите промежуточный тип с String на Char , и он быстро завершится.

3. @K.A.Buhr, я попробовал это, и ты прав! Можете ли вы подробнее рассказать о том, как вы узнали?

4. Никакого особого понимания — я просто повозился с вашим примером для bit и обнаружил, что String это проблема. Затем я протестировал Fun s с аргументами списка изолированно и увидел, что они работают довольно плохо.

Ответ №1:

Я подозреваю, что, возможно, QuickCheck использует очень длинные списки, из-за чего тест занимает много времени, но я недостаточно знаком со средой, чтобы отлаживать это или проверять эту гипотезу.

Я также не уверен в фактической причине, но один из способов начать отладку — использовать collect функцию из QuickCheck для сбора статистики о тестовых примерах. Для начала вы можете собрать размер результата.

  • Простой способ получить размер — использовать length функцию, требующую, чтобы функтор f был Foldable
  • Вам нужно будет реализовать или вывести Foldable for Parappa (добавить {-# LANGUAGE DeriveFoldable #-} в начало файла, добавить deriving Foldable в Parappa )
  • Для использования collect вам необходимо обобщить Bool на Property (в сигнатуре functorCompose' и в синониме типа ParappaComp )
 functorCompose' :: (Eq (f c), Functor f, Foldable f) 
               => Fun a b -> Fun b c -> f a -> Property
functorCompose' fab gbc x =
  collect (length x) $
    (fmap g (fmap f x)) == (fmap (g . f) x)
  where f = applyFun fab
        g = applyFun gbc

При этом вы можете видеть, что распределение длин сгенерированных списков кластеризуется около 20 с длинным хвостом до 100. Это само по себе, похоже, не объясняет медлительность, поскольку можно было бы ожидать, что обход списков такого размера должен быть практически мгновенным.