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