Оценка быстродействия с помощью criterion | 285
Экземпляр для класса NFData похож на экземпляр для Hashable. Мы также определили метод значения
через методы для типов, из которых он состоит. Класс NFData устроен так, что для типов из класса Enum мы
можем воспользоваться определением по умолчанию (как в случае для Way и Name).
Теперь перейдём в командную строку, переключимся на директорию с нашим модулем и скомпилируем
его:
$ ghc -O —make Speed.hs
Флаг -O говорит ghc, что не обходимо провести оптимизацию кода. Появится исполняемый файл Speed.
Что мы можем делать с этим файлом? Узнать это можно, запустив его с флагом –help:
Мы можем узнать какие функции нам доступны, набрав:
$ ./Speed —help
I don’t know what version I am.
Usage: Speed [OPTIONS] [BENCHMARKS]
-h, -?
—help
print help, then exit
-G
—no-gc
do not collect garbage between iterations
-g
—gc
collect garbage between iterations
-I CI
—ci=CI
bootstrap confidence interval
-l
—list
print only a list of benchmark names
-o FILENAME
—output=FILENAME
report file to write to
-q
—quiet
print less output
—resamples=N
number of bootstrap resamples to perform
-s N
—samples=N
number of samples to collect
-t FILENAME
—template=FILENAME
template file to use
-u FILENAME
—summary=FILENAME
produce a summary CSV file of all results
-V
—version
display version, then exit
-v
—verbose
print more output
If no benchmark names are given, all are run
Otherwise, benchmarks are run by prefix match
Из этих настроек самые интресные, это —s и —o. —s указывает число сэмплов выборке (столько раз будет
запущен каждый тест). а —o говорит, о том в какой файл поместить результаты. Результаты представлены в
виде графиков, формируется файл, который можно открыть в любом браузере. Записать данные в таблицу
(например для отчёта) можно с помощью флага —u.
Проверим результаты:
./Speed —o res. html —s 100
Откроем файл res. html и посмотрим на графики. Оказалось, что для данных двух случаев первый алго-
ритм работал немного лучше. Но выборку из двух вариантов вряд ли можно считать убедительной. Давайте
расширим выборку с помощью QuickCheck. Мы запустим проверку какого-нибудь свойства тем и другим
методом. В итоге 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, мы неизбежно
