testFor = forAll (liftA2 (,) gen gen) $ uncurry prop1
where gen = elements [St Blue De, St Red Lao,
St Green Til, St Orange Sever]
Проверим, те ли значения попали в выборку:
282 | Глава 19: Ориентируемся по карте
*Test> verboseCheckWith (stdArgs{ maxSuccess = 3 }) testFor
Passed:
(St Blue De, St Orange Sever)
Passed:
(St Orange Sever, St Red Lao)
Passed:
(St Red Lao, St Red Lao)
+++ OK, passed 3 tests.
Мы можем настроить формирование выборки ещё одним способом. Для этого мы сделаем специальный
тип обёртку над Station и определим для ненго свой экземпляр класса Arbitrary:
newtype OnlyOrange = OnlyOrange Station
newtype Only4
= Only4
Station
instance Arbitrary OnlyOrange where
arbitrary = OnlyOrange . St Orange
elements [DnoBolota, PlBakha, Krest, Lao, Sever]
instance Arbitrary Only4 where
arbitrary = Only4 elements [St Blue De, St Red Lao,
St Green Til, St Orange Sever]
После этого мы можем очень легко комбинировать различные выборки при тестировании.
*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, может таить в себе подвохи. Например если мы запустим оба алгоритма в одной программе, возмож-
но случится такая ситуация, что часть данных, одинаковая для каждого из методов будет вычислена один
раз, а во втором алгоритме переиспользована, и нам может показаться, что второй алгоритм гораздо быстрее
первого. Также необходимо учитывать внешние факторы. Тестовая программа вычисляется на одном ком-
пьютере, и если алгоритмы тестируются в разное время, может статься так, что мы сидели-сидели и ждали
пока тест завершится, в это время работал первый алгоритм, потом нам надоело ждать, мы решили включить
музыку, проверить почту, и второму алгоритмку досталось меньше вычислительных ресурсов. Все эти фак-
торы необходимо учитывать при тестировании. Как раз для этого и существует замечательная бибилиотека