*Test> quickCheck $ (Only4 a) (Only4 b) -> prop1 a b
+++ OK, passed 100 tests.
*Test> quickCheck $ (Only4 a) (OnlyOrange b) -> prop1 a b
+++ OK, passed 100 tests.
*Test> quickCheck $ a (OnlyOrange b) -> prop2 a b
+++ OK, passed 100 tests.
Классификация тестовых случаев
Мы можем попросить у QuickCheck, чтобы он разбил тестовую выборку на классы и в конце тестирования
сообщил бы нам сколько элементов в какой класс попали. Это делается с помощью функции classify:
classify :: Testable prop => Bool -> String -> prop -> Property
Она принимает условие классификации, метку класса и свойство. Например так мы можем разбить вы-
борку по типам линий:
prop3 :: Station -> Station -> Property
prop3 a@(St wa _) b@(St wb _) =
classify (wa == Orange || wb == Orange) ”Orange” $
classify (wa == Black
|| wb == Black)
”Black”
$
classify (wa == Red
|| wb == Red)
”Red”
$ prop1 a b
Протестируем:
*Test> quickCheck prop3
+++ OK, passed 100 tests:
34% Red
15% Orange
9% Black
8% Orange, Red
6% Black, Red
5% Orange, Black
19.3 Оценка быстродействия с помощью criterion
Недавно появилась библиотека unordered—containers. Она предлагает более эффективную реализацию
нескольких структур из стандартной библиотеки containers. Например там мы можем найти тип HashSet.
Почему бы нам не заменить на него стандартный тип Set?
Оценка быстродействия с помощью criterion | 283
cabal install unordered—containers
Изменения отразятся лишь на контекстах объявлений типов. Элементы принадлжежащие множеству
HashSet должны быть экземплярами классов Eq и Hashable. Новый класс Hashable нужен для ускорения
работы с данными. Давайте посмотрим на этот класс:
Prelude> :m Data.Hashable
Prelude Data.Hashable> :i Hashable
class Hashable a where
hash :: a -> Int
hashWithSalt :: Int -> a -> Int
— Defined in ‘Data.Hashable’
…
… много экземпляров
Обязательный метод класса hash даёт нам возможность преобразовать элемент в целое число. Это число
называют хеш-ключом. Хеш-ключи используеются для хранения элементов в хеш-таблицах. Мы не будем
подробно на них останавливаться, отметим лишь то, что они позволяют очень быстро извлекать данные из
контейнеров и обновлять данные.
Теперь просто скопируйте модуль Astar. hs измените одну строчку, и добавьте ещё одну (в шапке моду-
ля):
import qualified Data.HashSet as S
import Data.Hashable
Попробуйте загрузить модуль в интерпретатор. ghci выдаст длинный список ошибок, это – хорошо. По
ним вы сможете легко догадать в каких местах необходимо заменить Ord a на (Hashable a, Eq a).
Теперь для поиска маршрутов нам необходимо определить экземпляр класса Hashable для типа Station.
В модуле Data.Hashable уже определены экземпляры для многих стандартных типов. Мы воспользуемся
экземпляром для целых чисел.
Добавим в driving подчинённых типов класс Enum и воспользуемся им в экземпляре для Hashable:
instance Hashable Station where
hash (St a b) = hash (fromEnum a, fromEnum b)
Теперь определим две функции определения маршрута:
import qualified AstarSet
as S
import qualified AstarHashSet
as H
…
connectSet :: Station -> Station -> Maybe [Station]
connectSet a b = S. search (== b) $ metroTree a b
connectHashSet :: Station -> Station -> Maybe [Station]
connectHashSet a b = H. search (== b) $ metroTree a b
Как нам сравнить быстродействие двух алгоримтов? Оценка быстродействия программ, написанных на
Haskell, может таить в себе подвохи. Например если мы запустим оба алгоритма в одной программе, возмож-
но случится такая ситуация, что часть данных, одинаковая для каждого из методов будет вычислена один
раз, а во втором алгоритме переиспользована, и нам может показаться, что второй алгоритм гораздо быстрее
первого. Также необходимо учитывать внешние факторы. Тестовая программа вычисляется на одном ком-
пьютере, и если алгоритмы тестируются в разное время, может статься так, что мы сидели-сидели и ждали
пока тест завершится, в это время работал первый алгоритм, потом нам надоело ждать, мы решили включить
музыку, проверить почту, и второму алгоритмку досталось меньше вычислительных ресурсов. Все эти фак-
торы необходимо учитывать при тестировании. Как раз для этого и существует замечательная бибилиотека
criterion.
Она проводит серию тестов и по ним оценивает показатели быстродействия. При этом учитывается до-
стоверность тестов. По результатам тестирования показатели сверяются между собой, и если разброс оказы-
вается слишком большим, программа сообщает нам: что-то тут не чисто, данным не стоит доверять. Более
того результаты оформляются в наглядные графики, мы можем на глаз оценить распределения и разброс
показателей.
284 | Глава 19: Ориентируемся по карте
Основные типы criterion
Центральным элементом бибилиотеки является класс Benchmarkable. Он объединяет данные, которые
можно тестировать. Среди них чистые функции (тип Pure) и значения с побочными эффектами (тип IO a).
Мы можем превращать данные в тесты (тип Benchmark) с помощью функции bench:
benchSource :: Benchmarkable b => String -> b -> Benchmark
Она добавляет к данным комментарий и превращает их в тесты. Как было отмечено, существует одна
тонкость при тестировании чистых функций: чистые функции в Haskell могут разделять данные между со-
бой, поэтому для независимого тестирования мы оборачиваем функции в специальный тип Pure. У нас есть
два варианта тестирования:
Мы можем протестировать приведение результата к заголовочной нормальной форме (вспомните главу
о ленивых вычислениях):
nf :: NFData b => (a -> b) -> a -> Pure
или к слабой заголовочной нормальной форме:
whnf :: (a -> b) -> a -> Pure
Аналогичные функции (nfIO, whnfIO) есть и для данных с побочными эффектами. Класс NFData обозна-
чает все значения, для которых заголовочная нормальная форма определена. Этот класс пришёл в бибилио-
теку criterion из библиотеки deepseq. Стоит отметить эту бибилотеку. В ней определён аналог функции
seq. Функция seq приводит значения к слабой заголовочной нормальной форме (мы заглядываем вглюбь
значения лишь на один конструктор), а функция deepseq проводит полное вычисление значения. Значение
приводится к заголовочной нормальной форме.
Также нам пригодится функция группировки тестов:
bgroup :: String -> [Benchmark] -> Benchmark
С её помощью мы объединяем список тестов в один, под некоторым именем. Тестирование проводится с
помощью функции defaultMain:
defaultMain :: [Benchmark] -> IO ()
Она принимает список тестов и выполняет их. Выполнение тестов заключается в компиляции програм-
мы. После компиляции мы получим исполняемый файл который проводит тестирование в зависимости от
параметров, указываемых фланами. До них мы ещё доберёмся, а пока опишем наши тесты:
— | Module: Speed.hs
module Main where
import Criterion.Main
import Control.DeepSeq
import Metro
instance NFData Station where
rnf (St a b) = rnf (rnf a, rnf b)
instance NFData Way
where
instance NFData Name where
pair1 = (St Orange DnoBolota, St Green Prizrak)
pair2 = (St Red Lao, St Blue De)
test name search = bgroup name $ [
bench ”1” $ nf (uncurry search) pair1,
bench ”2” $ nf (uncurry search) pair2]
main = defaultMain [
test ”Set”
connectSet,
test ”Hash” connectHashSet]
