методом. В итоге QuickCheck сам сгенерирует достаточное число случайных данных, а criterion оценит
быстродействие. Мы проверим самое первое свойство (о перевёрнутых маршрутах) на том и другом алгорит-
ме.
module Main where
import Control.Applicative
import Test.QuickCheck
import Metro
instance Arbitrary Station where
arbitrary = ($ s0) . foldr (. ) id . fmap select ints
where ints = vector =<< choose (0, 100)
s0 = St Blue De
select :: Int -> Station -> Station
select i s = as !! mod i (length as)
where as = fst distMetroMap s
prop :: (Station -> Station -> Maybe [Station])
-> Station -> Station -> Bool
286 | Глава 19: Ориентируемся по карте
prop search a b = search a b == (reverse search b a)
main = defaultMain [
bench ”Set”
$ quickCheck (prop connectSet),
bench ”Hash” $ quickCheck (prop connectHashSet)]
В этом тесте метод Set также оказался совсем немного быстрее.
Как интерпретировать результаты? С левой стороны мы видим оценку плотности вероятности распреде-
ления быстродействия. Под графиком мы видим среднее (mean) и дисперсию значения (std dev). Показаны
три числа. Это нижняя грань доверительного интервала, оценка величины и верхняя грань доверительного
интервала (ci, confidence interval). Среднее значение показывает оценку величины, мы говорим, что алго-
ритм работает примерно 100 миллисекунд. Дисперсия – это разброс результатов вокруг среднего значения.
С правой стороны мы видим графики с точками. Каждая точка обозначает отдельный запуск алгоритма.
Количество запусков соответствует флагу —s. В последнеё строке под графиком criterion сообщает степень
недоверия к результатам. В последнем опыте этот показатель достаточно высок. Возможно это связано с тем,
что наш алгоритм выбора случайных станций имеет сильный разброс по времени. Ведь сначала мы генери-
руем слуайное число n от 0 до 100, и затем начинаем блуждать по карте от начальной точке n раз. Также
может влиять то, что время работы алгоритма зависит от положения станций.
19.4 Краткое содержание
В этой главе мы реализовали алгоритм эвристического поиска А*. Также мы узнали несколько стандарт-
ных структур данных. Это множества и очереди с приоритетом и освежили в памяти ленивые вычисления.
Мы научились проверять свойства программ (QuickCheck), а также оценивать быстродействие программ
(criterion).
19.5 Упражнения
• Я говорил о том, что два варианта алгоритмов дают одинаковые результаты, но так ли это на самом
деле? Проверьте это в QuickCheck.
• Алгоритм эвристического поиска может применятся не только для поиска маршрутов на карте. Часто
алгоритм А* применяется в играх. Встройте этот алгоритм в игру пятнашки (глава 13). Если игрок за-
путался и не знает как ходить, он может попросить у компьютера совет. В этой задаче альтернативы~–
это вершины графа, соседние вершины~– это те вершины, в которые мы можем попасть за один ход.
Подсказка: воспользуйтесь манхэттенским расстоянием.
• Оцените эффективность двух алгоритмов поиска в игре пятнашки. Рассмотрите зависимость быстро-
действия от степени сложности игры.
Краткое содержание | 287
Глава 20
Императивное программирование
В этой главе мы потренируемся в укрощении императивного кода. В Haskell все побочные эффекты огоро-
жены от чистых функций бетонной стеной IO. Однажды оступившись, мы не можем свернуть с пути побочных
эффектов, мы вынуждены тащить на себе груз IO до самого конца программы. Тип IO, хоть и обволакивает
программу, всё же позволяет пользоваться благами чистых вычислений. От программиста зависит насколь-
ко сильна будет хватка IO. Необходимо уметь выделять точки, в которых применение побочных вычислений
действительно необходимо, подключая в них чистые функции через методы классов Functor, Applicative
и Monad. Тип IO похож на дорогу с контрольными пунктами, в которых необходимо отчитаться перед ком-
пилятором за “грязный код”. При неумелом проектировании написание программ, насыщенных побочными
эффектами, может превратится в пытку. Контрольные пункты будут встречаться в каждой функции.
Естественный источник побочных эффектов – это пользователь программы. Но, к сожалению, это не един-
ственный источник. Haskell – открытый язык программирования. В нём можно пользоваться программами
из низкоуровневого языка C. Основное преимущество С заключается в непревзойдённой скорости программ.
Этот язык позволяет программисту работать с памятью компьютера напрямую. Но за эту силу приходится
платить. Возможны очень неприятные и трудноуловимые ошибки. Утечки памяти, обращение по неверному
адресу в памяти, неожиданное обновление переменных. Ещё один плюс С в том, что это язык с историей,
на нём написано много хороших библиотек. Некоторые из них встроены в Haskell с помощью специального
механизма FFI (foreign function interface). Обсуждение того, как устроен FFI выходит за рамки этой книги. Ин-
тересующийся читатель может обратиться к книге Real World Haskell. Мы же потренируемся в использовании
таких библиотек. Язык C является императивным, поэтому, применяя его функций в Haskell, мы неизбежно
сталкиваемся с типом IO, поскольку большинство интересных функций в С изменяют состояние своих аргу-