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 могут разделять данные между со-