Главная Алгоритмы. Справочник с примерами на C, C++, Java и Python

Алгоритмы. Справочник с примерами на C, C++, Java и Python

, ,
0 / 0
How much do you like this book?
What’s the quality of the file?
Download the book for quality assessment
What’s the quality of the downloaded files?
Для создания надежного программного обеспечения необходимы эффективные алгоритмы, но программисты редко представляют себе весь спектр алгоритмов для решения своих задач.
В данном обновленном издании описываются существующие алгоритмы для решения различных задач. Оно помогает выбрать и реализовать алгоритм, наиболее подходящий для ваших задач, при этом обеспечивая достаточное математическое обоснование для понимания и анализа производительности алгоритма.
Будучи акцентированной на приложениях, а не на теории, эта книга основана на строгих принципах, включая документированные решения реальных задач на разных языках программирования. В это издание добавлены десяток новых алгоритмов, реализованных на языке Python, в том числе реализация диаграмм Вороного, а также новая глава о пространственных древовидных структурах, таких как R-деревья и Quadtrees.

В этой книге вы научитесь:
• Решать новые задачи и повышать эффективность имеющихся решений
• Быстро находить алгоритмы для решения своих задач и выбирать наиболее подходящие
• Находить решения на языках программирования C, C++, Java, Python с помощью рекомендаций из книги
• Оценивать производительность алгоритмов и создавать условия для достижения максимальной эффективности
• Использовать наиболее подходящие структуры данных для повышения эффективности алгоритмов
Год:
2017
Издание:
2
Издательство:
ООО "Альфа-книга"
Язык:
russian
Страницы:
432 / 434
ISBN 13:
9785990891074
Файл:
PDF, 24,99 MB

Возможно Вас заинтересует Powered by Rec2Me

 

Ключевые фразы

 
0 comments
 

To post a review, please sign in or sign up
Вы можете оставить отзыв о книге и поделиться своим опытом. Другим читателям будет интересно узнать Ваше мнение о прочитанных книгах. Независимо от того, пришлась ли Вам книга по душе или нет, если Вы честно и подробно расскажете об этом, люди смогут найти для себя новые книги, которые их заинтересуют.
1

Design Patterns in Fluid Construction Grammar

Year:
2011
Language:
english
File:
PDF, 6.28 MB
0 / 0
2

Introduction to Robotics: Analysis, Control, Applications

Year:
2010
Language:
english
File:
PDF, 8.09 MB
0 / 0
Алгоритмы
Справочник
Второе издание

Algorithms
in a Nutshell
Second Edition

George T. Heineman,
Gary Pollice
& Stanley Selkow

Beijing • Boston • Farnham • Sebastopol «Tokyo

O'REILLY

Алгоритмы
Справочник
С ПРИМЕРАМИ НА С, C++, JAVA И PYTHON
Второе издание

Джордж Хайнеман
Гэри Поллис
Стэнли Селков

М о с к в а • С а н к т-П е те р б у р г • К и ев

2017

ББК 32.973.26-018.2.75
Х15
УДК 681.3.07
Издательство “Диалектика”
Зав. редакцией С.Н. Тригуб
Перевод с английского и редакция канд. техн. наук И.В. Красикова
По общим вопросам обращайтесь в издательство “Диалектика” по адресу:
info@dialektika.com, http://www. dialektika.com

X I5

Хайнеман, Джордж, Пояяис, Гэри, Сеяков, Стэнли.
Алгоритмы. Справочник с примерами на С, C++, Java и Python, 2-е изд.: Пер.
с англ. — С пБ .: ООО “Альфа-книга”, 2017. — 432 с . : ил. — Парал. тит. англ.
ISBN 978-5-9908910-7-4 (рус.)
ББК 32.973.26-018.2.75
Все названия программных продуктов являются зарегистрированными торговыми марками соответ­
ствующих фирм.
Никакая часть настоящего издания ни в каких целях не может быть воспроизведена в какой бы то ни
было форме и какими бы то ни было средствами, будь то электронные или механические, включая ф о­
токопирование и запись на магнитный носитель, если на это нет письменного разрешения издательства
O’Reilly & Associates.
Authorized Russian translation of the English edition of Algorithms in a Nutshell 2nd edition (ISBN 978-1-49194892-7) © 2016 George Heineman, Gary Pollice and Stanley Selkow.
This translation is published and sold by permission of O’Reilly Media, Inc., which owns or controls all rights
to publish and sell the same.
All rights reserved. No part of this work may be reproduced or transmitted in any form or by any means,
electronic or mechanical, including photocopying, recording, or by any information storage or retrieval system,
without the prior written permission of the copyright owner and the Publisher.

Научно-популярное издание
Джордж Хайнеман, Гэри Пояяис, Стэняи Сеяков

А л го р и тм ы
С п р а в о ; ч н и к с п р и м ер ам и н а С, C++, Java и P y th o n
2-е издание
Литературный редактор

Л.Н. Красножон
О.В. Мишутина

Верстка
Художественный редактор

В.Г. Павлютин

Корректор

Л.А. Гордиенко

Подписано в печать 12.04.2017. Формат 70x100/16.
Гарнитура Times.
Уел. печ. л. 27,0. Уч.-изд. л. 23,3.
Тираж 300 экз. Заказ
2767.
Отпечатано в АО «Первая Образцовая типография»
Филиал «Чеховский Печатный Двор»
142300, Московская область, г. Чехов, ул. Полиграфистов, д.1
Сайт: www.chpd.ru, E-mail: sales@chpd.ru, тел. 8(499)270-73-59
ООО “Альфа-книга”, 195027, Санкт-Петербург, Магнитогорская ул., д. 30
ISBN 978-5-9908910-7-4 (рус.)
ISBN 978-1-491-94892-7 (англ.)

© 2017 Компьютерное издательство “Диалектика”,
перевод, оформление, макетирование
© 2016 George Heineman, Gary Pollice and Stanley Selkow

Оглавление

Предисловие ко второму изданию

15

Глава 1. Мысли алгоритмически

21

Глава 2. Математика алгоритмов

29

Глава 3. Строительные блоки алгоритмов

57

Глава 4. Алгоритмы сортировки

77

Глава 5. Поиск

119

Глава 6. Алгоритмы на графах

165

Глава 7. Поиск путей в ИИ

205

Глава 8. Алгоритмы транспортных сетей

257

Глава 9. Вычислительная геометрия

289

Глава 10. Пространственные древовидные структуры

331

Глава 11. Дополнительные категории алгоритмов

375

Глава 12. Эпилог: алгоритмические принципы

397

Приложение. Хронометраж

409

Литература
Предметный указатель

421
425

Содержание

Предисловие ко второму изданию

15

Изменения во втором издании
Целевая аудитория
Соглашения, используемые в данной книге
Использование примеров кода
Благодарности
Об авторах
Об изображении на обложке
Ждем ваших отзывов!

15
16
17
18
18
19
19
20

Глава 1. М ысли алгоритмически

21

Понимание проблемы
Прямое решение
Интеллектуальные подходы
Жадный подход
Разделяй и властвуй
Параллельное вычисление
Приближение
Обобщение
Резюме

21
23
23
24
25
25
25
26
28

Глава 2. Математика алгоритмов

29

Размер экземпляра задачи
Скорость роста функций
Анализ наилучшего, среднего и наихудшего случаев
Наихудший случай
Средний случай
Наилучший случай
Нижняя и верхняя границы
Семейства производительности
Константное поведение
Логарифмическое поведение

29
30
34
37
37
38
39
40
40
41

Сублинейное поведение
Линейная производительность
Линейно-логарифмическая производительность
Квадратичная производительность
Менее очевидные производительности
Экспоненциальная производительность
Резюме по асимптотическому росту
Эталонные операции

43
44
47
47
49
52
53
53

Глава 3. Строительные блоки алгоритмов

57

Формат представления алгоритма
Название и краткое описание
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Формат шаблона псевдокода
Формат эмпирических оценок
Вычисления с плавающей точкой
Производительность
Ошибка округления
Сравнение значений с плавающей точкой
Специальные значения
Пример алгоритма
Название и краткое описание
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Распространенные подходы
Жадная стратегия
Разделяй и властвуй
Динамическое программирование

58
58
58
58
58
58
59
59
60
60
61
61
62
64
64
65
65
65
66
69
69
69
70
71

Глава 4. Алгоритмы сортировки

77

Терминология
Представление
Сравниваемость элементов
Устойчивая сортировка
Критерии выбора алгоритма сортировки
Сортировки перестановкой
Сортировка вставками

77
78
79
80
81
81
81
Содержание

7

Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Сортировка выбором
Пирамидальная сортировка
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Сортировка, основанная на разбиении
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Сортировка без сравнений
Блочная сортировка
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Сортировка с использованием дополнительной памяти
Сортировка слиянием
Входные и выходные данные алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Результаты хронометража для строк
Анализ методов

83
83
84
86
87
91
91
93
93
93
97
98
99
99
101
101
103
106
107
109
109
110
110
111
112
114
116

Глава 5. Поиск

119

Последовательный поиск
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Бинарный поиск
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Поиск на основе хеша
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма

120
121
121
122
123
124
124
124
125
127
128
129
131
131
135

8

|

Содержание

Анализ алгоритма
Вариации алгоритма
Фильтр Блума
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Бинарное дерево поиска
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма

137
140
146
147
148
148
149
150
151
152
153
163
163

Глава 6. Алгоритмы на графах

165

Графы
Проектирование структуры данных
Поиск в глубину
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Поиск в ширину
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Кратчайший путь из одной вершины
Входные и выходные данные алгоритма
Реализация алгоритма
Анализ алгоритма
Алгоритм Дейкстры для плотных графов
Вариации алгоритма
Сравнение вариантов поиска кратчайших путей из одной вершины
Данные хронометража
Плотные графы
Разреженные графы
Кратчайшие пути между всеми парами вершин
Входные и выходные данные алгоритма
Реализация алгоритма
Анализ алгоритма

Содержание

166
169
169
173
174
174
175
175
175
177
178
178
179
180
183
183
184
185
188
191
191
192
192
193
193
195
198

|

9

Алгоритмы построения минимального остовного дерева
Входные и выходные данные алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Заключительные мысли о графах
Вопросы хранения
Анализ графа

198
200
200
202
202
202
203
203

Глава 7. Поиск путей в ИИ

205

Дерево игры
Функции статических оценок
Концепции поиска путей
Представление состояния
Вычисление доступных ходов
Максимальная глубина расширения
Minimax
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
NegMax
Реализация алгоритма
Анализ алгоритма
AlphaBeta
Реализация алгоритма
Анализ алгоритма
Деревья поиска
Эвристические функции длины пути
Поиск в глубину
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Поиск в ширину
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
A*Search
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма

206
209
210
210
211
211
211
213
214
214
217
217
219
221
221
225
227
229
232
232
233
234
234
236
238
239
240
240
242
242
244
244
247

10

|

Содержание

Анализ алгоритма
Вариации алгоритма
Сравнение алгоритмов поиска в дереве

251
252
254

Глава 8. Алгоритмы транспортных сетей

257

Транспортная сеть
Максимальный поток
Входные и выходные данные алгоритма
Реализация алгоритма
Анализ алгоритма
Оптимизация
Связанные алгоритмы
Паросочетания в двудольном графе
Входные и выходные данные алгоритма
Реализация алгоритма
Анализ алгоритма
Размышления об увеличивающих путях
Поток минимальной стоимости
Перегрузка
Реализация алгоритма
Перевозка
Реализация алгоритма
Назначение
Реализация алгоритма
Линейное программирование

258
260
261
261
270
270
273
274
274
275
278
278
283
284
285
285
287
287
287
287

Глава 9. Вычислительная геометрия

289

Классификация задач
Входные данные
Вычисления
Природа задачи
Предположения
Выпуклая оболочка
Сканирование выпуклой оболочки
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Вычисление пересечения отрезков
LineSweep
Входные и выходные данные алгоритма
Контекст применения алгоритма

290
290
292
293
293
294
295
296
297
298
300
301
304
305
306
306
Содержание

|

11

Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Диаграмма Вороного
Входные и выходные данные алгоритма
Реализация алгоритма
Анализ алгоритма

308
313
316
316
322
322
329

Глава 10. Пространственные древовидны е структуры

331

Запросы ближайшего соседа
Запросы диапазонов
Запросы пересечения
Структуры пространственных деревьев
k-d-церевъя
Дерево квадрантов
R-дерево
Задача о ближайшем соседе
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
Запрос диапазона
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма
Деревья квадрантов
Входные и выходные данные алгоритма
Реализация алгоритма
Анализ алгоритма
Вариации алгоритма
R-деревья
Входные и выходные данные алгоритма
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма

332
333
333
334
334
335
336
337
339
339
340
343
348
348
349
349
350
352
355
357
357
361
361
362
366
366
366
372

Глава 11. Дополнительные категории алгоритмов

375

Вариации на тему алгоритмов
Приближенные алгоритмы
Контекст применения алгоритма
Реализация алгоритма
Анализ алгоритма

375
376
378
378
380

12

|

Содержание

Параллельные алгоритмы
Вероятностные алгоритмы
Оценка размера множества
Оценка размера дерева поиска

382
387
388
390

Глава 12. Эпилог: алгоритмические принципы

397

Используемые данные
Разложение задачи на задачи меньшего размера
Выбор правильной структуры данных
Пространственно-временной компромисс
Построение поиска
Приведение задачи к другой задаче
Тестировать алгоритмы труднее, чем писать
Допустимость приближенных решений
Повышение производительности с помощью параллелизма

397
398
400
401
402
403
404
406
406

Приложение. Хронометраж

409

Статистические основы
Пример
Решение для Java
Решение для Linux
Хронометраж с использованием Python
Вывод результатов
Точность

409
411
411
412
416
417
419

Литература

421

Предметный указатель

425

Содержание

|

13

Предисловие
ко второму изданию
Пересматривать содержание книги для нового издания всегда сложно. Мы стара­
лись сохранить все достоинства первого издания, опубликованного в 2009 году, но
при этом исправить его недостатки и добавить новые материалы. Мы по-прежнему
следовали принципам, изложенным в первом издании.
•

Использовать для описания алгоритмов только реальный код, а не псевдокод.

•

Отделять алгоритм от решаемой им задачи.

•

Использовать только необходимое количество математических выкладок, и не
более того.

•

Сопровождать математический анализ эмпирическими данными.

Во втором издании мы сократили текстовые описания и упростили макет кни­
ги, чтобы освободить место для новых алгоритмов и дополнительных материалов.
Мы считаем, что, как и ранее, нам удалось достаточно полно рассказать читателям
о важной области информатики, которая оказывает значительное влияние на прак­
тические программные системы.

Изменения во втором издании
При обновлении предыдущего издания мы руководствовались следующими
принципами.
Выбор новых алгоритмов
После публикации первого издания мы часто получали письма с комментари­
ями наподобие “А почему в книге нет сортировки слиянием?” или “Почему вы
ничего не рассказали о быстром преобразовании Фурье?” Все запросы удов­
летворить попросту невозможно, но мы сумели добавить во второе издание
несколько новых алгоритмов.

•

Алгоритм Форчуна для вычисления диаграммы Вороного для множества то­
чек (см. раздел “Диаграмма Вороного” главы 9, “Вычислительная геометрия”).

•

Сортировка слиянием как для внутренней памяти, так и для внешних файлов
(см. раздел “Сортировка слиянием” главы 4, “Алгоритмы сортировки”).

•

Многопоточная версия быстрой сортировки (см. раздел “Параллельные алго­
ритмы” главы 11, “Дополнительные категории алгоритмов”).

•

Реализация сбалансированных бинарных AVL-деревьев (см. раздел “Бинар­
ное дерево поиска” главы 5, “Поиск”).

•

Новая глава — глава 10, “Пространственные древовидные структуры”, содер­
жащая описания R-Trees и Quadtrees.
В целом сейчас в книге охвачено около 40 важных алгоритмов.

Упорядоченное представление
Чтобы освободить место для нового материала, мы пересмотрели почти каж­
дый аспект первого издания. Мы упростили шаблон, используемый для опи­
сания каждого алгоритма, и сократили сопутствующие описания алгоритмов.
Добавление реализаций на языке Python
Вместо того чтобы переписывать существующие алгоритмы на языке Python,
мы преднамеренно использовали Python для реализации большинства добав­
ленных вновь алгоритмов.
Управление кодом
Исходные тексты для первого издания были представлены в виде ZIP-файла.
С тех пор мы перешли к хранилищу GitHub (https://github.com/heineman/
algorithms-nutshell-2ed). За прошедшие годы мы улучшили качество кода
и документации. Мы также включили ряд записей из блога, которые были
написаны после публикации первого издания. Кроме того, добавлено более
500 модульных контрольных примеров. В целом весь представленный в репо­
зитории код состоит более чем из 110 тысяч строк.

Целевая аудитория
Мы позиционируем эту книгу как основной источник при поиске практической
информации о том, как реализовать или использовать тот или иной алгоритм. Мы
охватываем широкий диапазон существующих алгоритмов для решения большого
количества проблем и при этом придерживаемся следующих принципов.
•

16

При описании каждого алгоритма мы используем шаблон для единообразного
описания и пояснения важных мест каждого алгоритма.

|

Предисловие ко второму изданию

•

Мы используем различные языки программирования для реализации каждого
алгоритма (включая С, C++, Java и Python). При этом мы обсуждаем конкрет­
ные реализации алгоритмов на языках, с которыми вы знакомы.

•

Мы описываем ожидаемую производительность каждого алгоритма и предо­
ставляем эмпирические доказательства наших утверждений.

Мы писали книгу так, чтобы она была наиболее полезной для практиков програм­
мирования — программистов и проектировщиков программного обеспечения. Для
достижения своих целей вам необходим доступ к качественному ресурсу, который
подсказывает реальные реализации практических алгоритмов, которые нужны для ре­
шения конкретных задач. Вы умеете программировать на различных языках програм­
мирования; знаете об основных структурах данных, таких как массивы, связанные
списки, стеки, очереди, хеш-таблицы, бинарные деревья и ориентированные и неори­
ентированные графы. Вам не нужно реализовывать эти структуры данных, поскольку
они обычно предоставляются библиотеками. Так что мы ожидаем, что вы будете ис­
пользовать эту книгу, чтобы узнать о проверенных эффективных решениях стоящих
перед вами задач. Вы узнаете о некоторых новых структурах данных и новых способах
их применения для повышения эффективности алгоритмов. Ваши способности к эф­
фективному решению стоящих перед вами задач, несомненно, повысятся, после того
как вы познакомитесь с материалами, представленными в нашей книге.

Соглашения, используемые в данной книге
В книге использованы следующие типографские соглашения.
Код
Все исходные тексты в книге набраны данным шрифтом.
Этот код скопирован непосредствен но из репозитория и отражает
реальный код. Все листинги книги отформатированы так, чтобы
подчеркнуть синтаксис соответствующ его языка программирования.

Курсив
Указывает ключевые термины, используемые для описания алгоритмов
и структур данных, а также важных концепций.
Моноширинный шрифт

Указывает имена фактических элементов программного обеспечения в реали­
зации, такие как классы Java, имена массивов С или, скажем, такие константы,
как true или false.
Все URL в книге проверены по состоянию на январь 2016 года, и мы постара­
лись использовать только те URL, которые были корректны в течение длительного
Предисловие ко второму изданию

|

17

времени. Короткие URL, например http://www.oreilly.com,приводятся непосред­
ственно в тексте, длинные — в примечаниях или в списке литературы.

Использование примеров кода
Эта книга написана, чтобы помочь вам выполнить свою работу. В общем случае вы
можете использовать примеры кода из нее в своих программах и документации. Вам не
нужно связываться с издательством для получения разрешения, если только вы не вос­
производите значительную часть кода. Например, для написания программы, в которой
используется несколько фрагментов кода из этой книги, разрешение не нужно. Однако
для продажи или распространения на CD-ROM примеров из книг издательства O'Reilly
необходимо отдельное разрешение. Используя ссылку на книгу и пример кода в ответе
на вопрос, получать разрешение не нужно. Но оно необходимо при включении значи­
тельного объема кода из этой книги в документацию своего продукта.
Мы не требуем точного указания источника при использовании примеров кода,
но были бы признательны за него. Обычно достаточно названия книги, фамилии ав­
тора, названия издательства и ISBN.
Если вы полагаете, что использование примеров кода выходит за рамки опи­
санных разрешений, не постесняйтесь связаться с нами по адресу permissions®

oreilly.com.

Благодарности
Мы хотели бы поблагодарить рецензентов книги за их внимание и предложения, ко­
торые позволили улучшить текст и устранить недочеты предыдущих проектов. По пер­
вому изданию это Алан Дэвидсон (Alan Davidson), Скот Дрисдейл (Scot Drysdale), Кшиш­
тоф Дулеба (Krzysztof Duleba), Джин Хьюз (Gene Hughes), Мурали Мани (Murali Mani),
Джеффри Ясскин (Jeffrey Yasskin) и Дэниэль Ю (Daniel Yoo). По второму изданию —
Алан Солис (Alan Solis), Роберт Дэй (Robert P.J. Day) и Скот Дрисдейл (Scot Drysdale).
Джордж Хайнеман хотел бы поблагодарить тех, кто привил ему страсть к алго­
ритмам, включая профессора Скота Дрисдейла (Scot Drysdale) из Дартмутского кол­
леджа и Цви Галила (Zvi Galil) из Колумбийского университета. Как всегда, Джордж
благодарит жену Дженнифер и детей Николя (Nicholas) (который как раз начал
учиться программировать) и Александра (Alexander) (который любит делать оригами
из черновиков этого издания).
Гэри Поллис (Gary Pollice) хотел бы поблагодарить свою жену Викки за 46 отлич­
ных лет. Он также благодарен кафедре информатики Вустерского политехнического
института за прекрасную атмосферу.
Стэнли Селков (Stanley Selkow) хотел бы поблагодарить свою жену Деб. Эта кни­
га — еще один шаг на их длинном совместном пути.

18

|

Предисловие ко второму изданию

Об авторах
Джордж Т. Хайнеман является адъюнкт-профессором информатики в Вустерском
политехническом институте. Его научные интересы находятся в области программной
инженерии и модульного синтеза программных систем. Он является соредактором
книги Component-Based Software Engineering: Putting the Pieces Together (Addison-Wesley).
Помимо этого, Джордж — страстный любитель головоломок. Он изобрел Суджикен
(Sujiken) — вариацию судоку с расположением ячеек в прямоугольном треугольни­
ке, в котором числа не могут повторяться в горизонтали, вертикали или диагонали
в любом направлении. Среди опубликованных им книг — Sudoku on the Half Shell: 150
Addictive SujikenR Puzzles (Puzzlewright Press, 2011).
Гэри Поллис сам себя называет старым грубияном, который 35 с лишним лет про­
работал в промышленности, пытаясь выяснить, кем бы он хотел стать, когда вырастет.
Несмотря на то что он пока что так и не вырос, в 2003 году он перешел в священные лек­
ционные аудитории, дабы развращать умы следующего поколения разработчиков про­
граммного обеспечения такими радикальными идеями, как “разработка программного
обеспечения для потребителя”, “как работать в команде”, “дизайн, качество, элегантность
и правильность кода” и “легко быть ботаником, если ты достаточно велик”.
Гэри отошел от дел в 2015 году и в настоящее время преподает только один
онлайн-курс в год из своего дома престарелых в Куэнка, Эквадор.
Стэнли Селков, профессор информатики из Вустерского политехнического ин­
ститута, в 1965 году получил степень бакалавра в области электротехники в Инсти­
туте Карнеги, а в 1970 — ученую степень в той же области в Пенсильванском универ­
ситете. С 1968 по 1970 год он работал в системе здравоохранения в Национальном
институте здравоохранения в Бетесде, штат Мэриленд. С 1970 года работал в уни­
верситетах в Ноксвилле, штат Теннесси, и Вустере, штат Массачусетс, а также в Мон­
реале, Чунцине, Лозанне и Париже. Его основные исследования посвящены теории
графов и разработке алгоритмов.

Об изображении на обложке
Животное на обложке этой книги — рак-отшельник (Pagurus bernhardus). Имеет­
ся более 500 видов таких раков-отшельников. Преимущественно водные, они живут
в соленой воде мелководных коралловых рифов. Однако некоторые разновидности
раков-отшельников, особенно в тропиках, являются сухопутными (примером может
служить пальмовый вор, размер которого достигает 40 см). Но даже наземные от­
шельники носят в своих раковинах небольшое количество воды, помогающее им ды­
шать и поддерживать необходимый уровень влажности.
В отличие от истинных крабов, отшельники не имеют жесткого панциря и вы­
нуждены искать убежище от хищников в заброшенных раковинах брюхоногих

Предисловие ко второму изданию

|

19

(улиток). Особенно им нравятся брошенные раковины литорин. По мере роста от­
шельники находят новые раковины для обитания.
Раки-отшельники являются декаподами, что буквально означает “десятиногие”.
Из пяти пар ног первые две являются клешнями, которые они используют, чтобы за­
щищать себя и измельчать пищу. Меньшие клешни используются для питания. Вто­
рая и третья пары ног предназначены для передвижения, а последние две помогают
удерживаться в раковине.
Как и все ракообразные, отшельники не имеют внутреннего скелета; вместо этого
у них довольно твердый экзоскелет из кальция. У них два составных глаза, две пары
антенн (которые они используют, чтобы обонять и осязать) и три пары ротовых ор­
ганов. У основания их антенн есть пара зеленых желез для вывода отходов.
Часто в симбиозе с ними находятся морские анемоны, которые прикрепляются к ра­
ковинам отшельников. В обмен на услуги транспортировки и остатки еды морские ане­
моны помогают ракам защищаться от морских хищников, таких как рыбы и осьминоги.
Известные как “мусорщики моря”, отшельники едят что угодно, в том числе мерт­
вые и гниющие останки на берегу моря, и, таким образом, играют важную роль
в очистке побережья. Будучи всеядными, они имеют разнообразный рацион, который
включает в себя все от червей до органического мусора, такого как трава и листья.
Изображение на обложке взято из второго тома Library of Natural History Джонсона.

Ждем ваших отзывов!
Вы, читатель этой книги, и есть главный ее критик. Мы ценим ваше мнение и хотим
знать, что было сделано нами правильно, что можно было сделать лучше и что еще вы
хотели бы увидеть изданным нами. Нам интересны любые ваши замечания в наш адрес.
Мы ждем ваших комментариев и надеемся на них. Вы можете прислать нам бу­
мажное или электронное письмо либо просто посетить наш веб-сайт и оставить
свои замечания там. Одним словом, любым удобным для вас способом дайте нам
знать, нравится ли вам эта книга, а также выскажите свое мнение о том, как сделать
наши книги более интересными для вас.
Отправляя письмо или сообщение, не забудьте указать название книги и ее авто­
ров, а также свой обратный адрес. Мы внимательно ознакомимся с вашим мнением
и обязательно учтем его при отборе и подготовке к изданию новых книг.
Наши электронные адреса:
E-mail:
WWW:

info@ dialektika.com
h ttp ://w w w .d ialek tik a.co m

Наши почтовые адреса:
в России:
195027, Санкт-Петербург, Магнитогорская ул., д. 30, ящик 116
в Украине:
03150, Киев, а/я 152

20

|

Предисловие ко второму изданию

_____ 1
Мысли алгоритмически

Алгоритм имеет значение!
Знание, какой алгоритм следует применить при том или ином наборе обстоя­
тельств, может привести к очень большой разнице в производительности вашего
программного обеспечения. Пусть эта книга станет вашим учебником, из которо­
го вы узнаете о ряде важных групп алгоритмов, например о таких, как сортировка
и поиск. Мы введем ряд общих подходов, применяемых алгоритмами для решения
задач, например подход “разделяй и властвуй” или жадная стратегии. Вы сможете
применять полученные знания для повышения эффективности разрабатываемого
вами программного обеспечения.
Структуры данных жестко связаны с алгоритмами с самого начала развития ин­
форматики. Из этой книги вы узнаете о фундаментальных структурах данных, ис­
пользуемых для надлежащего представления информации для ее эффективной об­
работки.
Что вам нужно сделать при выборе алгоритма? Мы рассмотрим ответ на этот во­
прос в следующих разделах.

Понимание проблемы
Первый шаг в разработке алгоритма состоит в понимании задачи, которую вы
хотите решить. Начнем с примера задачи из области вычислительной геометрии. Для
данного набора точек двумерной плоскости Р, наподобие показанного на рис. 1.1,
представим резиновую ленту, которая растягивается так, чтобы охватить все точки,
и отпускается. Полученная в результате фигура называется выпуклой оболочкой (она
представляет собой наименьшую выпуклую фигуру, которая полностью охватывает
все точки множества Р). Ваша задача — разработать алгоритм для вычисления вы­
пуклой оболочки множества двумерных точек.

Рис. 1.1. Пример множества из 15 точек на плоскости
Для выпуклой оболочки Р любой отрезок между любыми двумя точками Р пол­
ностью лежит внутри оболочки. Предположим, что мы перенумеровали точки вы­
пуклой оболочки по часовой стрелке. Таким образом, оболочка формируется упоря­
дочением по часовой стрелке h точек L0, Llf ..., Lh как показано на рис. 1.2. Каждая
последовательность из трех точек оболочки L., L.+1, L.+2 образует правый поворот.

Рис. 1.2. Вычисленная выпуклая оболочка
Имея только эту информацию, вы, вероятно, сможете нарисовать выпуклую обо­
лочку для любого набора точек; но смогли бы вы придумать алгоритм (т.е. пошаго­
вую последовательность инструкций, которые будут эффективно вычислять выпук­
лую оболочку для любого набора точек)?
Задача о выпуклой оболочке представляется нам интересной, в первую очередь,
потому, что она не кажется легко классифицируемой в смысле имеющихся областей
применения алгоритмов. Не похоже, чтобы помогла любая линейная сортировка
точек слева направо, хотя точки оболочки и упорядочиваются по часовой стрелке.

22

|

Глава 1. Мысли алгоритмически

Аналогично не выполняется никакой очевидный поиск, хотя отрезок выпуклой обо­
лочки можно идентифицировать по тому, что оставшиеся п-2 точки плоскости ле­
жат “справа” относительно этого отрезка.

Прямое решение
Очевидно, что выпуклая оболочка существует для любого набора из трех или
более точек. Но как ее построить? Рассмотрим следующую идею. Выберем любые
три точки из исходного множества и образуем из них треугольник. Если какие-либо
оставшиеся п-Ъ точки содержатся в этом треугольнике, они заведомо не могут быть
частью выпуклой оболочки. Мы опишем общий процесс с использованием псевдоко­
да (аналогичные описания вы найдете для каждого из алгоритмов в книге).
Медленный поиск выпуклой оболочки

Наилучший, средний, наихудший случаи: 0(и4)
slowHull (Р)
foreach рО in Р do
foreach pi in {Р-рО} do
foreach р2 in {Р—pO-pl} do
foreach p3 in {P-p0-pl-p2} do
if рЗ содержится в Triangle(pO,pi,p2) then
Отметить рЗ как внутреннюю точку

О

©

Создать массив А из всех точек Р, не являющихся внутренними
Определить крайнюю слева точку множества оставшихся точек А
Отсортировать множество А по углу относительно вертикальной ©
линии, проходящей через крайнюю слева точку
Вернуть А

О Точки рО, pi, р2 образуют треугольник.
© Точки, не помеченные как внутренние, образуют выпуклую оболочку.
© Эти углы (в градусах) находятся в диапазоне от -90° до 90°.

В следующей главе мы рассмотрим математический анализ, который поясняет, поче­
му этот подход является неэффективным. В псевдокоде разъяснены шаги, которые стро­
ят выпуклую оболочку для каждого входного набора точек; в частности, такой способ
строит выпуклую оболочку на рис. 1.2. Но лучшее ли это, что мы можем сделать?

Интеллектуальные подходы
Многочисленные алгоритмы в этой книге являются результатом стремления по­
лучить более эффективные решения для существующего кода. Мы выявляем общие

Прямое решение

|

23

темы в этой книге, чтобы помочь вам решать ваши собственные задачи. Есть много
разных способов вычисления выпуклой оболочки. В набросках этих подходов мы зна­
комим вас с образцами материала, который будет представлен в последующих главах.

Жадный подход
Вот способ построить выпуклую оболочку по одной точке.
1. Убираем из множества Р самую нижнюю точку, low, которая должна быть
частью оболочки.
2. Сортируем оставшиеся и - 1 точек в убывающем порядке по углу, который
образуется по отношению к вертикальной линии, проходящей через точку low.
Эти углы лежат в диапазоне от 90° для точек слева от линии до -90° для точек
справа. рп 2 является крайней справа в смысле значения угла точкой, а р0 —
крайней слева. На рис. 1.3 показаны эта вертикальная линия и (тонкими
отрезками) соответствующие углы.
3. Начнем с частично выпуклой оболочки, сформированной из трех точек в порядке
[рп 2, lowy р0]. Далее пытаемся расширить оболочку, рассмотрев поочередно
каждую из точек от р { до рп2. Если рассматриваемые последними три точки
частичной оболочки приводят к повороту отрезка оболочки влево, значит,
оболочка содержит неправильную точку, которую необходимо из нее удалить.
4. После того как все точки рассмотрены, частичная оболочка становится полной
(рис. 1.3).

Рис. 1.3. Оболочка^ сформированная
с использованием жадного подхода

24

|

Глава 1. Мысли алгоритмически

Разделяй и властвуй
Мы можем разделить проблему пополам, если сначала отсортируем все точки Р слева
направо по координате х (при равных х рассматриваем координату у). Для этой отсор­
тированной коллекции мы сначала вычисляем верхнюю частичную выпуклую оболоч­
ку, рассматривая точки в порядке слева направо от р0 до рп { в направлении по часовой
стрелке. Затем таким же образом строится нижняя частичная выпуклая оболочка, путем
обработки тех же точек в порядке справа налево от рп { до р0 в том же направлении —
по часовой стрелке. При сканировании выпуклой оболочки (описанном в главе 9, “Вы­
числительная геометрия”) эти частичные оболочки (показанные на рис. 1.4) вычисляют­
ся и объединяются в окончательную выпуклую оболочку всего множества точек.

Рис. 1.4. Полная оболочка, образованная верхней и нижней частичными оболочками

Параллельное вычисление
Если у вас есть несколько процессоров, разделим начальное множество точек
по координате х, и пусть каждый процессор вычисляет выпуклую оболочку для сво­
его подмножества точек. После того как вычисления будут завершены, окончатель­
ная оболочка получается путем сшивания в единое целое соседних частичных ре­
шений. Параллельный подход делит подзадачи между несколькими процессорами,
чтобы ускорить общий ход решения.
На рис. 1.5 показано применение этого подхода на трех процессорах. Две сосед­
ние оболочки сшиваются вместе с помощью добавления двух касательных линий —
одной вверху, другой внизу — с последующим удалением отрезков, содержащихся
в четырехугольнике, образованном этими отрезками.

Приближение
Даже с использованием всех этих улучшений имеется фиксированный нижний
предел производительности для вычисления выпуклой оболочки, который невоз­
можно превзойти. Однако, возможно, вместо вычисления точного ответа вас мог
бы удовлетворить ответ приблизительный, который можно вычислить быстро и по­
грешность которого может быть точно определена.
Интеллектуальные подходы

|

25

Рис. 1.5. Оболочка, образованная путем параллельного построения и сшивания
Алгоритм Бентли-Фауста-Препараты создает приблизительную выпуклую обо­
лочку путем разбиения множества точек на вертикальные полоски [10]. В каждой
такой полосе определяются максимальные и минимальные точки (на основе коорди­
наты у), которые на рис. 1.6 изображены с квадратами вокруг точек. Вместе с край­
ней слева и крайней справа точками Р эти крайние точки сшиваются в единую при­
близительную выпуклую оболочку. При этом может случиться так, что некоторые
точки выходят за рамки полученной оболочки, как, например, точка р { на рис. 1.6.

Обобщение
Зачастую оказывается возможным решение более общей задачи, которое затем
может быть легко преобразовано в решение нашей конкретной задачи. Диаграм­
ма Вороного [47] является геометрической структурой, которая делит набор точек
на плоскости на области, каждая из которых оказывается закрепленной за одной из
исходных точек входного множества Р. Каждая область R. представляет собой набор
точек (х,у) плоскости, более близких к точке закрепления р., чем к любой иной точке
множества Р. После вычисления диаграммы Вороного эти области можно изобра­
зить так, как показано на рис. 1.7. Серые области полубесконечны и, как вы можете
видеть, соответствуют точкам выпуклой оболочки. Это наблюдение ведет к следую­
щему алгоритму.

26

|

Глава 1. Мысли алгоритмически

Рис. 1.6. Выпуклая оболочка, полученная путем приблизительных вычислений

Рис. 1.7. Оболочка, вычисленная из диаграммы Вороного

Интеллектуальные подходы

|

27

1. Вычисляем диаграмму Вороного для Р.
2. Инициализируем оболочку наинизшей точкой, low, множества Р и начинаем
работу с закрепленной за ней областью.
3. Двигаясь по часовой стрелке, посещаем соседнюю область, имеющую с данной
смежную бесконечную сторону, и добавляем к оболочке точку закрепления
этой области.
4. Продолжаем добавлять точки до тех пор, пока вновь не придем к нашей
исходной области.

Резюме
Эффективный алгоритм часто вовсе не очевиден, и для различных наборов дан­
ных, различных операционных сред (например, в которых можно использовать па­
раллелизм) и различных целей лучшими могут оказаться очень разные алгоритмы.
Прочитанное вами очень краткое введение — только маленькая борозда на огром­
ном поле алгоритмов. Мы надеемся, что эта глава вдохнула в вас желание узнать
побольше об этих различных алгоритмических подходах, а также о различных ал­
горитмах, которые мы собрали для вас в этой книге. Мы реализовали все рассмат­
риваемые здесь алгоритмы и задокументировали их, чтобы помочь вам понять, как
использовать эти алгоритмы и даже как реализовать их самостоятельно.

28

|

Глава 1. Мысли алгоритмически

______ 2
Математика алгоритмов

Одним из наиболее важных факторов при выборе алгоритма является скорость его
работы. Характеристика ожидаемого времени вычисления алгоритма по своей сути
является математическим процессом. В этой главе представлены математические ин­
струменты, лежащие в основе этого предсказания времени работы алгоритма. После
прочтения этой главы вы должны понимать различные математические термины, ис­
пользуемые как в этой книге, так и в других книгах, посвященных алгоритмам.

Размер экземпляра задачи
Экземпляр задачи представляет собой определенный набор входных данных
для программы. В большинстве задач время выполнения программы увеличивается
с ростом размера этого набора данных. В то же время чрезмерно компактные пред­
ставления (возможно, с использованием технологий сжатия) могут необоснованно
замедлить выполнение программы. Определить оптимальный способ кодирования
экземпляра задачи на удивление трудно, поскольку задачи приходят к нам из реаль­
ного мира и должны быть переведены в надлежащее представление для решения
с помощью программы.
При вычислении алгоритма мы, насколько это возможно, полагаем, что кодиров­
ка экземпляра задачи не является определяющим фактором при выяснении вопроса
о том, насколько эффективно может быть реализован тот или иной алгоритм. Ваше
представление экземпляра задачи должно зависеть только от типа и набора опера­
ций, которые должны быть выполнены. Разработка эффективных алгоритмов часто
начинается с выбора правильных структур данных для представления задачи.
Поскольку мы не можем формально определить размер экземпляра, мы пред­
полагаем, что экземпляр кодируется некоторым общепринятым лаконичным спо­
собом. Например, при сортировке п целых чисел мы принимаем общее соглаше­
ние о том, что каждое из п чисел помещается в 32-разрядное слово в используемой

вычислительной платформе и размер экземпляра задачи сортировки равен п. В слу­
чае, если некоторые числа требуют для представления более одного слова — но при
этом постоянного, фиксированного количества слов, — наша мера размера экзем­
пляра изменяется только на постоянный множитель. Таким образом, алгоритм, ко­
торый выполняет вычисления, используя целые числа, хранящиеся с использовани­
ем 64 битов памяти, может оказаться в два раза длиннее аналогичного алгоритма,
закодированного с использованием целых чисел, хранящихся в 32 битах.
Исследователи алгоритмов принимают, что они не в состоянии вычислить с до­
статочной точностью расходы, связанные с использованием в реализации алгоритма
конкретной кодировки. Таким образом, они утверждают, что стоимости производи­
тельности, которые отличаются на постоянный множитель, асимптотически эквива­
лентны, или, другими словами, их отношение не имеет значения при росте размера
задачи. В качестве примера можно ожидать, что применение 64-разрядных целых
чисел потребует большего времени работы, чем применение 32-разрядных целых
чисел, но мы должны игнорировать это различие и считать, что алгоритм, который
хорош для миллиона 32-разрядных целых чисел, будет столь же хорош и для милли­
она 64-разрядных целых чисел. Хотя такое определение непрактично для реальных
ситуаций (вас бы устроило, если бы расходы на коммунальные услуги оказались в 10
раз больше, чем ожидалось?), оно служит универсальным средством сравнения ал­
горитмов.
Для всех алгоритмов в этой книге константы практически для всех платформ
невелики. Однако при реализации алгоритма в производственном коде необходи­
мо уделять внимание и деталям, которые отражаются на значениях этих констант.
Асимптотический подход полезен, поскольку он может предсказать производитель­
ность алгоритма для большого экземпляра задачи, основываясь на знаниях о про­
изводительности при решении небольших экземпляров задач. Это помогает опре­
делить наибольший размер экземпляра задачи, который можно решить с помощью
конкретной реализации алгоритма [11].
Для хранения коллекций информации большинство языков программирования
поддерживают массивыУ которые представляют собой смежные области памяти,
индексируемые целым числом / для обеспечения быстрого доступа к i-му элемен­
ту. Массив является одномерным, когда каждый элемент помещается в слово в ис­
пользуемой платформе (например, массив целых чисел или логических значений).
Некоторые массивы могут распространяться на несколько измерений, обеспечивая
возможность представления более сложных данных.

Скорость роста функций
Мы описываем поведение алгоритма путем представления скорости роста вре­
мени выполнения в зависимости от размера входного экземпляра задачи. Такая

30

|

Глава 2. Математика алгоритмов

характеристика производительности алгоритма является распространенной абстрак­
цией, которая игнорирует многочисленные детали. Чтобы правильно использовать
эту меру, требуется осведомленность о деталях, скрытых абстракцией. Каждая про­
грамма выполняется на определенной вычислительной платформе; под этим общим
термином подразумевается масса конкретных деталей.
•

Компьютер, на котором выполняется программа, его процессор (CPU), кеш
данных, процессор для вычислений с плавающей точкой (FPU) и другие аппа­
ратные возможности.

•

Язык программирования, на котором написана программа, наряду с тем, яв­
ляется ли он компилируемым или интерпретируемым, и настройки оптимиза­
ции для генерации кода.

•

Операционная система.

•

Прочие процессы, выполняющиеся в фоновом режиме.

Мы предполагаем, что с изменением платформы время выполнения программы
будет изменяться на постоянный множитель и что мы, таким образом, можем игно­
рировать различия платформ в соответствии с принципом асимптотической эквива­
лентности, описанным ранее.
Чтобы поместить эту дискуссию в практический контекст, обсудим вкратце алго­
ритм последовательного поиска, представленный в главе 5, “Поиск” Последователь­
ный поиск анализирует список из п > 1 отдельных элементов, по одному за раз, пока
не будет найдено искомое значение v. Пока что предположим следующее.
•

В списке имеется п различных элементов.

•

Список содержит искомое значение v.

•

Каждый элемент списка с равной вероятностью может быть искомым значением v.

Чтобы разобраться с производительностью последовательного поиска, мы долж­
ны знать, сколько элементов он просматривает “в среднем”. Так как известно, что
v имеется в списке и каждый элемент также может быть v, среднее число рассмо­
тренных элементов, £(м), является суммой количества элементов, просмотренных
для каждого из п значений, разделенной на п. Математически это записывается так:

Таким образом, с учетом высказанных выше предположений последовательный
поиск анализирует около половины элементов списка из п отдельных элементов.
Если число элементов в списке удваивается, то последовательному поиску при­
дется просматривать примерно вдвое больше элементов; ожидаемое количество
Скорость роста функций

|

31

просмотров является линейной функцией от п. Ожидаемое количество проверок —
“около” с-п для некоторой постоянной с; в данном случае с = 0,5. Фундаментальный
факт анализа производительности состоит в том, что постоянная с в долгосрочной
перспективе не важна, потому что наиболее важным фактором стоимости является
размер экземпляра задачи п. По мере того как п становится все больше и больше,
ошибка в утверждении, что
1

1

—
2

1

и+—
2
2

становится все менее важной. Фактически отношение между двумя величинами сле­
ва и справа от знака приближенного равенства стремится к 1, т.е.
- п

lim- \ *
1

=

1

1

-я +2
2

хотя ошибка в оценке имеет важное значение для небольших значений п. В этом кон­
тексте мы говорим, что скорость роста ожидаемого количества элементов, просматри­
ваемых последовательным поиском, является линейной. То есть мы игнорируем по­
стоянный множитель и рассматриваем только большие размеры экземпляров задачи.
При использовании абстракции скорости роста при выборе среди нескольких ал­
горитмов следует помнить о следующем.
Константы имеют значение
Именно поэтому мы используем суперкомпьютеры и постоянно обновляем
нашу вычислительную технику.
Размер п не всегда большой
В главе 4, “Алгоритмы сортировки”, мы увидим, что скорость роста времени
выполнения Quicksort меньше, чем скорость роста времени выполнения сор­
тировки вставками. Однако сортировка вставками на одной и той же плат­
форме превосходит быструю сортировку для небольших массивов.
Скорость роста для алгоритма определяет, как он будет работать со все большими
и большими экземплярами задач. Давайте применим этот базовый принцип к более
сложному примеру.
Рассмотрим оценку четырех алгоритмов сортировки для конкретной задачи.
Приведенные далее данные о производительности были получены путем сорти­
ровки блока из п случайных строк. Для блоков размером п= 1-512 было выполнено
по 50 испытаний. Были отброшены наилучшие и наихудшие результаты, и на рис. 2.1
показано среднее время (в микросекундах) для оставшихся 48 замеренных значений
времени работы. Полученные результаты удивительны.

32

|

Глава 2. Математика алгоритмов

Рис. 2.1. Сравнение четырех алгоритмов
сортировки для малых наборов данных
Один из способов интерпретации этих результатов заключается в попытке соз­
дать функцию, которая будет предсказывать производительность каждого алгоритма
для экземпляра задачи размера п. Мы вряд ли сможем угадать такую функцию, по­
этому воспользуемся коммерчески доступным программным обеспечением для вы­
числения линии тренда с помощью статистического процесса, известного как регрес­
сионный анализ. Соответствие линии тренда фактическим данным оценивается как
значение в диапазоне от 0 до 1, известное как R2. Значение около 1 указывает высокую
степень соответствия. Например, если R2=0,9948, то вероятность того, что линия трен­
да обусловлена случайными отклонениями данных, составляет всего лишь 0,52%.
Очевидно, что среди представленных алгоритмов сортировки алгоритм Sort-4
имеет наихудшую производительность. Для полученных 512 точек данных линия
тренда производительности имеет следующий вид:
Скорость роста функций

|

33

у = 0,0053 •п2 - 0,3601 •п + 39,212
R2 =0,9948
Значение R2, настолько близкое к 1, объявляет эту линию тренда как точную
оценку. Сортировка Sort-2 является наиболее быстрой сортировкой для заданного
диапазона точек. Ее поведение характеризуется следующей формулой линии тренда:
у = 0,05765 •п •log (и) + 7,9653
Изначально Sort-2 незначительно превосходит Sort-З, и ее конечное поведение
примерно на 10% быстрее, чем поведение Sort-3. Sort-1 демонстрирует две различ­
ные модели поведения. Для блоков размером 39 или менее поведение характеризует­
ся линией тренда
у = 0,0016 •п2 + 0,2939 •п + 3,1838
R2 =0,9761
Однако при 40 и более строках поведение описывается как
у = 0,0798 •п •log (п) +142,7818
Числовые коэффициенты в этих уравнениях полностью зависят от платформы,
на которой выполняются соответствующие реализации. Как было указано ранее, та­
кие случайные различия не являются важными. При вычислениях, в первую очередь,
интересует долгосрочная тенденция, доминирующая при больших значениях п. На
рис. 2.1 графики поведения алгоритмов представлены с использованием двух раз­
личных диапазонов специально, чтобы показать, что, пока п не достигнет достаточно
больших значений, реальное поведение алгоритма не может быть очевидным.
Разработчики алгоритмов стремятся понять поведенческие различия между раз­
ными алгоритмами. Sort-1 отражает производительность qsort в Linux 2.6.9. Про­
смотрев исходный код (который можно найти в любом из доступных репозитори­
ев кода Linux), мы обнаружим следующий комментарий: “Подпрограмма Qsort из
Engineering a Sort Function Бентли и Макилроя”. Бентли и Макилрой [9] описывают,
как оптимизировать быструю сортировку путем изменения стратегии для задач раз­
мером меньше 7, между 8 и 39, а также 40 и выше. Приятно видеть, что представлен­
ные здесь эмпирические результаты соответствуют описанной реализации.

Анализ наилучшего, среднего и наихудшего случаев
Имеется один вопрос, который нельзя не задать, — будут ли результаты преды­
дущего раздела верны для всех экземпляров задачи? Как изменится поведение Sort-2
при изменении входных данных экземпляров задач того же размера?
•

34

Данные могут содержать большие группы элементов, находящиеся уже в отсор­
тированном порядке.
|

Глава 2. Математика алгоритмов

•

Входные данные могут содержать повторяющиеся значения.

•

Независимо от размера п входного множества элементы могут выбираться из
гораздо меньшего набора и содержать значительное количество повторяющих­
ся значений.

Хотя Sort-4 на рис. 2.1 является самым медленным из четырех алгоритмов сор­
тировки п случайных строк, оказывается, что она самая быстрая, если данные уже
отсортированы. Однако это преимущество быстро исчезает; как показано на рис. 2.2,
всего лишь 32 случайных элементов вне правильных позиций достаточно, чтобы
Sort-З имела более высокую производительность.

Рис. 2.2. Сравнение алгоритмов сортировки
для отсортированных и почти отсортированных данных

Анализ наилучшего, среднего и наихудшего случаев

35

Однако предположим, что входной массив с п строками “почти отсортирован”,
т.е. что п!4 строк (25% из них) поменялись местами со строками в другой позиции
на расстоянии всего лишь четырех позиций. Это может показаться удивительным,
но, как видно из рис. 2.3, теперь сортировка Sort-4 превосходит прочие алгоритмы
сортировки.

Рис. 2.3. Sort-4 хорошо работает с почти отсортированными данными
Из представленного материала можно сделать вывод, что для многих задач не су­
ществует единого оптимального алгоритма. Выбор алгоритма зависит от понимания
решаемой задачи и лежащего в ее основе распределения вероятности экземпляров
с учетом поведения рассматриваемых алгоритмов.
Чтобы дать некоторые ориентиры, поведение алгоритмов обычно представлено
в трех распространенных ситуациях.
Наихудший случай (worst case)
Определяет класс экземпляров задачи, для которых алгоритм показывает
свое наихудшее поведение во время выполнения. Вместо того чтобы пытать­
ся определить конкретные входные данные, разработчики алгоритмов обычно
описывают их свойства, которые мешают эффективной работе алгоритма.
Средний случай (average case)
Определяет ожидаемое поведение при выполнении алгоритма для случайных
экземпляров задачи. Хотя некоторые экземпляры могут потребовать больше­
го времени выполнения, для подавляющего большинства экземпляров задачи
этого не произойдет. Эта мера описывает то, чего следует ожидать от примене­
ния алгоритма среднему пользователю.

36

|

Глава 2. Математика алгоритмов

Наилунший случай (best case)
Определяет класс экземпляров задачи, для которых алгоритм демонстрирует
наилучшее поведение во время выполнения. Для этих экземпляров алгоритм
выполняет наименьшее количество работы. В реальности наилучшие случаи
встречаются редко.
Зная производительность алгоритма в каждом из этих случаев, вы можете судить,
подходит ли данный алгоритм для использования в вашей конкретной ситуации.

Наихудший случай
Для любого конкретного значения п работа алгоритма или программы может рез­
ко изменяться для разных экземпляров одного и того же размера п. Для конкретной
программы и конкретного значения п наихудшее время выполнения — это макси­
мальное время выполнения, где максимум взят по всем экземплярам размера п.
Нас интересует наихудшее поведение алгоритма, поскольку зачастую это про­
стейший случай для анализа. Он также показывает, насколько медленной может
быть программа в произвольной ситуации.
Говоря более формально, если Sn представляет собой множество экземпляров за­
дачи s. размера и, a t() — функция, которая измеряет работу алгоритма для каждого
экземпляра, то работа алгоритма на множестве Sn в наихудшем случае представляет
собой максимум f(s.) по всем s. e S n. Обозначив эту наихудшую на Sn производитель­
ность как Т,с(и), получаем, что скорость роста Тт(п) определяет сложность алгорит­
ма в наихудшем случае.
Для вычисления каждого отдельного экземпляра s., на котором выполняется алго­
ритм для эмпирического определения экземпляра, приводящего к наихудшей произ­
водительности, ресурсов обычно недостаточно. Вместо этого предлагается описание
экземпляра задачи, приводящего к наименьшей производительности алгоритма.

Средний случай
Рассмотрим телефонную систему, предназначенную для поддержки большого ко­
личества п телефонов. В худшем случае она должна быть в состоянии выполнить
все вызовы, когда п/2 человек одновременно возьмут свои телефоны и вызовут п/2
других человек. Хотя такая система никогда не рухнет из-за перегрузки, создавать
ее было бы слишком дорого. В действительности вероятность того, что каждый из
п/2 человек вызовет своего уникального корреспондента из других п/2 человек, чрез­
вычайно мала. Вместо этого мы могли бы разработать более дешевую систему и ис­
пользовать математический инструментарий для выяснения вероятности аварии изза перегрузки.
Для множества экземпляров размера п мы связываем распределение вероятнос­
тей Pr{s.}, которое каждому экземпляру s. назначает вероятность от 0 до 1, так что
Анализ наилучшего, среднего и наихудшего случаев

|

37

сумма вероятностей по всем экземплярам размера п равна 1. Говоря более формаль­
но, если Sn — множество экземпляров размера пу то
s, eS„

Если функция t() измеряет работу, выполнимую алгоритмом для каждого экземпля­
ра, то работа алгоритма над множеством Sn в среднем случае равна
s, <=S„

То есть фактическая работа для экземпляра s. представляет собой f(s.) с весом,
равным вероятности того, что экземпляр s. будет представлен в качестве входных
данных. Если Pr{s.} = 0, то фактическое значение f(s.) не влияет на ожидаемую рабо­
ту, выполняемую программой. Обозначая работу с множеством Sn в среднем случае
как ГДи), мы получаем, что скорость роста ГД л) определяет сложность алгоритма
в среднем случае.
Напомним, что при описании скорости роста работы или времени мы последо­
вательно игнорируем константы. Поэтому, когда мы говорим, что последовательный
поиск п элементов занимает в среднем
1
—

2

пл

1
—

2

испытаний (с учетом сделанных нами ранее предположений), то по соглашению мы
просто говорим, что при этих предположениях ожидается, что последовательный по­
иск будет проверять линейное количество элементов, или порядка п элементов.

Наилучший случай
Знать наилучший случай для алгоритма полезно, несмотря даже на то, что такая
ситуация крайне редко встречается на практике. Во многих случаях она обеспечива­
ет понимание оптимальных условий для работы алгоритма. Например, наилучшим
случаем для последовательного поиска является тот, когда искомое значение v явля­
ется первым элементом в списке. Рассмотрим несколько иной подход, который мы
будем называть поиском подсчетом и который подсчитывает, сколько раз v встре­
чается в списке. Если вычисленное значение равно нулю, то этот элемент не найден,
так что поиск возвращает значение false; в противном случае он возвращает значе­
ние true. Обратите внимание, что поиск подсчетом всегда проходит весь список; по­
этому, несмотря на то что его поведением в наихудшем случае является О(п) — так
же, как и при последовательном поиске, — его поведение в наилучшем случае так
и остается О(п), поэтому невозможно воспользоваться его преимуществами в наи­
лучшем или среднем случае, в котором он мог бы работать быстрее.

38

|

Глава 2. Математика алгоритмов

Нижняя и верхняя границы
Мы упростили презентацию записи с “большим О” в этой книге. Наша цель —
классифицировать поведение алгоритма по тому, как он решает экземпляры задач
с увеличением их размера п. Классификация алгоритмов имеет вид 0(Дя)), где Дм)
наиболее часто является такой функцией от п, как я, п3 или 2”.
Предположим, например, что существует алгоритм, наихудшая производитель­
ность которого никогда не превышает прямую пропорциональность размеру вход­
ного экземпляра задачи по достижении некоторого “достаточно большого” размера.
Точнее говоря, существует некоторая константа с> 0, такая, что t(n)< с-п для всех
п > я0, где nQявляется той точкой, в которой экземпляр задачи становится “доста­
точно большим”. В этом случае классификацией будет функция f[n) = п и мы будет
использовать запись О(я). Для этого же алгоритма предположим, что производи­
тельность в наилучшем случае никогда не меньше, чем прямая пропорциональность
размеру экземпляра входной задачи. В этом случае существуют другая постоянная с
и другой порог размера задачи п0 и t(n)>c-n для всех n>nQ. В этом случае классифи­
кация вновь имеет вид/{я) = я, но в этот раз она записывается как Q(n).
Таким образом, фактическая формальная запись выглядит следующим образом:
•

нижняя граница времени работы алгоритма классифицируется как
и соответствует сценарию наилучшего случая;

•

верхняя граница времени работы алгоритма классифицируется как 0{f(n))
и соответствует сценарию наихудшего случая.

Необходимо рассматривать оба сценария. Внимательный читатель заметит, что
мы могли просто использовать функцию j{n) = с-2п для классификации рассмотрен­
ного выше алгоритма как 0(2"), хотя это выражение и описывает гораздо более мед­
ленное поведение. В действительности это дает нам очень мало информации — все
равно что сказать, что нам понадобится не более чем неделя для решения задачи, ко­
торая в действительности решается за 5 минут. В этой книге мы всегда представляем
классификацию алгоритма, используя наиболее точное соответствие.
В теории сложности есть еще одна запись, ©(Дм)), которая сочетает в себе обе
концепции для определения тонной границы, т.е. когда нижняя граница П(Д«))
и верхняя граница 0(Ди)) используют для классификации одну и ту же функцию J{n).
Мы выбрали широко признанную (и более неформальную) запись 0(Ди)) для упро­
щения представления и анализа. В книге мы гарантируем, что при обсуждении по­
ведения алгоритма нет более точной функции /'(«)> которая может использоваться
для классификации алгоритма, который мы определяем как 0(Д«)).

Анализ наилучшего, среднего и наихудшего случаев

|

39

Семейства производительности
Мы сравниваем алгоритмы, оценивая их производительность для экземпляров
задач размера п. Эта методология является стандартным средством, разработанным
в последние полвека для сравнения алгоритмов. Поступая таким образом, мы можем
определить, какие алгоритмы масштабируются для решения задач нетривиального
размера, оценивая время, необходимое алгоритму для обработки входных данных
определенного размера. Вторичной характеристикой является потребность алгорит­
ма в памяти; при необходимости мы будем рассматривать эту проблему в рамках
описания отдельных алгоритмов.
Мы используем следующую классификацию, упорядоченную по убыванию эффек­
тивности.
•

Константная: 0(1)

•

Логарифмическая: 0(log п)

•

Сублинейная: 0(nd) при d< 1

•

Линейная: 0(п)

•

Линейно-логарифмическая: 0(n-log п)

•

Квадратичная: 0 (п 2)

•

Экспоненциальная: 0(2”)

При оценке производительности алгоритма следует иметь в виду, что для опре­
деления ее классификации требуется найти самые дорогостоящие вычисления в ал­
горитме. Например, рассмотрим алгоритм, который подразделяется на две задачи,
которые классифицируются как линейная, за которой следует квадратичная. В этом
случае общая производительность алгоритма должна быть классифицирована как
квадратичная.
Теперь проиллюстрируем данную классификацию производительности на при­
мерах.

Константное поведение
Анализируя производительность алгоритмов в этой книге, мы часто утверждаем,
что некоторые примитивные операции обеспечивают константную производитель­
ность. Очевидно, что это утверждение не является абсолютным фактором для факти­
ческой производительности операции, так как мы никак не затрагиваем аппаратное
обеспечение. Например, сравнение двух 32-битных чисел х и у на равенство должно
иметь одинаковую производительность независимо от фактических значений х и у.
Константная операция определяется как имеющая производительность 0(1).

40

|

Глава 2. Математика алгоритмов

А что можно сказать о производительности сравнения двух 256-битных чисел?
Или двух 1024-битных чисел? Оказывается, что для предопределенного фиксирован­
ного размера к можно сравнить два /с-битных числа за постоянное время. Ключевым
является тот факт, что размер задачи (например, сравниваемые значения х и у) не
могут выйти за пределы фиксированного размера к. Мы абстрагируемся от дополни­
тельных действий, мультипликативных в терминах к, используя запись 0(1).

Логарифмическое поведение
Бармен предлагает следующий спор на 10000 долларов: “Я загадываю число от 1
до 1000000 и даю вам 20 попыток, чтобы его отгадать. После каждой вашей догадки
я говорю вам, назвали ли вы слишком малое число, слишком большое или угадали.
Если вы угадываете число за 20 или меньше попыток, я плачу вам 10000 долларов.
Если не угадали, вы платите мне”. Ну как, вы принимаете пари? Вы просто обязаны
это сделать, потому что вы всегда можете выиграть. В табл. 2.1 показан пример сце­
нария для диапазона от 1 до 8, в котором задается ряд вопросов, уменьшающий раз­
мер задачи примерно наполовину.
Таблица 2.1. Угадывание числа от 1 до 8
Число

Первый раунд

Второй раунд

Третий раунд

1

Это 41
М ного

Это 2?
М ного

Это 1!
Угадал!

2

Это 4?
М ного

Это 2?
Угадал!

3

Это 4?

Это 21
М ало

Э то З !
Угадал!

М ало

Это 6?
М ного

Это 5!
Угадал!

6

Это 4?
М ало

Это 61
Угадал!

7

Это 4?
М ало

Это 6?
М ало

Это 7?
Угадал!

8

Это 4?
М ало

Это 6?
М ало

Это 7?
М ало

М ного
4

Это 4?
Угадал!

5

Это 4?

Четвертый раунд

Это 8!
Угадал!

В каждом раунде, в зависимости от конкретных ответов от бармена, размер по­
тенциального диапазона, содержащего загаданное число, сокращается примерно
в два раза. В конце концов диапазон окажется ограниченным только одним возмож­
ным числом; это происходит после l + [log2 n j раундов, где log2 х вычисляет лога­

J

рифм х по основанию 2. Функция “пол” |_x округляет число х до наибольшего цело­
го числа, не превосходящего х. Например, если бармен выбирает число от 1 до 10,
Семейства производительности

|

41

то вы могли бы отгадать его за l + [log210J = 1ч-1_3,322J, т.е. за четыре попытки. Как
еще одно подтверждение верности этой формулы рассмотрим загадывание барменом
одного из двух чисел. Вам нужно два раунда, чтобы гарантировать угаданное число:
1+ [_log22 = 1+ 1_1 = 2. Помните, что согласно правилам бармена вы должны назвать
число вслух.
Этот подход одинаково хорошо работает и для 1000000 чисел. В самом деле, ал­
горитм отгадывания, показанный в примере 2.1, работает для любого диапазона

J

J

[low,high) и определяет значение загаданного числа п за 1+ [log2(h ig h -lo w + \)\^ ра­
ундов. Если всего имеется 1000000 чисел, этот алгоритм найдет загаданное число
максимум за l + [log21000 000j = 1-h |_19,932 = 20 раундов (в наихудшем случае).

J

Пример 2.1. Код на языке программирования Java
для угадывания чисел в диапазоне [low, high]
// Вычисляет количество раундов, если п гарантированно
// находится в диапазоне [low,high],
public static int turns (int n, int low, int high) {
int turns = 0;
// Продолжаем, пока имеется число для угадывания
while (high >= low) {
turns++;
int mid = (low + high)/2;
if (mid == n) {
return turns;
} else if (mid < n) {
low = mid + 1;
} else {
high = mid - 1;

return turns;

}
Логарифмические алгоритмы чрезвычайно эффективны, потому что быстро схо­
дятся к решению. Эти алгоритмы уменьшают размер задачи на определенный мно­
житель при каждой итерации (чаще всего примерно вполовину). Рассмотренный
выше алгоритм приводит к решению после максимум /c = l+ [lo g 2 nj итераций и на
/-й итерации (0<i<k) вычисляет пробное значение, о котором известно, что оно на­
ходится в пределах ± s = 2k~l -1 от фактического загаданного числа. Значение е рас­
сматривается как ошибка, или неопределенность, угадывания. После каждой итера­
ции цикла значение е уменьшается вдвое.
В оставшейся части книги всякий раз, когда мы ссылаемся на log(«), предполага­
ется логарифм по основанию 2, так что мы просто убираем индекс из записи log2(п).
Еще один пример, демонстрирующий эффективное поведение, — алгоритм
деления пополам, который вычисляет корень уравнения от одной переменной,
42

|

Глава 2. Математика алгоритмов

а именно — вычисляет значение х, при котором значение непрерывной функции fix)
равно нулю. Вычисления начинаются с двух значений, а и ЬУв которых Да) и f(b)
имеют противоположные знаки, т.е. одно из значений положительное, а другое —
отрицательное. На каждом шаге метод делит пополам диапазон [а, Ь] путем вычис­
ления его средины с и определяет, в какой из половин должен находиться корень.
Таким образом, на каждой итерации значение с является приближенным значением
корня с погрешностью, уменьшающейся в два раза.
Чтобы найти кореньях)=x-sin(;t)-5-х-cos(x), начнем с а = -1 иЬ=1. Как показано
в табл. 2.2, алгоритм сходится к решению уравнения Д х)= 0, корнем которого являет­
ся значение х - -0,189302759.
Таблица 2.2. Метод деления пополам
л

а

1

-1,0000000

Ь
1,0000000

0,0000000

2

-1,0000000

0,0000000

-0,5000000

1,8621302

3

-0,5000000

0,0000000

-0,2500000

0,3429386

С

т
-1,0000000

4

-0,2500000

0,0000000

-0,1250000

-0,3516133

5

-0,2500000

-0,1250000

-0,1875000

-0,0100227

6

-0,2500000

-0,1875000

-0,2187500

0,1650514

7

-0,2187500

-0,1875000

-0,2031250

0,0771607

8

-0,2031250

-0,1875000

-0,1953125

0,0334803

9

-0,1953125

-0,1875000

-0,1914062

0,0117066

10

-0,1914062

-0,1875000

-0,1894531

0,0008364

11

-0,1894531

-0,1875000

-0,1884766

-0,0045945

12

-0,1894531

-0,1884766

-0,1889648

-0,0018794

13

-0,1894531

-0,1889648

-0,1892090

-0,0005216

14

-0,1894531

-0,1892090

-0,1893311

0,0001574

15

-0,1893311

-0,1892090

-0,1892700

-0,0001821

16

-0,1893311

-0,1892700

-0,1893005

-0,0000124

Сублинейное поведение
В некоторых случаях поведение алгоритма лучше линейногоу но не так эффектив­
но, как логарифмическое. Как описано в главе 10, “Пространственные древовидные
структуры”, /c-d-дерево (/с-мерное дерево) может эффективно разделять множество,
состоящее из п d-мерных точек. Если дерево сбалансировано, время поиска для за­
просов диапазонов, которые соответствуют оси точек, составляет 0 (n ll/d). Для дву­
мерных запросов производительность равна 0(\/л).

Семейства производительности

43

Линейная производительность
Очевидно, что для решения одних задач требуется больше усилий, чем для решения
других. Ребенок может вычислить 7+5 и получить 12. Насколько сложнее задача 37+45?
В частности, насколько трудно сложить два л-значных числа ап г ..а0+ bn_r --bQ
и получить в результате и+1-значное число сп...с ? В этом алгоритме используются
следующие примитивные операции:
ci <-(а. + b{ + сапу.) mod 10
Г1, если а. + Ъ. + carry. > 10,
carry. . <- <
\0 в противном случае.
Пример реализации этого алгоритма на языке программирования Java показан в при­
мере 2.2, где п-значное число представлено в виде массива значений типа int, в кото­
ром старшая (т.е. крайняя слева) цифра находится в позиции с индексом 0. В примерах
в этом разделе предполагается, что каждое из этих значений представляет собой деся­
тичную цифру d, такую, что 0<d<9.
Пример 2.2. Реализация сложения многозначных
чисел на языке программирования Java
public static void add (int[] nl, int[] n2, int[] sum) {
int position = nl.length-1;
int carry = 0;
while (position >= 0) {
int total = nl[position] + n2[position] + carry;
sum[position+l] = total % 10;
if (total > 9) { carry = 1; } else { carry = 0; }
position— ;

}
sum[0] = carry;

}
До тех пор, пока входные данные задачи могут храниться в памяти, метод add
вычисляет сумму двух чисел, представленных входными целочисленными массива­
ми nl и п2 и сохраняет результат в массиве sum. Будет ли эта реализация такой же
эффективной, как альтернативный метод plus, приведенный в примере 2.3, который
вычисляет точно такое же значение, используя другие вычисления?
Пример 2.3. Реализация метода p lu s на Java
public static void plus(int[] nl, int[] n2, int[] sum) {
int position = nl.length;
int carry = 0;
while (— position >= 0) {
int total = nl[position] + n2[position] + carry;
if (total > 9) {

44

|

Глава 2. Математика алгоритмов

sum[position+l] = total-10;
carry = 1;
} else {
sum[position+l] = total;
carry = 0;

}
}
sum[0] = carry;

}
Влияют ли эти небольшие различия реализации на производительность алгорит­
ма? Рассмотрим два других потенциальных фактора, которые могут влиять на про­
изводительность алгоритма.
•

add и plus можно тривиально преобразовать в программу на языке програм­
мирования С. Как выбор языка влияет на производительность алгоритма?

•

Программа может выполняться на разных компьютерах. Как выбор аппарат­
ного обеспечения влияет на производительность алгоритма?

Эти реализации были выполнены 10 000 раз с числами в диапазоне от 256
до 32768 знаков. Для каждого количества создавалось случайное число такого раз­
мера; после этого для каждой из 10000 проб над обоими числами выполнялся цикли­
ческий перенос (один — влево, другой — вправо) для создания двух разных чисел.
Были использованы два различных языка программирования (С и Java). Мы начина­
ем с гипотезы, что при удвоении размера задачи время выполнения алгоритма также
удваивается. Мы хотели бы убедиться, что это общее поведение, наблюдаемое неза­
висимо от компьютера, языка программирования или использованной реализации.
Каждый вариант был выполнен на множестве конфигураций.
g

Версия на языке программирования С, скомпилированная с включением от­
ладочной информации.
01, 02, 03
Версия на языке программирования С, скомпилированная с разными уровня­
ми оптимизации. Увеличение значения приводит к более высокой производи­
тельности.
Java
Реализация алгоритма на языке программирования Java.
В табл. 2.3 содержатся результаты и для add, и для p lus. В восьмом, последнем,
столбце сравнивается соотношение производительности метода plus для задачи раз­
мера 2п и задачи размера п. Определим t(n) как фактическое время работы алгорит­
ма для входных данных размера гг. Этот шаблон роста предоставляет эмпирические
данные времени вычисления plus для двух и-значных чисел.
Семейства производительности

|

45

Таблица 2 3 . Время (в мс) выполнения 10000 вызовов a d d / p l u s
случайных д-значных чисел
Add-g

п
256

33

Add-java

Add-03

19

10

Plus-g
31

Plus-java

Plus-03

20

11

Отношение

512

67

22

20

58

32

23

2,09

1024

136

49

40

126

65

46

2,00

2048

271

98

80

241

131

95

2,07
2,05

4096

555

196

160

489

264

195

8192

1107

392

321

972

527

387

1,98

16384

2240

781

647

1972

1052

805

2,08

32768

4604

1554

1281

4102

2095

1721

2,14

65536

9447

3131

2572

8441

4200

3610

2,10

131072

19016

6277

5148

17059

8401

7322

2,03

16811

14782

2,02

262144

38269

12576

10336

34396

524288

77147

26632

21547

69699

35054

30367

2,05

1048576

156050

51077

53916

141524

61856

66006

2,17

Можно классифицировать алгоритм сложения как линейный по отношению к раз­
меру входных данных п. То есть имеется некоторая константа с>0, такая, что c<t{n)-n
для “достаточно большого” я, или, точнее, для всех п > nQ. На самом деле нам не нуж­
но вычислять фактическое значение с или nQ; мы просто знаем, что они существуют
и могут быть вычислены. Можно выполнить доказательство для установления ли­
нейной нижней границы сложности сложения, показав, что должна быть рассмотре­
на каждая цифра (достаточно рассмотреть последствия пропуска одной из цифр).
Для всех выполнений p lu s (независимо от языка или настроек компиляции) мы
можем установить с равным 1/7 и выбрать в качестве nQзначение 256. Другие ре­
ализации сложения будут иметь другие значения констант, но общее поведение попрежнему будет линейным. Этот результат может показаться удивительным, учитывая,
что большинство программистов предполагают, что целочисленные арифметические
операции являются операциями с константным временем выполнения; однако посто­
янное время сложения достижимо только тогда, когда представление целочисленных
значений (например, 16- или 64-битное) использует фиксированный размер п.
При рассмотрении различий в алгоритмах постоянная с не так важна, как знание
скорости роста. Кажущиеся несущественными различия приводят к различной про­
изводительности. Реализация plu s пытается повысить эффективность путем устра­
нения вычисления остатка от деления (%). Тем не менее при компиляции как метода
plus, так и метода add с оптимизацией -03 последний почти на 30% быстрее. Но мы
не игнорируем значение с. Если мы выполняем сложение большое количество раз,
даже небольшие изменения фактического значения с могут оказать большое влияние
на общую производительность программы.

46

|

Глава 2. Математика алгоритмов

Линейно-логарифмическая производительность
Поведение многих эффективных алгоритмов лучше всего описывается этим
семейством производительности. Чтобы объяснить, как это поведение возника­
ет на практике, давайте определим t(n) как время, которое требуется алгоритму
для решения экземпляра задачи размера я. Метод “разделяй и властвуй” является
эффективным средством решения задач, когда задача размера я делится на (пример­
но равные) подзадачи размера я/2, решаемые рекурсивно. Решения этих подзадач
объединяются вместе в решение исходной задачи размера я за линейное время. Мате­
матически это можно определить следующим образом:
t{n) = 2-t{nj2} + c-n
Иначе говоря, t(n) включает стоимость двух подзадач вместе с не более чем ли­
нейной временной стоимостью (например, с-я) объединения результатов. Теперь
в правой части уравнения t(n/2) представляет собой время, необходимое для реше­
ния задачи размера я/2; используя ту же логику, его можно представить как
t (n j l ) = 2 •t (я/4) + с •я/2,
так что исходное уравнение превращается в
f (я) = 2-[^2Т (я/4) + с-я/2^ + с-я.
Если мы распишем правую часть уравнения еще раз, то получим
t (я) = 2 •^2 *t («/4) + с •n jl J + с •п.
Это последнее уравнение сводится к
t (я) = 2 •^2 •[^2 •t (я/8) + с •п/А J -ь с •п/2 J + с •п.
Таким образом, можно просто сказать, что
t(n) = 2к -*(я/2*) + к-с-п.
Это преобразование правой части завершается, когда 2к=п (т.е. когда к = log п). В по­
следнем, базовом случае, когда размер задачи равен 1, производительность t( 1) явля­
ется константой d. Таким образом, мы получаем решение для t(n) в аналитическом
виде: t(ri) = n-d + c -n ’logn. Поскольку с-п -log я асимптотически больше drt для лю­
бых фиксированных констант с п d> t(n) можно просто записать как 0(n-log п).

Квадратичная производительность
Рассмотрим теперь задачу, похожую на задачу сложения я-значных чисел, но те­
перь мы будем их умножать. В примере 2.4 показана реализация такого умножения
“в столбик” — элементарный школьный алгоритм, использующий то же представле­
ние я-значных чисел, что и использованное ранее при сложении.

Семейства производительности

|

47

Пример 2Л. Реализация умножения n-значных чисел на Java
public static void mult (int[] nl, int[] n2, int[] result)
int pos = result.length-1;

{

// Очистка всех значений
for (int i = 0; i < result.length; i++) { result[i] = 0; }
for (int m = nl.length-1; m>=0; m— ) {
int off = nl.length-1 - m;
for (int n = n2.length-1; n>=0; n— ,off++) {
int prod = nl[m]*n2[n];
// Вычисление частичной суммы переносом предыдущей позиции
result[pos-off] += prod % 10;
result[pos-off-1] += result[pos-off]/10 + prod/10;
result[pos-off] %= 10;

}

И вновь мы написали альтернативную программу tim es, в которой устранена
необходимость в дорогостоящем операторе получения остатка от деления и опу­
щено наиболее глубоко вложенное вычисление при нулевом n l [ш] (описываемый
код tim es не показан, но его можно найти в репозитории). Метод tim es содержит
203 строки исходного текста на Java для удаления двух операторов вычисления
остатка от деления. Настолько ли велико при этом повышение производительности,
что оправдывает дополнительные усилия по разработке и поддержке этого кода?
В табл. 2.4 показано поведение этих реализаций умножения с теми же случайным
образом генерируемыми входными данными, которые использовались при демонстра­
ции суммирования. На рис. 2.4 производительность показана графически с помощью
параболической кривой, которая является признаком квадратичного поведения.
Таблица 2.4. Время (в мс) выполнения 10000 умножений
л

multn(ms) timesn(ms) mult./mult
2П
П

4

2

8

8

41
83

4,00

16

33

129

4,13

32

133

388

4,03

64

530

1276

3,98

128

2143

5009

4,04

256

8519

19014

3,98

512

34231

74723

4,02

48

|

Глава 2. Математика алгоритмов

Рис. 2.4. Сравнение умножений mult и times
Несмотря на то что метод times примерно в два раза медленнее mult, как times,
так и mult демонстрируют одну и ту же асимптотическую производительность. От­
ношение mult2ri/multw примерно равно 4, что указывает на квадратичную произво­
дительность умножения. Давайте определим t(n) как фактическое время работы ал­
горитма умножения для входных данных размера п. При таком определении должна
иметься некоторая константа с> 0, такая, что t(rt)<c-n2 для всех п>п0. На самом деле
нам не нужно знать все детали значений с и я0, достаточно знать, что они существу­
ют. Для реализации умножения mult на нашей платформе мы можем установить с
равным 1/7 и выбрать п0 равным 16.
И вновь, отдельные изменения реализации не могут “испортить” присущее дан­
ному алгоритму квадратичное поведение производительности. Однако существуют
и другие алгоритмы [61] для умножения пары я-значных чисел, которые значительно
быстрее, чем квадратичный. Эти алгоритмы играют важную роль в таких приложе­
ниях, как шифрование данных, когда часто необходимо перемножать очень большие
целые числа.

Менее очевидные производительности
В большинстве случаев прочтения описания алгоритма (как, например, описания
приведенных выше алгоритмов сложения и умножения) достаточно для классифика­
ции алгоритма как линейного или квадратичного. Например, основным показателем
квадратичности является наличие вложенного цикла. Но некоторые алгоритмы не
поддаются такому простому анализу. Рассмотрим в примере 2.5 реализацию алго­
ритма вычисления НОД (наибольшего общего делителя (greatest common divisor —
GCD) двух целых чисел), разработанного Евклидом.

Семейства производительности

|

49

Пример 2.5. Алгоритм вычисления НОД Евклида
public static void gcd (int a[], int b[], int gcd[]) {
if (isZero (a)) { assign (gcd, a); return; }
if (isZero (b)) { assign (gcd, b); return; }
a = copy (a);
b = сору (Ь);

// Делаем копии для гарантии, что
// а и b не изменяются

while (!isZero (b)) {
// Последний аргумент subtract - знак результата,
// который можно игнорировать, так как мы вычитаем
// только меньшее из большего.
// compareTo(a, Ь) положительно при а > Ь.
if (compareTo (а, b) > 0) {

subtract (a, b, gcd, new int El]);
assign (a, gcd);
} else {
subtract (b, a, gcd, new int[1]);
assign (b, gcd);

// В а находится вычисленное значение НОД исходных (a,b)
assign (gcd, а);

}
Этот алгоритм многократно сравнивает два числа (а и Ь) и вычитает меньшее чис­
ло из большего до достижения нуля. Реализации вспомогательных методов (isZero,
assign, compareTo, subtract) можно найти в репозитории кода книги.
Этот алгоритм возвращает наибольший общий делитель двух чисел, но четко­
го ответа на вопрос о том, сколько (с учетом размера входных данных) итераций
для этого потребуется, нет. При каждой итерации цикла либо а, либо b уменьшается,
но при этом никогда не становится отрицательным; поэтому мы можем гарантиро­
вать, что алгоритм завершит работу, но одни запросы могут потребовать гораздо
больше времени, чем другие; например при вычислении НОД(1000,1) алгоритм вы­
полняет 999 шагов! Производительность этого алгоритма явно более чувствительна
ко входным данным, чем производительность сложения или умножения; имеются
различные экземпляры задачи одинакового размера, которые требуют очень разного
количества вычислений. Данная реализация алгоритма демонстрировала наихудшую
производительность, когда мы запрашивали вычисление НОД(Ю*-1,1); при этом
приходилось выполнять п = 10*-1 итераций. Так как мы уже показали, что сложение
и вычитание имеют сложность О(п), где п — размер входных данных, алгоритм вы­
числения НОД можно классифицировать как 0 (я 2).

50

|

Глава 2. Математика алгоритмов

Производительность реализации вычисления НОД в примере 2.5 существенно
хуже производительности реализации алгоритма из примера 2.6, в котором исполь­
зуется оператор вычисления остатка от целочисленного деления а на Ь.
Пример 2.6. Реализация алгоритма вычисления НОД
с использованием операции получения остатка от деления
public static void modgcd (int a[], int b[], int gcd[])
if (isZero(a)) { assign (gcd, a); return; }
if (isZero(b)) { assign (gcd, b); return; }

{

// Выравнивание а и b до одинакового количества знаков
/ / и работа с копиями
а = copy(normalize(a, b.length));
b = copy(normalize(b, a.length));
// Гарантируем, что а > Ь. Возврат тривиального НОД
int rc = compareTo(а,Ь);
if (rc == 0) { assign (gcd, a); return; }
if (rc < 0) {
int t [] = b;
b = a;
a = t;

int quot[] = new int[a.length];
int remainder[] = new int[a.length];
while (!lsZero(b)) {
int t [] = copy (b);
divide (a, b, quot, remainder);
assign (b, remainder);
assign (a, t);

// В а хранится вычисленное значение НОД(а,Ь).
assign (gcd, a);

Метод modgcd получает окончательное значение НОД более быстро, поскольку не
тратит время на вычитание малых значений из больших в цикле w hile. Это отли­
чие — не просто деталь реализации; оно отражает фундаментальный сдвиг в под­
ходе алгоритма к решению задачи.
Вычисления, показанные на рис. 2.5 (и подытоженные в табл. 2.5), показывают
результат генерации 142 случайных я-значных чисел и вычисления НОД для всех
10011 пар этих чисел.

Семейства производительности

|

51

Рис. 2.5. Сравнение производительности методов gcd и modgcd
Таблица 2.5. Время (в мс) вычисления 10011 НОД
m odgcd

п

g cd

m o d g c d 2M/m o d g c d n

4

68

45

0,23

8

226

408

3,32

16

603

1315

2,67

32

1836

4050

3,04

64

5330

18392

2,90

128

20485

76180

3,84

Несмотря на то что реализация modgcd почти в три раза быстрее, чем соот­
ветствующая реализация gcd для тех же случайных данных, производительность
modgcd является квадратиннойу т.е. 0 (п 2). Анализ этого алгоритма является слож­
ной задачей, и в результате его выполнения оказывается, что наихудшие показатели
для modgcd достигаются для двух последовательных чисел Фибоначчи. Тем не менее
из табл. 2.5 можно сделать вывод о том, что алгоритм квадратичен, поскольку время
работы алгоритма возрастает примерно в четыре раза при удвоении размера задачи.
Были разработаны и более сложные алгоритмы для вычисления НОД, хотя при­
менение большинства из них нецелесообразно, за исключением разве что очень
больших целых чисел; их анализ свидетельствует о том, что данная задача имеет
и более эффективные по сравнению с квадратичными решения.

Экспоненциальная производительность
Рассмотрим замок с тремя числовыми дисками, каждый из которых содержит
цифры от 0 до 9. На каждом диске можно независимо один от другого устанавливать
одну из 10 цифр. Предположим, что у нас есть такой замок, но не открывающий его
52

|

Глава 2. Математика алгоритмов

код. Открытие такого замка является вопросом времени и некоторого труда, чтобы
испытать каждую из 1000 возможных комбинаций — от 000 до 999. Чтобы обобщить
эту задачу, предположим, что замок имеет п дисков, так что общее число возможных
вариантов равно 10”. Решение этой проблемы с помощью грубой силы рассматри­
вается как имеющее экспоненциальную производительность, или 0(10”), в данном
случае по основанию 10. Часто основанием экспоненты является 2; но такая произ­
водительность справедлива для любого основания b> 1.
Экспоненциальные алгоритмы практичны только для очень малых значений п.
Некоторые алгоритмы могут иметь экспоненциальное поведение в наихудшем слу­
чае и при этом активно использоваться на практике из-за их поведения в среднем
случае. Хорошим примером является симплекс-метод для решения задач линейного
программирования.

Резюме по асимптотическому росту
Алгоритм с лучшим асимптотическим ростом в конечном итоге будет выполнять­
ся быстрее, чем алгоритм с худшим асимптотическим ростом, независимо от реаль­
ных констант. Положение точки пересечения может быть различным в зависимости
от конкретных констант, но такая точка существует и может быть оценена эмпири­
чески. Кроме того, в ходе асимптотического анализа нас должен интересовать только
наиболее быстро растущий член функции £(«). По этой причине, если количество
операций алгоритма можно вычислить как c-n3+ d-n-log п, мы классифицируем этот
алгоритм как 0 (я 3), потому что и3 является доминирующим членом, который растет
гораздо быстрее, чем « log п.

Эталонные операции
Оператор ** языка программирования Python выполняет быстрое возведение
в степень. Пример вычисления 2**851 показан ниже:
150150336576094004599423153910185137226235191870990070733
557987815252631252384634158948203971606627616971080383694
109252383653813326044865235229218132798103200794538451818
051546732566997782908246399595358358052523086606780893692
34238529227774479195332149248

В Python вычисления относительно независимы от базовой платформы (напри­
мер, вычисление 2851 в Java или С на большинстве платформ вызовет целочисленное
переполнение). Но быстрое вычисление в Python дает результат, показанный выше.
Является ли преимуществом или недостатком абстрагирование Python от базовой
архитектуры? Рассмотрим две следующие гипотезы.

Эталонные операции

|

53

Гипотеза HI
Вычисление 2п носит систематический характер, не зависящий от значения п.
Гипотеза Н2
Большие числа (такие, как показанные ранее в развернутом виде) могут рас­
сматриваться так же, как и любое другое число, например 123827 или 997.
Чтобы опровергнуть гипотезу Н1, вычислим 10000 значений 2п. Общее время вы­
полнения для каждого значения п отображено на графике на рис. 2.6.

Рис. 2.6. Время вычисления 2х в языке Python
Как ни странно, производительность, похоже, имеет различное поведение,
одно — для х меньше 16, другое — для значений х около 145, а третье — для значе­
ний х более 200. Такое поведение показывает, что Python при возведении в степень
с использованием оператора ** применяет алгоритм возведения в степень путем
возведения в квадрат. Вычисление 2х вручную с использованием цикла for должно
приводить к квадратичной производительности.
Чтобы опровергнуть гипотезу Н2, мы проводим эксперимент, который выполняет
предварительное вычисление значения 2”, а затем оценивает время вычисления п-2п.
Общее время выполнения 10000 таких испытаний показано на рис. 2.7.
Почему точки на рис. 2.7 не находятся на прямой линии? При каком значении х
наблюдается разрыв? Как представляется, операция умножения (*) в Python перегру­
жена. Она выполняется по-разному в зависимости от того, являются ли перемножа­
емые значения числами с плавающей точкой или целыми числами, помещающимися
в одно машинное слово, или числами, которые настолько велики, что должны хра­
ниться в нескольких машинных словах (или наблюдается некоторое сочетание этих
крайностей).

54

|

Глава 2. Математика алгоритмов

Рис. 2.7. Время вычисления произведения больших чисел
Разрыв в графике наблюдается при х - {64,65} и, как представляется, соответству­
ет изменению способа хранения больших чисел с плавающей точкой. И здесь вновь
может обнаружиться замедление скорости роста вычислений, которое выявляется
только с помощью выполнения подобного хронометража.

Эталонные операции

|

55

____ 3
Строительные
блоки алгоритмов

Мы создаем программное обеспечение для решения задач. Но программисты
часто слишком сосредоточены на решении задачи, чтобы выяснять, нет ли уже го­
тового ее решения. Даже если программист знает, что задача уже была решена, не
очевидно, что существующий код будет соответствовать конкретной задаче, с ко­
торой работает программист. В конечном счете не так уж легко найти код на дан­
ном языке программирования, который мог бы быть легко изменен для решения
конкретной задачи.
Размышлять об алгоритмах можно по-разному. Многие практики просто ищут
алгоритм в книге или на веб-сайтах, копируют код, запускают его (а может быть,
даже проверяют), а затем переходят к следующей задаче. По нашему мнению, такой
процесс ничуть не улучшает понимание алгоритмов. В самом деле, такой подход мо­
жет вывести вас на кривую дорожку неверного выбора конкретной реализации ал­
горитма.
Вопрос заключается не только в том, как найти правильный алгоритм для реше­
ния вашей задачи, но и в том, чтобы хорошо в нем разобраться и понять, как он
работает, чтобы убедиться, что вы сделали правильный выбор. И, когда вы выбрали
алгоритм, как эффективно его реализовать? Каждая глава нашей книги объединяет
набор алгоритмов для решения стандартной задачи (например, для сортировки или
поиска) или связанных с ней задач (например, поиска пути). В этой главе мы пред­
ставим формат, используемый нами для описания алгоритмов в этой книге. Мы так­
же подытожим общие алгоритмические подходы, используемые для решения про­
граммных задач.

Формат представления алгоритма
Реальная мощь применения шаблона для описания каждого алгоритма проявля­
ется в том, что вы можете быстро сравнивать различные алгоритмы и выявлять об­
щие особенности в, казалось бы, совершенно разных алгоритмах. Каждый алгоритм
в книге представлен с использованием фиксированного набора разделов, соответ­
ствующих упомянутому шаблону. Мы можем также пропустить некоторый раздел,
если он не добавляет ничего ценного к описанию алгоритма, или добавить разделы
для освещения некоторой конкретной особенности алгоритма.

Название и краткое описание
Описательное название алгоритма. Мы используем это название для лаконичных
ссылок одних алгоритмов на другие. Когда мы говорим об использовании последо­
вательного поиска, это название точно передает, о каком именно алгоритме поиска
мы говорим. Название каждого алгоритма всегда выделено полужирным шрифтом.

Входные и выходные данные алгоритма
Описывает ожидаемый формат входных данных алгоритма и вычисленных им
значений.

Контекст применения алгоритма
Описание задачи, которое показывает, когда алгоритм является полезным и когда
его производительность будет наилучшей. Описание свойств задачи/решения, ко­
торые необходимо рассмотреть для успешной реализации алгоритма. Это те сооб­
ражения, которые должны привести вас к решению о выборе данного конкретного
алгоритма для вашей задачи.

Реализация алгоритма
Описание алгоритма с использованием реального рабочего кода с документацией.
Все исходные тексты решений можно найти в репозитории к книге.

Анализ алгоритма
Краткий анализ алгоритма, включая данные о производительности и информа­
цию, которая должна помочь вам понять поведение алгоритма. Хотя раздел, посвя­
щенный анализу, не предназначен для формального доказательства указанной про­
изводительности алгоритма, вы должны быть в состоянии понять, почему алгоритм
ведет себя именно таким образом. Чтобы пояснить описанное поведение алгоритмов,

58

|

Глава 3. Строительные блоки алгоритмов

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

Вариации алгоритма
Представляет вариации алгоритма или различные альтернативы.

Формат шаблона псевдокода
Каждый алгоритм в этой книге представлен с примерами кода, которые демон­
стрируют его реализацию на основных языках программирования, таких как Python,
С, C++ и Java. Для читателей, которые не знакомы со всеми этими языками, мы опи­
сываем каждый алгоритм с помощью псевдокода с небольшим примером, показыва­
ющим его выполнение.
Рассмотрим следующий пример описания производительности, которое имену­
ет алгоритм и четко классифицирует его производительность для всех трех случаев
(наилучший, средний, наихудший), описанных в главе 2, “Математика алгоритмов”.
Последовательный поиск

Наилучший: 0(1); средний, наихудший: О(и)
search (A,t)
for i=0 to n-1 do
if A[i] = t then
return true
return false
end

О

О Последовательное обращение к каждому элементу от 0 до п-1.

Описание псевдокода преднамеренно краткое. Ключевые слова и имена функций
приведены с использованием полужирного шрифта. Все переменные имеют имена,
записываемые строчными буквами, в то время как массивы записываются пропис­
ными буквами, а обращение к их элементам выполняется с помощью индексной
записи [ i ]. Отступы в псевдокоде показывают области видимости инструкций if
и циклов while и for.
Перед тем как рассматривать исходные тексты реализаций на конкретных язы­
ках программирования, следует ознакомиться с кратким резюме алгоритма. После
каждого резюме следует небольшой пример (наподобие показанного на рис. 3.1),
призванный облегчить понимание работы алгоритма. Эти рисунки показывают вы­
полнение алгоритмов в динамике, часто с изображением основных шагов алгоритма,
представленных на рисунке сверху вниз.
Формат шаблона псевдокода

|

59

Рис. 3.1. Пример выполнения
последовательного поиска

Формат эмпирических оценок
Мы подтверждаем производительность каждого алгоритма путем выполнения
ряда хронометражей решения задач, соответствующих индивидуальным алгорит­
мам. Приложение А содержит более подробную информацию о механизмах, ис­
пользуемых для хронометража. Для правильной оценки производительности набор
тестов состоит из множества к индивидуальных испытаний (обычно к> 10). Лучшее
и худшее выполнения отбрасываются, остальные же к- 2 испытания проходят статис­
тическую обработку с вычислением среднего значения и стандартного отклонения.
Экземпляры задач, приводимые в таблицах, обычно имеют размеры от п - 2 до 220.

Вычисления с плавающей точкой
Поскольку ряд алгоритмов в этой книге включает числовые вычисления, нам
нужно описать мощь и ограничения современных компьютеров в этой области.
Компьютеры выполняют основные вычисления со значениями, хранящимися в ре­
гистрах центрального процессора (CPU). По мере того, как компьютерные архитек­
туры эволюционировали от 8-разрядных процессоров Intel, популярных в 1970-х го­
дах, до сегодняшних получивших широкое распространение 64-битных архитектур
(например, процессоры Intel Itanium и Sun Microsystems Sparc), эти регистры сущес­
твенно выросли в размерах. Процессор часто поддерживает базовые операции — та­
кие, как сложение, умножение, вычитание и деление — для целочисленных значе­
ний, хранящихся в этих регистрах. Устройства для вычислений с плавающей точкой
(FPU) могут эффективно выполнять вычисления в соответствии со стандартом ШЕЕ
для бинарной арифметики с плавающей точкой (IEEE 754).
Математические вычисления на основе целочисленных значений (таких, как
логические значения, 8-битные байты и 16- и 32-разрядные целые числа) тради­
ционно являются наиболее эффективными вычислениями, выполняемыми про­
цессором. Программы часто оптимизированы таким образом, чтобы использовать
эту историческую разницу в производительности между вычислениями с целы­
ми числами и с числами с плавающей точкой. Однако в современных процессорах

60

|

Глава 3. Строительные блоки алгоритмов

производительность вычислений с плавающей точкой значительно улучшена. Поэто­
му важно, чтобы разработчики были ознакомлены со следующими вопросами про­
граммирования арифметики с плавающей точкой [28].

Производительность
Общепризнано, что вычисления с целочисленными значениями будут более эф­
фективными, чем аналогичные вычисления с плавающей точкой. В табл. 3.1 перечис­
лены значения времени выполнения 10000000 операций, включая результаты в Linux
времен первого издания этой книги и результаты Sparc Ultra-2 1996 года. Как видите,
производительность отдельных операций может значительно отличаться от платфор­
мы к платформе. Эти результаты показывают также огромные улучшения процессоров
в течение последних двух десятилетий. Для некоторых результатов указано нулевое
время выполнения, так как они быстрее, чем имеющиеся средства хронометража.
Таблица 3.1. Время (в секундах) выполнения 10000000 операций
Операция

Sparc Ultra-2

Linux i686

В настоящее время

32-битное целое СМР

0,811

0,0337

0,0000

32-битное целое MUL

2,372

0,0421

0,0000

32-битное float MUL

1,236

0,1032

0,02986

64-битное double MUL

1,406

0,1028

0,02987

32-битное float DIV

1,657

0,1814

0,02982
0,02980

2,172

0,1813

36,891

0,2765

0,02434

32-битное целое DIV

3,104

0,2468

0,0000

32-битное double SQRT

3,184

0,2749

0,0526

64-битное double DIV
128-битное double MUL

Ошибка округления
Все вычисления с использованием значений с плавающей точкой могут привести
к ошибкам округления, вызванным бинарным представлением чисел с плавающей
точкой. В общем случае число с плавающей точкой является конечным представле­
нием, разработанным для приближения действительного числа, бинарное представ­
ление которого может быть бесконечным. В табл. 3.2 показана информация о пред­
ставлениях чисел с плавающей точкой и представлении конкретного значения 3.88f.
Таблица 3.2. Представления чисел с плавающей точкой
Тип

Знак, бит

Экспонента, бит

Мантисса, бит

float

1

8

23

double

1

11

52

П рим ер бинарного представления 3.88f как 0х407851ес

01000000 01111000 01010001 11101100 (всего 32 бита)
seeeeeee emrnmmmmm лж1шшшшшт гштштшгашп

Вычисления с плавающей точкой

|

61

Тремя следующими за 3.88f 32-битными представлениями чисел с плавающей
точкой (и их значениями) являются:
•

0x407851ed: 3.8800004

•

0х407851ее: 3.8800006

•

0x407851ef: 3.8800008

Вот некоторые случайным образом выбранные 32-битные значения с плавающей
точкой:
•

0xlaec9fae: 9.786529Е-23

•

0x622be970: 7.9280355Е20

•

0х18а4775Ь: 4.2513525Е-24

В 32-разрядном значении с плавающей точкой один бит используется для знака,
8 битов — для экспоненты и 23 бита — для мантиссы. В представлении Java “степень
двойки может определяться путем трактовки битов экспоненты как положительного
числа с последующим вычитанием из него значения смещения. Для типа float смещение
равно 126” [59]. Если сохраненная экспонента равна 128, ее фактическое значе­
ние равно 128-126, или 2.
Для достижения наибольшей точности мантисса всегда нормализована таким
образом, что крайняя слева цифра всегда равна 1; этот бит в действительности не
должен храниться, но воспринимается FPU как часть числа. В предыдущем примере
мантисса представляет собой
. [ 1]11110000101000111101100 =

[1/2] +1/4+1/8+1/16+1/32+1/1024+1/4096+1/65536+1/131072+1/262144+ 1/524288+
+1/20974152+1/4194304,
что равно в точности значению 0.9700000286102294 921875.
При хранении с использованием этого представления значения 3.8 8 f при­
ближенное значение равно + 1-0,9700000286102294921875-22, т.е. в точности
3.88000011444091796875. Ошибка этого значения составляет -0.0000001. Наиболее
распространенный способ описания ошибок чисел с плавающей точкой — исполь­
зование относительной ошибкиу которая вычисляется как отношение абсолютной
ошибки к точному значению. В данном случае относительная ошибка составляет
0.0000001144091796875/3.88, или 2.9Е-8. Относительные ошибки достаточно часто
оказываются меньше одной миллионной.

Сравнение значений с плавающей точкой
Поскольку значения с плавающей точкой являются всего лишь приблизительны­
ми, простейшие операции с плавающей точкой становятся подозрительными. Рас­
смотрим следующую инструкцию:
if (х == у) { ... }
62

|

Глава 3. Строительные блоки алгоритмов

Действительно ли эти два числа с плавающей запятой должны быть точно рав­
ны? Или достаточно, чтобы они были просто приблизительно равны (что обычно
описывается знаком “«*)? Не может ли случиться так, что два значения хотя и раз­
личны, но достаточно близки, так что они должны рассматриваться как одно и то же
значение? Рассмотрим практический пример: три точки, р0= (аУЬ), p ^ic yd ) и р2= (е,Д
в декартовой системе координат определяют упорядоченную пару отрезков (p0,pj)
и (pj,p2). Значение выражения (c - a ) ( f- b ) - ( d - b ) ( e - a ) позволяет определить, коллинеарны ли эти два отрезка (т.е. находятся ли они на одной линии). Если это значение
•

=0, то отрезки коллинеарны;

•

<0, то отрезки повернуты влево (против часовой стрелки);

•

>0, то отрезки повернуты вправо (по часовой стрелке).

Чтобы показать, как при вычислениях Java могут возникать ошибки с плавающей
точкой, определим три точки, используя значения от а до / и з табл. 3.3.
Таблица 3 3 . Арифметические ошибки с плавающей точкой
32-битное значение

(flo a t)

64-битное значение

(double)

0.3333333333333333

1.6666666

1.6666666666666667

33.0

33.0

165.0

165.0

19.0

19.0

LO
II

о=1/3
Ь = 5/3
с =33
d= 165
е= 19

0.33333334

95.0

95.0

(c-a)(f-b)-{d-b)(e-a)

4.8828125Е-4

-4.547473508864641Е-13

Как вы можете легко определить, три точки, р0, р х и р2, коллинеарны и лежат
на прямой у-5-х. При вычислении тестового значения с плавающей точкой для про­
верки коллинеарности на результат вычисления влияют имеющиеся ошибки, при­
сущие арифметике с плавающей точкой. Использование при вычислениях 32-битных
значений с плавающей точкой дает значение 0,00048828125; использование 64-бит­
ных значений дает очень небольшое отрицательное число. Этот пример показывает,
что как 32-, так и 64-разрядные представления чисел с плавающей точкой не дают
истинные значения математических вычислений. И в рассмотренном случае резуль­
таты вычислений приводят к разногласиям по поводу того, представляют ли точки
угол по часовой стрелке, против часовой стрелки или коллинеарные отрезки. Таков
уж мир вычислений с плавающей точкой.
Одним из распространенных решений для этой ситуации является введение не­
большого значения б для определения операции
(приблизительного равенства)
между двумя значениями с плавающей точкой. Согласно этому решению, если
Iх-у\<8, то мы считаем х и у равными. Тем не менее даже при такой простой мере

Вычисления с плавающей точкой

63

возможна ситуация, когда х ~ у и
но при этом условие х - z не выполняется. Это
нарушает математический принцип транзитивности и осложняет написание пра­
вильного кода. Кроме того, это решение не решает задачу коллинеарности, в которой
при принятии решения используется знак полученного значения (нулевое, положи­
тельное или отрицательное).

Специальные значения
Хотя все возможные 64-битные значения могут представлять допустимые числа
с плавающей точкой, стандарт IEEE определяет несколько значений (табл. 3.4), ко­
торые интерпретируются как специальные значения (и часто не могут участвовать
в стандартных математических вычислениях, таких как сложение или умножение).
Эти значения были разработаны для упрощения восстановления после распростра­
ненных ошибок, таких как деление на нуль, квадратный корень из отрицательного
числа, переполнение и потеря значи