Unknown - haskell-notes

Prelude> :m Data.Hashable

Prelude Data.Hashable> :i Hashable

class Hashablea where

hash ::a -> Int

hashWithSalt :: Int ->a -> Int

-- Defined in ‘Data.Hashable’

...

... много экземпляров

Обязательный метод класса hash даёт нам возможность преобразовать элемент в целое число. Это число

называют хеш-ключом. Хеш-ключи используеются для хранения элементов в хеш-таблицах. Мы не будем

подробно на них останавливаться, отметим лишь то, что они позволяют очень быстро извлекать данные из

контейнеров и обновлять данные.

Теперь просто скопируйте модуль Astar.hs измените одну строчку, и добавьте ещё одну (в шапке моду-

ля):

import qualified Data.HashSet asS

import Data.Hashable

Попробуйте загрузить модуль в интерпретатор. ghci выдаст длинный список ошибок, это – хорошо. По

ним вы сможете легко догадать в каких местах необходимо заменить Orda на ( Hashablea, Eqa).

Теперь для поиска маршрутов нам необходимо определить экземпляр класса Hashableдля типа Station.

В модуле Data.Hashableуже определены экземпляры для многих стандартных типов. Мы воспользуемся

экземпляром для целых чисел.

Добавим в driving подчинённых типов класс Enumи воспользуемся им в экземпляре для Hashable:

instance Hashable Station where

hash ( Sta b) =hash (fromEnum a, fromEnum b)

Теперь определим две функции определения маршрута:

import qualified AstarSet

asS

import qualified AstarHashSet

asH

...

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) и значения с побочными эффектами (тип IOa).

Мы можем превращать данные в тесты (тип Benchmark) с помощью функции bench:

benchSource :: Benchmarkableb => String ->b -> Benchmark

Она добавляет к данным комментарий и превращает их в тесты. Как было отмечено, существует одна

тонкость при тестировании чистых функций: чистые функции в Haskellмогут разделять данные между со-

бой, поэтому для независимого тестирования мы оборачиваем функции в специальный тип Pure. У нас есть

два варианта тестирования:

Мы можем протестировать приведение результата к заголовочной нормальной форме (вспомните главу

о ленивых вычислениях):

nf :: NFDatab =>(a ->b) ->a -> Pure

или к слабой заголовочной нормальной форме:

whnf ::(a ->b) ->a -> Pure

Аналогичные функции (nfIO, whnfIO) есть и для данных с побочными эффектами. Класс NFDataобозна-

чает все значения, для которых заголовочная нормальная форма определена. Этот класс пришёл в бибилио-