Unknown - haskell-notes

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, мы неизбежно