Учебник по Haskell

Классификация тестовых случаев

Мы можем попросить у 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