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

Когда разработчики «Википедии» обсуждали организацию коллективной работы, они создали блок-схему дискуссии. Договариваться проще, если все инициативы перед глазами и объединены в общую картину (рис. 1.1).

Компьютерный код, как и изображенный выше процесс редактирования вики-страницы, по существу является процессом. Программисты часто пользуются блок-схемами для изображения вычислительных процессов на бумаге. Чтобы другие могли понимать ваши блок-схемы, вы должны соблюдать следующие рекомендации[3]:

• записывайте состояния и инструкции внутри прямоугольников;

• записывайте принятие решений, когда процесс может пойти различными путями, внутри ромбов;

• никогда не объединяйте инструкции с принятием решений;

• соединяйте стрелкой каждый последующий шаг с предыдущим;

• отмечайте начало и конец процесса.

Рис. 1.1. Редакционный процесс в «Википедии»[4]

Рассмотрим составление блок-схемы на примере задачи поиска наибольшего из трех чисел (рис. 1.2).

Рис. 1.2. Поиск наибольшего из трех чисел

Так же, как блок-схемы, псевдокод выражает вычислительные процессы. Псевдокод — это код, удобный для нашего восприятия, но непонятный для машины. Следующий пример передает тот же процесс, что был изображен на рис. 1.2. Задержитесь на минуту и проверьте, как он работает с разными значениями A, B и C[5].

function maximum(A, B, C)

····if A > B

·········if A > C

··············max ← A

·········else

··············max ← C

····else

·········if B > C

··············max ← B

·········else

··············max ← C

····print max

Заметили, что этот пример полностью игнорирует синтаксические правила языков программирования? В псевдокод можно вставлять даже разговорные фразы! Когда вы пишете псевдокод, дайте своей творческой мысли течь свободно — как при составлении блок-схем (рис. 1.3 ).

Рис. 1.3. Псевдокод в реальной жизни[6]

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

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

Начнем с того, что именно требуется определить; w и l — это размеры пастбища; w × l — его площадь. Сделать площадь максимальной означает использовать всю проволоку, потому мы устанавливаем связь между w и l, с одной стороны, и 100 мотками, с другой:

l

w

A = w × l

100 = 2w + 3l

Подберем w и l, при которых площадь A будет максимальной.

Подставив l из второго уравнения в первое, получаем:

Да это же квадратное уравнение! Его максимум легко найти при помощи формулы корней квадратного уравнения, которую проходят в средней школе. Квадратные уравнения так же важны для программиста, как мультиварка — для повара. Они экономят время. Квадратные уравнения помогают быстрее решать множество задач, а это для вас самое главное. Повар знает свои инструменты, вы должны знать свои. Математическое моделирование вам просто необходимо. А еще вам потребуется логика.

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

Рис. 1.4. Логика программиста[7]

Для начала мы поэкспериментируем с логическими высказываниями и операторами. Затем научимся решать задачи с таблицами истинности и увидим, как компьютеры опираются на логику.

В математике переменные и операторы (+, ×, −, …) используются для моделирования числовых задач. В математической логике переменные и операторы указывают на достоверность. Они выражают не числа, а истинность (true) или ложность (false). Например, достоверность выражения «Если вода в бассейне теплая, то я буду плавать» основывается на достоверности двух вещей, которые можно преобразовать в логические переменные A и B:

A: Вода в бассейне теплая.

B: Я плаваю.

Они либо истинны (true), либо ложны (false)[8]. A = True обозначает теплую воду в бассейне, B = False обозначает «Я не плаваю». Переменная B не может быть наполовину истинной, потому что я не способен плавать лишь отчасти. Зависимость между переменными обозначается символом , условным оператором. A B выражает идею, что A = True влечет за собой B = True:

A B: если вода в бассейне теплая, то я буду плавать.

При помощи других операторов можно выражать другие идеи. Для отрицания идеи используется знак! оператор отрицания.!A противоположно A:

!A: Вода в бассейне холодная.

!B: Я не плаваю.

Противопоставление. Если дано A B, и я при этом не плаваю, что можно сказать о воде в бассейне? Теплая вода влечет за собой плавание, потому, если его нет, вода в бассейне не может быть теплой. Каждое условное выражение имеет противопоставленный ему эквивалент:

Для любых двух переменных A и B

A B тождественно! B !A.

Еще пример: если вы не умеете писать хороший код, значит, вы не прочли эту книгу. Противопоставлением данному суждению является такое: если вы прочли эту книгу, значит, вы умеете писать хороший код. Оба предложения сообщают одно и то же, но по-разному[9].

Двусторонняя условная зависимость. Обратите внимание, что высказывание «Если вода в бассейне теплая, то я буду плавать» не означает: «Я буду плавать только в теплой воде». Данное высказывание ничего не говорит насчет холодных бассейнов. Другими словами, A B не означает B A. Чтобы выразить оба условных суждения, используйте двустороннюю условную зависимость:

A <—> B: Я буду плавать, если и только если вода в бассейне теплая.

Здесь теплая вода в бассейне равнозначна тому, что я буду плавать: знание о воде в бассейне означает знание о том, что я буду плавать, и наоборот. Опять же, остерегайтесь обратной ошибки: никогда не предполагайте, что B A следует из A B.

AND, OR и XOR. Эти логические операторы — самые известные, поскольку они часто записываются в исходном коде в явном виде — AND (И), OR (ИЛИ) и XOR (исключающее ИЛИ). AND возвращает True, если все идеи истинны; OR возвращает True, если любая идея истинна; XOR возвращает True, если идеи взаимоисключающие. Представим вечеринку, где подают водку и вино:

A: Вы пили вино.

B: Вы пили водку.

A OR B: Вы пили.

A AND B: Вы пили и то и другое.

A XOR B: Вы пили, не смешивая.

Проверьте, правильно ли вы понимаете, как работают эти операторы. В табл. 1.1 перечислены все возможные комбинации двух переменных. Обратите внимание, что A B тождественно! A OR B, а A XOR B тождественно!(A <—> B).

Таблица 1.1. Логические операции для четырех возможных комбинаций A и B

Булева алгебра[10] позволяет упрощать логические выражения точно так же, как элементарная алгебра упрощает числовые.

Ассоциативность. Для последовательностей, состоящих только из операций AND или OR, круглые скобки не имеют значения. Так же, как последовательности только из операций сложения или умножения в элементарной алгебре, эти операции могут вычисляться в любом порядке.

A AND (B AND C) = (A AND B) AND C;

A OR (B OR C) = (A OR B) OR C.

Дистрибутивность. В элементарной алгебре мы раскрываем скобки: a × (b + c) = (a × b) + (a × c). Точно так же и в логике выполнение операции AND после OR эквивалентно выполнению операции OR над результатами операций AND и наоборот:

A AND (B OR C) = (A AND B) OR (A AND C);

A OR (B AND C) = (A OR B) AND (A OR C).

Правило де Моргана[11]. Одновременно лета и зимы не бывает, поэтому у нас либо не лето, либо не зима. С другой стороны, оба выражения «не лето» и «не зима» истинны, если (и только) у нас не тот случай, когда либо лето, либо зима. Согласно этой логике, выполнение операций AND может быть сведено к операциям OR и наоборот:

!(A AND B) =!A OR! B;

!A AND!B =!(A OR B).

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

Моделируя эту задачу в логических переменных, можно в одном выражении сформулировать условия, когда сервер выходит из строя:

A: Сервер перегревается.

B: Кондиционирование отключено.

C: Не работает кулер.

D: Сервер вышел из строя.

(A AND B) OR (A AND C) D.

Используя правило дистрибутивности, выведем за скобки A:

A AND (B OR C) D.

Сервер работает, когда! D. Противопоставление записывается так:

!D !(A AND (B OR C)).

Применим правило де Моргана и раскроем скобки:

!D !A OR!(B OR C).

Воспользуемся правилом де Моргана еще раз:

!D !A OR (!B AND!C).

Данное выражение нам говорит, что когда сервер работает, мы имеем либо! A (он не перегревается), либо! B AND!C (все в порядке и с кондиционированием воздуха, и с кулером).

Еще один способ анализа логических моделей состоит в сверке данных со всевозможными сочетаниями ее переменных. Каждой переменной в таблице истинности соответствует свой столбец. Строки представляют комбинации состояний переменных.

Рис. 1.5. Таблицы со всеми возможными сочетаниями от одной до пяти логических переменных

Одна переменная требует двух строк: в одной она имеет значение True, в другой — False. Чтобы добавить переменную, нужно удвоить число строк. Новой переменной задается True в исходных строках и False — в добавленных (рис. 1.5). Размер таблицы истинности увеличивается вдвое с каждым добавлением переменной, поэтому такую таблицу оправданно использовать лишь в случаях, когда переменных немного[12].

Давайте посмотрим, как можно использовать таблицу истинности для анализа задачи.

Хрупкая система Предположим, что мы должны создать систему управления базами данных с соблюдением следующих технических требований:

1) если база данных заблокирована, то мы можем сохранить данные;

2) база данных не должна блокироваться при заполненной очереди запросов на запись;

3) либо очередь запросов на запись полна, либо полон кэш;

4) если кэш полон, то база данных не может быть заблокирована.

Возможно ли это? При каких условиях станет работать такая система?

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

A: База данных заблокирована	1: A —> B
B: Есть возможность сохранить данные	2:!(A AND C).
C: Очередь запросов на запись полна	3: C OR D.
D: Кэш полон	4: D —>!A.

Далее создадим таблицу истинности со всеми возможными сочетаниями переменных (табл. 1.2). Дополнительные столбцы добавлены для проверки соблюдения технических требований.

Таблица 1.2. Таблица истинности для проверки четырех выражений

Все технические требования удовлетворяются в состояниях с 9-го по 11-е и с 13-го по 15-е. В этих состояниях A = False, а значит, база данных не может быть заблокирована никогда. Обратите внимание, что кэш не заполнен лишь в состояниях 10 и 14.

Чтобы проверить, чему вы научились, попробуйте разгадать загадку «Кто держит зебру?»[13]. Это известная логическая задача, ошибочно приписываемая Альберту Эйнштейну. Говорят, что только 2 % людей могут ее решить, но я сильно сомневаюсь. Используя большую таблицу истинности и правильно упрощая и объединяя логические высказывания, вы ее разгадаете, я уверен в этом.

Всегда, имея дело с ситуациями, допускающими один из двух вариантов, помните: их можно смоделировать с помощью логических переменных. Благодаря этому очень легко получать выражения, упрощать их и делать выводы.

А теперь давайте взглянем на самое впечатляющее применение логики: проектирование электронно-вычислительных машин.

Группы логических переменных могут представлять числа в двоичной форме[14]. Логические операции в случае с двоичными числами могут объединяться для расчетов. Логические вентили выполняют логические операции с электрическим током. Они используются в электрических схемах, выполняющих вычисления на сверхвысоких скоростях.

Логический вентиль получает значения через входные контакты, выполняет работу и передает результат через выходной контакт. Существуют логические вентили AND, OR, XOR и т. д. Значения True и False представлены электрическими сигналами с высоким и низким напряжением соответственно. Сложные логические выражения можно вычислять таким образом практически мгновенно. Например, электрическая схема на рис. 1.6 суммирует два числа.

Давайте посмотрим, как работает эта схема. Не поленитесь, проследите за ходом выполнения операций, чтобы понять, как устроена магия (рис. 1.7).

Рис. 1.6. Схема суммирования двухразрядных чисел, передаваемых парами логических переменных (A₁A₀ и B₁B₀) в трехразрядное число (S₂S₁S₀)

Рис. 1.7. Вычисление 2 + 3 = 5 (в двоичном формате это 10 + 11 = 101)

Чтобы воспользоваться преимуществом этого быстрого способа вычислений, мы преобразуем числовые задачи в двоичную (логическую) форму. Таблицы истинности помогают моделировать и проверять схемы. А булева алгебра — упрощать выражения и, следовательно, схемы.

Когда-то логические вентили изготавливали с использованием больших, неэффективных и дорогих электрических реле. Когда на смену реле пришли транзисторы, стало возможным массовое производство логических вентилей. Люди находили все новые и новые способы делать транзисторы меньше[15]. Принципы работы современного центрального процессора (ЦП) по-прежнему построены на булевой алгебре. Современный ЦП — это просто схема, которая состоит из миллионов микроскопических контактов и логических вентилей, управляющих электрическими потоками информации.

Важно уметь считать вещи правильно, ведь в случае с вычислительными задачами вам придется делать это много раз[16]. Математика далее будет еще более сложной, чем раньше, но не пугайтесь. Кое-кто полагает, что ему не стать хорошим программистом только потому, что, как ему кажется, математик он так себе. Если хотите знать, лично я завалил школьный экзамен по математике , и все же я стал тем, кем хотел . В школе дают совсем не ту математику, которая делает людей хорошими программистами.

Никто не захочет зубрить формулы и пошаговые процедуры, если он уже сдал выпускные экзамены. Если такая информация вдруг понадобится — ее легко отыскать в Интернете. Расчеты не обязательно делать от руки на бумаге. От программиста в первую очередь требуется интуиция. Познания в комбинаторике и умение решать комбинаторные задачи развивает эту интуицию. Так что давайте поработаем с несколькими инструментами по порядку: с умножением, перестановками, сочетаниями и суммами.

Если некоторое событие происходит n разными способами, а другое событие — m разными способами, то число разных способов, которыми могут произойти оба события, равно n × m. Вот пара примеров.

Две цифры можно набрать 100 способами (00–99), букву — 26 способами (A — Z). Следовательно, всего существует 100 × 26 = 2600 PIN-кодов. В худшем случае, чтобы подобрать правильный, нам придется перепробовать их все. Через 2600 секунд (то есть через 43 минуты) мы его точно взломаем.

До начала набора есть всего один вариант состава — вы сами. Далее каждый бросок монеты удваивает число возможных вариантов. Это должно быть сделано 23 раза, таким образом, вам нужно посчитать, чему равно 2 в степени:

вариантов команды.

Обратите внимание, что один из этого множества вариантов — когда в команде состоите только вы.

Если у нас n элементов, то мы можем упорядочить их n! разными способами. Факториал числа имеет взрывной характер, даже с малыми значениями n он дает огромные числа. На случай, если вы с ним не знакомы:

n! = n × (n — 1) × (n — 2) … × 2 × 1.

Легко заметить, что n! — это общее количество способов упорядочивания n элементов. Сколькими способами можно выбрать первый элемент из n? После того как он будет выбран, сколькими способами можно выбрать второй? Сколько вариантов останется для третьего? Подумайте об этом некоторое время, а потом переходите к примерам[17].

Любая перестановка 15 городов дает новый маршрут. Факториал — это количество различных комбинаций, так что всего существует 15! = 15 × 14 × … × 1 ≈ 1,3 трлн маршрутов. Число микросекунд, которые уйдут на их вычисление, примерно эквивалентно 15 дням. Будь у вас не 15, а 20 городов, вам бы понадобилось 77 тысяч лет.

Мы должны подсчитать количество комбинаций по 6 нот из 13. Чтобы исключить неиспользуемые ноты, нужно остановить вычисление факториала после шестого множителя. Формально  — это количество возможных комбинаций m из n возможных элементов. В нашем случае получится:

= 1 235 520 мелодий.

Чтобы их все прослушать, потребуется 343 часа, так что вам лучше убедить девушку найти идеальную мелодию каким-нибудь другим путем.

Факториал n! дает завышенное число способов упорядочивания n элементов, если некоторые из них одинаковые. Лишние комбинации, где такие элементы просто оказываются на других позициях, не должны учитываться.

Если в последовательности из n элементов r идентичны, существуют r! способов переупорядочить их. То есть n! включает r! таких комбинаций. Чтобы получить число уникальных комбинаций, нужно разделить n! на этот излишек. Например, число различных сочетаний букв E в CODE ENERGY равняется .

Ученый хочет выполнить моделирование на всех возможных сегментах ДНК, где есть такое количество пар нуклеотидов. Сколько задач ему предстоит выполнить?

Сначала вычислим все возможные комбинации этих 23 пар нуклеотидов. Затем, чтобы учесть повторяющиеся пары нуклеотидов A-T и G-C, разделим результат на 9! и на 14! и получим:

 вариантов.

Но задача еще не решена. Нужно учесть ориентацию пар нуклеотидов.

Следующие два примера не тождественны:

Для каждой последовательности из 23 пар нуклеотидов существует 2²³ различных сочетаний ориентации. Потому общее количество комбинаций равно:

817 190 × 2²³ ≈ 7 трлн.

И это только для крошечной последовательности всего из 23 пар нуклеотидов, где мы знаем распределение! Наименьшая воспроизводимая ДНК, которая известна на сегодняшний день, — это ДНК крохотного цирковируса свиней, и в ней 1800 пар нуклеотидов. Код ДНК и жизнь в целом с технологической точки зрения по-настоящему удивительны. Просто с ума можно сойти: ДНК человека имеет около 3 млрд пар нуклеотидов, продублированных в каждой из 3 трлн клеток тела.

Представьте колоду из 13 игральных карт только пиковой масти . Сколькими способами вы сможете раздать шесть карт своему сопернику? Мы уже видели, что — это количество перестановок 6 карт из 13. Поскольку порядок их следования не имеет значения, нужно разделить это число на 6! чтобы получить

 комбинаций.

Бином — это количество способов, которыми можно извлечь m элементов из ряда, состоящего из n элементов, независимо от порядка их следования:

Конструкция в левой части (запись бинома) читается как «из n по m»[18].

Шахматная доска поделена на 64 клетки, 8 × 8. Число способов выбрать 8 клеток из 64 составляет млрд[19].

Подсчет сумм последовательностей часто встречается при решении комбинаторных задач. Суммы последовательных чисел обозначаются прописной буквой «сигма» (). Такая форма записи показывает, как выражение будет суммироваться для каждого значения i:

выражение с участием i.

Например, суммирование первых пяти нечетных чисел записывается так:

.

Обратите внимание: чтобы получить слагаемые 1, 3, 5, 7 и 9, вместо i последовательно используются числа от 0 до 4 включительно. Следовательно, сумма первых n натуральных чисел составляет:

Когда гениальному математику Гауссу было 10 лет, он устал от суммирования натуральных чисел одного за другим по порядку и нашел такой ловкий прием:

Догадаетесь, каким образом Гаусс это обнаружил? Объяснение приема приведено в приложении II. Давайте посмотрим, как можно его использовать для решения следующей задачи.

Любая пара дней между сегодняшним (день 1) и последним (день 30) допустима при условии, что возвращение будет в тот же день или позже, чем отъезд. Следовательно, 30 пар начинаются с 1-го дня, 29 пар начинаются со 2-го дня, 28 — с 3-го и т. д. И есть всего одна пара, приходящаяся на последний день. Таким образом, 30 + 29 + … + 2 + 1 — общее количество пар, которое нужно рассмотреть. Мы можем записать это как  и использовать удобную формулу Гаусса:

пар.

Кроме того, мы можем решить эту задачу при помощи комбинаций, выбрав 2 дня из 30. Порядок не имеет значения: на более ранний день придется отъезд, на более поздний — возвращение. Таким образом, мы получим . Что-то не то… Дело в том, что мы должны учесть еще и случаи, когда прибытие и отъезд приходятся на одну дату. Так как дней всего 30, следовательно, .

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

Рис. 1.8. Случайное число[20]

Сейчас мы применим наши навыки решения комбинаторных задач к вычислению вероятностей. Затем мы узнаем, каким образом различные типы событий используются для решения задач. Наконец, мы увидим, почему азартные игроки проигрываются в пух и прах.

Бросок кубика имеет шесть возможных результатов: 1, 2, 3, 4, 5 и 6. Шансы получить 4, следовательно, составляют . А какова вероятность выпадения нечетного числа? Это может произойти в трех случаях (когда на кубике будет 1, 3 или 5), потому шансы составляют . Вероятность того, что некое событие произойдет, выражается такой формулой:

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

Мы уже убедились, что существует 2²³ = 8 388 608 возможных вариантов состава команды. Вам придется рассчитывать только на себя в одном-единственном случае: если в результате подбрасывания монеты выпадут 23 «решки» подряд. Вероятность такого события равна P(никто) = . Если посмотреть на это с высоты птичьего полета, то вероятность того, что конкретный рейс коммерческой авиакомпании потерпит крушение, составляет порядка 1 из 5 млн.

Если вы одновременно бросаете монету и кубик, то шанс получить «орел» и 6 равняются , или 8 %. Когда исход одного события не влияет на исход другого, их называют независимыми. Вероятность получить сочетание конкретных результатов двух независимых событий равна произведению вероятностей каждого из них.

Если вы решите использовать три дешевых диска, то потеряете данные, только если все три выйдут из строя. Вероятность того, что это произойдет, равняется . Риск потери данных оказывается гораздо ниже, чем в случае с дорогим диском, а заплатите вы всего 60 % от его стоимости.

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

Перечисленные события несовместны: нельзя выбрать и основной, и профессиональный тарифы одновременно. Вероятность, что пользователь подпишется на платный тариф, равняется 0,2 + 0,1 = 0,3.

Выпавшее на кубике количество очков не может одновременно оказаться кратным трем (3, 6) и не делящимся на три, но оно определенно будет относиться к одной из этих категорий чисел. Вероятность получить результат, кратный трем, равняется , следовательно, вероятность получить число, которое не делится на три, равняется . Когда два несовместных события охватывают все возможные варианты, их называют взаимодополняющими, или соподчиненными. Сумма вероятностей взаимодополняющих событий равна 100 %.

Вероятность поразить врага равна 0,2 + 0,2 + 0,2 + 0,2 + 0,2 = 1, или 100 %, верно? Неверно! Никогда не суммируйте вероятности независимых событий, не совершайте распространенной ошибки. Вместо этого используйте взаимодополняющие события дважды следующим образом.

• 20 %-ный шанс поразить врага — взаимодополняющий для 80 %-го шанса промахнуться. Вероятность того, что не попадут все башни, составляет 0,8⁵ ≈ 0,33.

• Событие «все башни промахнулись» — взаимодополняющее для события «по крайней мере одна башня попала». Значит, вероятность остановить врага равна 1–0,33 = 0,67.

Если вы подбросили монету 10 раз и получили 10 «орлов», увеличилась ли от этого вероятность, что на 11-м броске выпадет «решка»? Или будет ли вероятность выигрыша в лотерею комбинации из шести последовательных чисел от 1 до 6 ниже, чем любой другой комбинации?

Не становитесь жертвой «заблуждения игрока»! Уже случившееся никак не влияет на результат независимого события. Никак. Никогда. В по-настоящему случайно разыгрываемой лотерее вероятность выпадения любого конкретного числа точно такая же, как любого другого. Нет никакой закономерности, согласно которой числа, редко выпадавшие в прошлом, должны чаще выпадать в будущем.

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

Да, это трудно посчитать. Если вы будете долго искать в Интернете, то в конечном счете придете к биномиальному распределению. Вы можете визуализировать его в Wolfram Alpha[21], набрав: B(23,l/2) <= 7.

Будет ли быстрее отсортирована колода карт, которая уже почти упорядочена? Объем входящих данных — не единственная характеристика, влияющая на количество требуемых алгоритмом операций. Когда алгоритм может иметь разные значения T(n) для одного n, мы обращаемся к случаям, или, говоря по-другому, вариантам развития событий.

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

• Худший случай — когда для любых входящих данных данного объема требуется максимальное количество операций. Во многих алгоритмах сортировки такое случается, когда данные на входе передаются в обратном порядке.

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

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

Рис. 2.1. Оценка времени[22]

Временную сложность алгоритма определяют, подсчитывая основные операции, которые ему требуются для гипотетического набора входных данных объема n. Мы продемонстрируем это на примере сортировки выбором, алгоритма сортировки с вложенным циклом. Внешний цикл for обновляет текущую позицию, с которой ведется работа, внутренний цикл for выбирает элемент, который затем подставляется в текущую позицию[23]:

function selection_sort(list)

····for current ← 1 … list.length — 1

········smallest ← current

········for i ← current + 1 … list.length

············if list[i] < list[smallest]

················smallest ← i

·······list.swap_items(current, smallest)

Давайте посмотрим, что произойдет со списком из n элементов в худшем случае. Внешний цикл совершит n — 1 итераций и в каждой из них выполнит две операции (одно присвоение и один обмен значениями), всего 2n-2 операций. Внутренний цикл сначала выполнится n — 1 раз, затем n — 2 раза, n — 3 раза и т. д. Мы уже знаем, как суммировать эти типы последовательностей[24]:

В худшем случае условие if всегда соблюдается. Это означает, что внутренний цикл выполнит одно сравнение и одно присвоение  раз, отсюда n² — n операций. В целом стоимость алгоритма 2n — n складывается из операций внешнего цикла и n² операций внутреннего цикла. Мы получаем временную сложность:

T(n) = n² + n — 2.

Что дальше? Если размер нашего списка был n = 8, а затем мы его удвоили, то время сортировки увеличится в 3,86 раза:

.

Если мы снова удвоим размер списка, нам придется умножить время на 3,9. Дальнейшие удвоения дадут коэффициенты 3,94, 3,97, 3,98. Заметили, как результат становится все ближе и ближе к 4? Это значит, что сортировка 2 млн элементов потребует в четыре раза больше времени, чем сортировка 1 млн элементов.

Допустим, объем входящих данных алгоритма очень велик, и мы его еще увеличиваем. Чтобы предсказать, как изменится время выполнения, нам не нужно знать все члены функции T(n). Мы можем аппроксимировать T(n) по ее наиболее быстрорастущему члену, который называется доминантным членом.

Мы уже убедились, что сортировка выбором подчиняется T(n) = = n² + n — 2. Наиболее быстро растущим членом является n², поэтому мы можем записать T(n) ≈ n². Приняв, что в одной коробке лежит n карточек, мы находим:

Вам потребуется приблизительно 100 × (2 часа) = 200 часов! А что, если сортировать по другому принципу? Например, есть метод под названием «сортировка пузырьком», временная сложность которого определяется формулой T(n) = 0,5n² + 0,5n. Наиболее быстро растущий член тогда даст T(n) ≈ 0,5n², следовательно:

Рис. 2.2. Уменьшение масштаба n², n² + n — 2 и 0,5n² + 0,5n с увеличением n

Коэффициент 0,5 сам себя аннулирует! Понять мысль, что оба выражения — n² — n — 2 и 0,5n² + 0,5n — растут как n², не так-то просто. Почему доминантный член функции игнорирует все другие числа и оказывает наибольшее влияние на рост? Давайте попытаемся эту концепцию представить визуально.

На рис. 2.2 изображены графики двух временных сложностей, которые мы рассмотрели, рядом с графиком n² на разных уровнях масштабирования. По мере увеличения значения n графики, судя по всему, становятся все ближе и ближе. На самом деле вместо точек в функции T(n) = ∙ n² + ∙ n + ∙ вы можете подставить любые числа, и она по-прежнему будет расти как n².

Запомните, такой эффект сближения кривых работает, если наиболее быстро растущий член — одинаковый. График функции с линейным ростом (n) никогда не будет сближаться с графиком квадратичного роста (n²), который, в свою очередь, никогда не догонит график, имеющий кубический рост (n³).

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

Итеративная стратегия состоит в использовании циклов (например, for и while) для повторения процесса до тех пор, пока не окажется соблюдено некое условие. Каждый шаг в цикле называется итерацией. Итерации очень полезны для пошагового просмотра входных данных и применения одних и тех же операций к каждой их порции. Вот пример.

Мы можем сравнивать в цикле верхние элементы двух списков (рис. 3.1).

Данный процесс можно записать в виде одного цикла с условием продолжения while loop:

function merge(sea, fresh)

····result ← List.new

····while not (sea.empty and fresh.empty)

········if sea.top_item > fresh.top_item

············fish ← sea.remove_top_item

·······else

···········fish ← fresh.remove_top_item

·····result.append(fish)

return result

Рис. 3.1. Объединение двух отсортированных списков в третий, тоже отсортированный

Он выполняет обход всех названий рыб из входных списков, совершая фиксированное число операций для каждого элемента[28]. Следовательно, алгоритм слияния merge имеет сложность O(n).

В предыдущей главе мы увидели, как функция сортировки выбором selection_sort использует один цикл, вложенный в другой. Сейчас мы научимся использовать вложенный цикл для вычисления степенного множества. Если дана коллекция объектов S, то степенное множество S есть множество, содержащее все подмножества S[29].

Любой аромат состоит из подмножества F, потому его степенное множество содержит все возможные ароматы. Это степенное множество вычисляется итеративно. Для нулевого множества цветов есть всего один вариант — без запаха. В случае, когда мы берем очередной цветок, мы дублируем уже имеющиеся ароматы и добавляем его к ним (рис. 3.2).

Этот процесс можно описать при помощи циклов. Во внешнем цикле мы принимаем решение, какой цветок будем рассматривать следующим. Внутренний цикл дублирует ароматы и добавляет новый цветок к этим копиям.

function power_set(flowers)

····fragrances ← Set.new

····fragrances.add(Set.new)

····for each flower in flowers

········new_fragrances ← copy(fragrances)

········for each fragrance in new_fragrances

············fragrance.add(flower)

········fragrances ← fragrances + new_fragrances

····return fragrances

Добавление каждого нового цветка приводит к удвоению количества ароматов в множестве fragrances, что говорит об экспоненциальном росте (2^k+1 = 2 × 2^k). Алгоритмы, которые удваивают число операций, если объем входных данных увеличивается на один элемент, — экспоненциальные, их временная сложность — O(2ⁿ).

Генерирование степенных множеств эквивалентно генерированию таблиц истинности (см. раздел «Логика» в главе 1). Если обозначить каждый цветок логической переменной, то любой аромат легко представить в виде значений True/False этих переменных. В таблице истинности каждая строка будет возможной формулой аромата.

Рис. 3.2. Итеративное перечисление всех ароматов с использованием четырех цветков

Мы говорим о рекурсии, когда функция делегирует работу своим клонам. Рекурсивный алгоритм естественным образом приходит на ум, когда нужно решить задачу, сформулированную с точки зрения самой себя. Например, возьмем известную последовательность Фибоначчи. Она начинается с двух единиц, и каждое последующее число является суммой двух предыдущих: 1, 1, 2, 3, 5, 8, 13, 21. Как создать функцию, возвращающую n-е число Фибоначчи (рис. 3.3)?

Рис. 3.3. Рекурсивное вычисление шестого числа Фибоначчи

function fib(n)

····if n ≤ 2

········return 1

····return fib(n — 1) + fib(n — 2)

При использовании рекурсии требуется творческий подход, чтобы понять, каким образом задача может быть поставлена с точки зрения самой себя. Чтобы проверить, является ли слово палиндромом[30], нужно посмотреть, изменится ли оно, если его перевернуть. Это можно сделать, проверив, одинаковы ли первая и последняя буквы слова и не является ли палиндромом заключенная между ними часть слова (рис. 3.4).

Рис. 3.4. Рекурсивная проверка, является ли слово racecar палиндромом

function palindrome(word)

····if word.length ≤ 1

········return True

····if word.first_char ≠ word.last_char

········return False

····w ← word.remove_first_and_last_chars

····return palindrome(w)

Рекурсивные алгоритмы имеют базовые случаи, когда объем входных данных слишком мал, чтобы его можно было продолжать сокращать. Базовые случаи для функции fib — числа 1 и 2; для функции palindrome это слова, состоящие из единственной буквы или не имеющие ни одной буквы.

Рекурсивные алгоритмы обычно проще и короче итеративных. Сравните эту рекурсивную функцию с power_set из предыдущего раздела, которая не использует рекурсию:

function recursive_power_set(items)

····ps ← copy(items)

····for each e in items

·······ps ← ps.remove(e)

·······ps ← ps + recursive_power_set(ps)

·······ps ← ps.add(e)

····return ps

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

Эту проблему можно наглядно увидеть на деревьях рекурсивных вызовов — диаграммах, показывающих, каким образом алгоритм порождает новые вызовы, углубляясь в вычисления. Мы уже видели деревья рекурсивных вызовов для поиска чисел Фибоначчи (см. рис. 3.3) и для проверки слов-перевертышей (см. рис. 3.4).

Если требуется максимальная производительность, то можно избежать этих дополнительных издержек, переписав рекурсивный алгоритм в чисто итеративной форме. Такая возможность есть всегда. Это компромисс: итеративный программный код обычно выполняется быстрее, но вместе с тем он более громоздкий и его труднее понять.

В обычных шахматах — 32 фигуры шести типов и 64 клетки, по которым они ходят. После каких-то четырех первых ходов число возможных дальнейших позиций достигает 288 млрд. Даже самые сильные игроки в мире не в состоянии найти идеальный ход. Они полагаются на интуицию, чтобы найти тот, который окажется достаточно хорошим. Мы можем делать то же самое при помощи алгоритмов. Эвристический метод, или просто эвристика, — это метод, который приводит к решению, не гарантируя, что оно — лучшее или оптимальное. Эвристические алгоритмы помогут, когда методы вроде полного перебора или поиска с возвратом оказываются слишком медленными. Существует много отличных эвристических подходов, но мы сосредоточимся на самом простом: на поиске без возврата.

Очень распространенный эвристический подход к решению задач — использование так называемых «жадных» алгоритмов. Основная их идея состоит в том, чтобы никогда не откатываться к предыдущим вариантам. Это полная противоположность поиску с возвратом. Иными словами, на каждом шаге мы пытаемся сделать самый лучший выбор, а потом уже не подвергаем его сомнению. Давайте испытаем эту стратегию, чтобы по-новому решить задачу о рюкзаке (из раздела «Полный перебор» ).

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

function greedy_knapsack(items, max_weight)

····bag_weight ← 0

····bag_items ← List.new

····for each item in sort_by_value(items)

········if max_weight ≤ bag_weight + item.weight

············bag_weight ← bag_weight + item.weight

············bag_items.append(item)

····return bag_items

Здесь мы не принимаем во внимание то, как наше текущее действие повлияет на будущие варианты выбора. Такой «жадный» подход позволяет отыскать подборку предметов намного быстрее, чем метод полного перебора. Однако он не дает никакой гарантии, что общая стоимость подборки окажется максимальной.

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

Как мы убедились в разделе «Комбинаторика» (см. главу 1), число возможных комбинаций в этой задаче демонстрирует взрывной рост и достигает неприлично больших величин, даже если городов всего несколько. Найти оптимальное решение задачи коммивояжера с тысячами городов — чрезвычайно дорого (а то и вовсе невозможно)[35]. И тем не менее вам нужен маршрут. Вот простой «жадный» алгоритм для этой задачи:

1) посетить ближайший город, где вы еще не были;

2) повторять, пока не объедете все города.

Рис. 3.9. Задача коммивояжера[36]

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

Выбирая эвристический алгоритм вместо классического, вы идете на компромисс. Насколько далеко от идеального решения вы можете отойти, чтобы результат все еще удовлетворял вас? Это зависит от конкретной ситуации.

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

Данная задача может быть решена очень просто.

1. Среди поселков, еще не подключенных к сети, выбрать тот, который находится ближе всех к электрифицированному поселку, и соединить их.

2. Повторять, пока все поселки не будут подключены.

Рис. 3.10. Решение задачи об электрической сети с «жадными» вариантами выбора

На каждом шаге мы выбираем для соединения пару поселков, которая на текущий момент выглядит самой лучшей. Несмотря на то что мы не анализируем, как этот вариант влияет на будущие возможности выбора, присоединение самого близкого поселка без электричества — всегда правильный выбор. Здесь нам повезло: структура задачи идеально подходит для решения «жадным» алгоритмом. В следующем разделе мы увидим структуры задач, для решения которых нужна стратегия великих полководцев.

Когда силы врага раздроблены на небольшие группы, его проще победить. Цезарь и Наполеон управляли Европой, разделяя и завоевывая своих врагов. При помощи той же стратегии вы можете решать задачи — в особенности задачи с оптимальной подструктурой, то есть такие, которые легко делятся на подобные, но меньшие подзадачи. Их можно дробить снова и снова, пока подзадачи не станут простыми. Затем их решения объединяются — так вы получаете решение исходной задачи.

Если у нас есть большой список, который нужно отсортировать, мы можем разделить его пополам: каждая половина становится подзадачей сортировки. Затем решения подзадач (то есть отсортированные половины списка) можно объединить в конечное решение при помощи алгоритма слияния[37]. Но как отсортировать эти две половины? Их тоже можно разбить на подзадачи, отсортировать и объединить.

Новые подзадачи будут также разбиты, отсортированы и объединены. Процесс разделения продолжаем, пока не достигнем базового случая: списка из одного элемента. Такой список уже отсортирован!

Этот изящный рекурсивный алгоритм называется сортировкой слиянием. Как и для последовательности Фибоначчи (см. раздел «Рекурсия»), дерево рекурсивных вызовов помогает увидеть, сколько раз функция merge_sort вызывает саму себя (рис. 3.11).

function merge_sort(list)

····if list.length = 1

········return list

····left ← list.first_half

····right ← list.last_half

····return merge(merge_sort(left),

·················merge_sort(right))

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

Подсчет операций. Допустим, у нас есть большой список размером n. При вызове функция merge_sort выполняет следующие операции:

• разбивает список на половины, что не зависит от размера списка O(1);

• вызывает функцию merge (из раздела «Итерация» мы знаем, что merge имеет сложность O(n);

• делает два рекурсивных вызова merge_sort, которые не учитываются[38].

Поскольку мы оставляем только доминирующий член и не учитываем рекурсивные вызовы, временная сложность функции составляет O(n). Теперь подсчитаем временную сложность каждого шага разбиения.

Шаг разбиения 1. Функция merge_sort вызывается для списка из n элементов. Временная сложность этого шага составляет O(n).

Рис. 3.11. Демонстрация сортировки слиянием. Прямоугольники показывают отдельные вызовы merge_sort, при этом входные данные находятся вверху, а выходные — внизу

Шаг разбиения 2. Функция merge_sort вызывается дважды, каждый раз для элементов. Мы получаем .

Шаг разбиения 3. Функция merge_sort вызывается четыре раза, каждый раз для элементов: .

.

.

.

.

Шаг разбиения x. Функция merge_sort вызывается 2^x раз, каждый для списка из элементов: .

Все шаги разбиения имеют одинаковую сложность O(n). Временная сложность сортировки слиянием, следовательно, составляет x × O(n), где x — это количество шагов разбиения, необходимых для полного выполнения алгоритма[39].

Подсчет шагов. Как вычислить x? Мы знаем, что рекурсивные функции заканчивают вызывать себя, как только достигают своего базового случая. Наш базовый случай — это одноэлементный список. Мы также увидели, что шаг разбиения x работает на списках из элементов. Потому:

Если вы не знакомы с функцией log₂, то не робейте! x = log₂ n — это просто еще один способ написать 2^x = n. Программисты любят логарифмический рост.

Посмотрите, как медленно растет количество требуемых шагов разбиения[40] с увеличением общего числа сортируемых элементов (табл. 3.1).

Таблица 3.1. Количество шагов разбиения, требуемых для списков разных размеров

Размер списка (n)	log2 n	Требуемое количество шагов разбиения
10	3,32	4
100	6,64	7
1024	10,00	10
1 000 000	19,93	20
1 000 000 000	29,89	30

Временная сложность сортировки слиянием, следовательно, составляет log₂ n × O(n) = O(n log n). Это колоссальное улучшение по сравнению с сортировкой выбором O(n²). Помните разницу в производительности между линейно-логарифмическими и квадратичными алгоритмами, которые мы видели в предыдущей главе на рис. 2.4? Даже если предположить, что алгоритм O(n²) будет обрабатываться быстрым компьютером, в конечном счете он все равно окажется медленнее, чем алгоритм O(n log n) на слабой машине (табл. 3.2).

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

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

Таблица 3.2. В случае больших объемов входных данных алгоритмы O(n log n) выполняются намного быстрее алгоритмов O(n²), запущенных на компьютерах, в 1000 раз более производительных

Объем данных	Квадратичный	Логлинейный
196 (число стран в мире)	38 мс	2 с
44 000 (число аэропортов в мире)	32 минуты	12 минут
171 000 (число слов в словаре английского языка)	8 часов	51 минута
1 млн (число жителей Гавайев)	12 дней	6 часов
19 млн (число жителей штата Флорида)	11 лет	6 дней
130 млн (число книг, опубликованных за все время)	500 лет	41 день
4,7 млрд (число страниц в Интернете)	700 000 лет	5 лет

Для задачи о самой лучшей сделке (см. раздел «Полный перебор» ) подход «Разделяй и властвуй» оказывается лучше, чем решение «в лоб». Разделение списка цен пополам приводит к двум подзадачам: нужно найти лучшую сделку в первой половине и лучшую сделку во второй. После этого мы получим один из трех вариантов:

1) лучшая сделка с покупкой и продажей в первой половине;

2) лучшая сделка с покупкой и продажей во второй половине;

3) лучшая сделка с покупкой в первой половине и продажей во второй.

Рис. 3.12. Демонстрация выполнения функции trade. Прямоугольники показывают отдельные вызовы trade с входными и выходными данными

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

function trade(prices)

····if prices.length = 1

········return 0

····former ← prices.first_half

····latter ← prices.last_half

····case3 ← max(latter) — min(former)

····return max(trade(former), trade(latter), case3)

Функция trade выполняет тривиальное сравнение, разбивает список пополам и находит максимум и минимум в его половинах. Поиск максимума или минимума в списке из n элементов требует просмотра всех n элементов, таким образом, отдельный вызов trade стоит O(n).

Вы наверняка заметите, что дерево рекурсивных вызовов функции trade (рис. 3.12) очень похоже на такое же для сортировки слиянием (рис. 3.11). Оно тоже имеет log₂ n шагов разбиения, каждый стоимостью O(n). Следовательно, функция trade тоже имеет сложность O(n log n) — это огромный шаг вперед по сравнению со сложностью O(n²) предыдущего подхода, основанного на полном переборе.

Задачу о рюкзаке (см. раздел «Полный перебор» ) тоже можно разделить и тем самым решить. Если вы не забыли, у нас n предметов на выбор. Мы обозначим свойство каждого из них следующим образом:

• w_i — это вес i-го предмета;

• v_i — это стоимость i-го предмета.

Индекс i предмета может быть любым числом от 1 до n. Максимальный доход для вместимости c рюкзака с уже выбранными n предметами составляет K(n, c). Если рассматривается дополнительный предмет i = n + 1, то он либо повысит, либо не повысит максимально возможный доход, который становится равным большему из двух значений.

1. K(n, c) — если дополнительный предмет не выбран.

2. K(n, c − w_n+1) + v_n+1 — если дополнительный предмет выбран.

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

K(n, c) = max (K(n − 1, c),

K(n − 1, c − w_n) + v_n).

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

Рис. 3.13. Решение задачи о рюкзаке с 5 предметами и вместимостью рюкзака 4. Предметы под номерами 5 и 4 весят две единицы, остальные — одну единицу

Во время решения задачи иногда приходится выполнять одни и те же вычисления многократно[41]. Динамическое программирование позволяет идентифицировать повторяющиеся подзадачи, чтобы можно было выполнить каждую всего один раз. Общепринятый метод, предназначенный для этого, основан на запоминании и имеет «говорящее» название.

Помните алгоритм вычисления чисел Фибоначчи? Его дерево рекурсивных вызовов (см. рис. 3.3) показывает, что fib(3) вычисляется многократно. Мы можем это исправить, сохраняя результаты по мере их вычисления и делая новые вызовы fib только для тех вычислений, результатов которых еще нет в памяти (рис. 3.14). Этот прием

Рис. 3.14. Дерево рекурсивных вызовов для dfib. Зеленые прямоугольники обозначают вызовы, не выполняемые повторно

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

Очевидно, что в дереве рекурсивных вызовов для задачи о рюкзаке (см. рис. 3.13) имеются многократно повторяемые вызовы. Применение того же самого приема, который мы использовали для функции Фибоначчи, позволяет избежать этих повторных вызовов и в итоге уменьшить объем вычислений (рис. 3.15).

Рис. 3.15. Рекурсивное решение задачи о рюкзаке при помощи мемоизации

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

Дерево рекурсии для функции trade (см. рис. 3.12) не имеет повторных вызовов, и все равно делает повторные вычисления. Он просматривает вход, чтобы найти максимальное и минимальное значения. Затем входные данные разбиваются на две части, и рекурсивные вызовы анализируют их снова, чтобы найти максимум и минимум в каждой половине[42]. Нам нужен другой принцип, для того чтобы избежать этих повторных проходов.

До сих пор мы использовали нисходящий подход, где объем входных данных постепенно уменьшается, пока не будут достигнуты базовые случаи. Но мы также можем пойти снизу вверх: сначала вычислить базовые случаи, а затем раз за разом собирать их, пока не получим общий результат. Давайте решим задачу о лучшей сделке (см. раздел «Полный перебор» ) таким способом.

Пусть P(n) — это цена в n-й день, а B(n) — лучший день для покупки при продаже в n-й день. Если мы продаем в первый день, то купить у нас получится только тогда же, других вариантов нет, поэтому B(1) = 1. Но если мы продаем во второй день, B(2) может равняться 1 либо 2:

• P(2) < P(1)! B(2) = 2 (купить и продать в день 2);

• P(2) ≥ P(1)! B(2) = 1 (купить в день 1, продать в день 2).

День с самой низкой ценой перед днем 3, но не в день 3 — это B(2). Потому для B(3):

• P(3) < цена в день B(2) —> B(3) = 3.

• P(3) ≥ цена в день B(2) —> B(3) = B(2).

Обратите внимание, что день с самой низкой ценой перед днем 4 будет B(3). Фактически для каждого n день с самой низкой ценой перед днем n — B(n — 1). Мы можем это использовать, чтобы выразить B(n) через B(n — 1):

Когда у нас есть все пары [n, B(n)] для для каждого дня n, решением является пара, которая дает самую высокую прибыль. Следующий алгоритм решает задачу, вычисляя все значения B снизу вверх:

function trade_dp(P)

····B[1] ← 1

····sell_day ← 1

····best_profit ← 0

Многие задачи связаны с минимизацией или максимизацией целевого значения: найти кратчайший путь, получить наибольшую прибыль и т. д. Такие задачи называются задачами оптимизации. Когда решением является последовательность вариантов, мы часто используем стратегию ветвей и границ. Ее цель состоит в том, чтобы выиграть время за счет быстрого обнаружения и отбрасывания плохих вариантов. Чтобы понять, каким образом они ищутся, мы сначала должны разобраться в понятиях «верхняя граница» и «нижняя граница».

Границы обозначают диапазон значения. Верхняя граница устанавливает предел того, каким высоким оно может быть. Нижняя граница — это наименьшее значение, на которое стоит надеяться; она гарантирует, что любое значение либо равно ей, либо ее превышает.

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

В задаче о жадном грабителе и рюкзаке (см. раздел «Эвристические алгоритмы» ) прибыль, полученная посредством greedy_knapsack, является нижней границей оптимальной прибыли (она может быть или не быть близкой к оптимальной прибыли). Теперь представим версию задачи о рюкзаке, в которой вместо предметов у нас сыпучие материалы, и мы можем насыпать их в рюкзак, сколько поместится. Эта версия задачи решается «жадным» способом: просто продолжайте насыпать материалы с самым высоким соотношением стоимости и веса:

function powdered_knapsack(items, max_weight)

····bag_weight ← 0

····bag_items ← List.new

····items ← sort_by_value_weight_ratio(items)

····for each i in items

········weight ← min(max_weight — bag_weight,

·····················i.weight)

········bag_weight ← bag_weight + weight

········value ← weight * i.value_weight_ratio

········bagged_value ← bagged_value + value

········bag_items.append(item, weight)

····return bag_items, bag_value

Добавление ограничения неделимости предметов только уменьшит максимально возможную прибыль, потому что нам придется менять последнюю уложенную в рюкзак вещь на что-то подешевле. Это означает, что powdered_knapsack дает верхнюю границу оптимальной прибыли с неделимыми предметами[43].

Мы уже убедились, что поиск оптимальной прибыли в задаче о рюкзаке требует дорогих вычислений O(n²). Однако мы можем быстро получить верхние и нижние границы оптимальной прибыли при помощи функций powdered_knapsack и greedy_knapsack. Давайте попробуем это сделать на примере задачи о рюкзаке (табл. 3.3).

Таблица 3.3. Верхняя и нижняя границы в задаче о рюкзаке

Предмет	Стоимость	Вес	Соотношение стоимости и веса	Макс. вместимость
A	20	5	4,00
B	19	4	4,75
C	16	2	8,00	10
D	14	5	2,80
E	13	3	4,33
F	9	2	4,50

Рисунок справа иллюстрирует ситуацию перед началом заполнения рюкзака. В первом поле находятся неупакованные предметы, которые нам предстоит рассмотреть. Второе поле представляет свободное место в рюкзаке и предметы, которые уже уложены. Выполнение функции greedy_knapsack дает прибыль 39, а powdered_knapsack — 52,66. Это означает, что оптимальная прибыль находится где-то посередине. Как мы знаем из раздела «Разделяй и властвуй», эта задача с n предметами делится на две подзадачи с n — 1 предметами. Первая подзадача подразумевает, что предмет A был взят, вторая — что он не был взят:

Мы вычисляем верхнюю и нижнюю границы для этих двух подзадач. Каждая имеет нижнюю границу, равную 48: теперь мы знаем, что оптимальное решение находится между 48 и 52. Давайте рассмотрим подзадачу справа, поскольку у нее более интересные границы:

Крайняя левая подзадача имеет самую многообещающую верхнюю границу. Давайте продолжим наш анализ и выполним разбиение этой подзадачи:

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

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

Вот общие принципы работы метода ветвей и границ:

1) разделить задачу на подзадачи;

2) найти верхние и нижние границы каждой подзадачи;

3) сравнить границы подзадач всех ветвей;

4) выбрать самую многообещающую задачу и вернуться к шагу 1.

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

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

В программном обеспечении процедурные абстракции скрывают за вызовом процедур сложности реализации процесса. В алгоритме trade (см. раздел «Разделяй и властвуй» главы 3) процедуры min и max скрывают механику поиска минимальных и максимальных чисел и тем самым упрощают алгоритм. При помощи абстракций можно создавать модули[44], которые позволяют выполнять сложные операции вызовом одной единственной процедуры, вроде этой:

html ← fetch_source("https://code.energy")

Всего одной строкой кода мы получили страницу сайта, несмотря на то что внутренние операции для этой задачи чрезвычайно сложны[45].

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

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

Например, переменная, содержащая последовательность символов, которые можно преобразовать в верхний или нижний регистр, и допускающая добавление новых символов, имеет тип String (строка). Строки представляют текстовые данные. Переменная, которую можно инвертировать и которая допускает операции XOR, OR и AND, имеет тип Boolean (логический). Такие булевы переменные принимают одно из двух значений: True или False. Переменные, которые можно складывать, делить и вычитать, имеют тип Number (численный).

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

Абстрактный тип данных (АТД) — это подробное описание группы операций, применимых к конкретному типу данных. Они определяют интерфейс для работы с переменными, содержащими данные конкретного типа, и скрывают все подробности хранения данных в памяти и управления ими.

Когда нашим алгоритмам приходится оперировать данными, мы не включаем в них команды чтения и записи в память компьютера. Мы используем внешние модули обработки данных, которые предоставляют процедуры, определенные в АТД.

Например, для работы с переменными, хранящими списки, нам нужны: процедуры для создания и удаления списков; процедуры для доступа к n-му элементу списка и его удаления; процедура для добавления нового элемента в список. Определения этих процедур (их имена и что они делают) содержатся в АТД «Список». Мы можем работать со списками, руководствуясь исключительно этими процедурами. Так что мы никогда не управляем памятью компьютера непосредственно.

Простота. АТД делает наш код доступнее для понимания и изменения. Опустив детали в процедурах обработки данных, вы сможете сосредоточиться на самом главном — на алгоритмическом процессе решения задачи.

Гибкость. Существуют разные способы структурирования данных в памяти и, как следствие, разные модули обработки одного и того же типа данных. Мы должны выбрать тот, что лучше соответствует текущей ситуации. Модули, которые реализуют тот же АТД, предлагают одинаковые процедуры. Это означает, что мы можем изменить способ хранения данных и выполнения операций, просто применив другой модуль обработки данных. Это как с автомобилями: все автомобили на электрической и бензиновой тяге имеют одинаковый интерфейс. Если вы умеете управлять одним автомобилем, вы сумеете управлять и любыми другими.

Повторное использование. Мы задействуем одни и те же модули в проектах, где обрабатываются данные одинакового типа. Например, процедуры power_set и recursive_power_set из предыдущей главы работают с переменными, представляющими множества, Set. Это означает, что мы можем использовать один и тот же модуль Set в обоих алгоритмах.

Организация. Нам, как правило, приходится оперировать несколькими типами данных: числами, текстом, географическими координатами, изображениями и пр. Чтобы лучше организовать нашу программу, мы создаем отдельные модули, каждый из которых содержит код, работающий исключительно с конкретным типом данных. Это называется разделением функциональности: части кода, которые имеют дело с одним и тем же логическим аспектом, должны быть сгруппированы в собственном, отдельном модуле. Когда они перемешаны с чем-то посторонним, это называется запутанным кодом.

Удобство. Мы берем модуль обработки данных, написанный кем-то другим, разбираемся с использованием определенных в его АТД процедур, и сразу после этого можем их использовать, чтобы оперировать данными нового типа. Нам не нужно понимать, как функционирует этот модуль.

Устранение программных ошибок. Если вы используете модуль обработки данных, то в вашем программном коде не будет ошибок обработки данных. Если же вы найдете ошибку в модуле обработки данных, то, устранив ее один раз, вы немедленно исправите все части своего кода, которые она затрагивала.

Чтобы решить вычислительную задачу, крайне важно знать тип обрабатываемых данных и операции, которые вам предстоит выполнять с этими данными. Не менее важно принять решение, какой АТД вы будете использовать.

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

Примитивные типы данных — это типы данных со встроенной поддержкой в языке программирования, который вы используете. Для работы с ними на нужны внешние модули. Сюда относятся целые числа, числа с плавающей точкой[46] и универсальные операции с ними (сложение, вычитание, деление). Большинство языков также по умолчанию поддерживают хранение в своих переменных текста, логических значений и других простых данных.

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

• push(e) — добавить элемент e на вершину стека;

• pop() — получить и удалить элемент с вершины стека.

Более совершенные разновидности стеков могут поддерживать дополнительные операции: проверку наличия в стеке элементов или получение их текущего количества.

Такая обработка данных известна под названием LIFO (Last-In, First-Out, «последним пришел, первым вышел»); мы можем удалить только верхний элемент, который был добавлен последним. Стек — это важный тип данных, он встречается во многих алгоритмах. Для реализации функции «Отменить ввод» в текстовом редакторе каждая вносимая вами правка помещается в стек. Если вы хотите ее отменить, то текстовый редактор выталкивает правку из стека и возвращается к предыдущему состоянию.

Чтобы реализовать поиск с возвратом (см. соответствующий раздел главы 3) без рекурсии, вы должны запоминать в стеке последовательность вариантов, которые привели вас к текущей точке. Обследуя новый узел, мы помещаем ссылку на него в стек. Чтобы вернуться на шаг назад, мы просто выталкиваем (pop()) последний элемент из стека, заодно получая ссылку на предыдущее состояние.

Очередь (queue) — это полная противоположность стека. Она тоже позволяет сохранять и извлекать данные, но элементы всегда берутся из начала очереди — тот, который находился в очереди дольше всего. Звучит пугающе? В действительности это то же самое, что и реальная очередь из людей, стоящих у раздачи в столовой! Вот основные операции с очередями:

• enqueue(e) — добавить элемент e в конец очереди;

• dequeue() — удалить элемент из начала очереди.

Очередь работает по принципу организации данных FIFO (First-In, FirstOut, «первый пришел, первый вышел»), потому что первый помещенный в очередь элемент всегда покидает ее первым.

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

Очередь с приоритетом (priority queue) аналогична обычной очереди с той лишь разницей, что помещенным в нее элементам присваивается приоритет. Люди, ожидающие медицинской помощи в больнице, — вот реальный пример очереди с приоритетом. Экстренные случаи получают высший приоритет и переходят непосредственно в начало очереди, тогда как незначительные добавляются в ее конец. Основные операции, реализуемые очередью с приоритетом, таковы:

• enqueue(e, p) — добавить элемент e в очередь согласно уровню приоритетности p;

• dequeue() — вернуть элемент, расположенный в начале очереди, и удалить его.

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

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

При работе с группами элементов иногда требуется гибкость. Например, может понадобиться переупорядочить элементы или извлекать, вставлять и удалять их в произвольном порядке. В этих случаях удобно использовать список (list). Чаще всего АТД «Список» поддерживает следующие операции:

• insert(n, e) — вставить элемент e в позицию n;

• remove(n) — удалить элемент, находящийся в позиции n;

• get(n) — получить элемент, находящийся в позиции n;

• sort() — отсортировать элементы;

• slice(start, end) — вернуть фрагмент списка, начинающийся с позиции start и заканчивающийся в позиции end;

• reverse() — изменить порядок следования элементов на обратный.

Список — один из наиболее используемых АТД. Например, если вам нужно хранить ссылки на часто запрашиваемые файлы в системе, то список — идеальное решение: вы можете сортировать ссылки для отображения и удалять их, если к соответствующим файлам стали обращаться реже.

Стеку и очереди следует отдавать предпочтение, когда гибкость, предоставляемая списком, не нужна. Использование более простого АТД гарантирует, что данные будут обрабатываться строгим и предсказуемым образом (по принципу FIFO или LIFO). Это также делает код яснее: зная, что переменная представляет собой стек, легче понять характер потоков данных на входе и выходе.

Сортированный список (sorted list) бывает полезен, когда нужна постоянная упорядоченность элементов. В этих случаях вместо поиска правильной позиции перед каждой вставкой в список (и периодической сортировки его вручную) мы используем сортированный список. Что бы в него ни помещали, элементы всегда будут стоять по порядку. Ни одна из операций этого АТД не позволяет переупорядочить его элементы. Сортированный список поддерживает меньше операций, чем обычный:

• insert(e) — вставить элемент e в автоматически определяемую позицию в списке;

• delete(n) — удалить элемент, находящийся в позиции n;

• get(n): получить элемент, находящийся в позиции n.

Словарь (map) используется для хранения соответствий между двумя объектами: ключом key и значением value. Вы можете осуществить поиск по ключу и получить связанное с ним значение. Словарь хорошо подходит, например, для хранения идентификационных номеров пользователей в качестве ключей и полных имен в качестве значений. Такой словарь по заданному идентификационному номеру вернет связанное с ним имя. Существуют следующие операции для словарей:

• set(key, value) — добавить элемент с заданным ключом и значением;

• delete(key) — удалить ключ key и связанное с ним значение;

• get(key) — получить значение, связанное с ключом key.

Множество (set) представляет неупорядоченные группы уникальных элементов, подобные математическим множествам, которые описаны в приложении III. Этот АТД используется, когда неважен порядок следования элементов либо когда нужно обеспечить уникальность элементов в группе. Стандартный набор операций для множества включает в себя:

• add(e) — добавить элемент в множество или вернуть ошибку, если элемент уже присутствует в множестве;

• list() — перечислить все элементы, присутствующие в множестве;

• delete(e) — удалить элемент из множества.

АТД для программиста — как приборная панель для водителя. Но давайте все-таки попробуем понять, как проложены провода за этой приборной панелью.

Абстрактный тип данных лишь описывает, какие действия можно совершать с переменными конкретного типа. Он определяет список операций, но не объясняет, как они выполняются. Со структурами данных — обратная ситуация: они описывают, как данные организованы и как к ним получить доступ в памяти компьютера. Структуры данных обеспечивают реализацию АТД в модулях обработки данных.

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

Массив (array) — это самый простой способ хранения набора элементов в памяти компьютера. Он заключается в выделении единого пространства в памяти и последовательной записи в него ваших элементов. Конец последовательности отмечается специальным маркером NULL (рис. 4.1).

Рис. 4.1. Массив в памяти компьютера

Каждый объект в массиве занимает такой же объем памяти, что и любой другой. Представим массив, начинающийся с адреса ячейки памяти s, где каждый элемент занимает b байт. Чтобы получить n-й элемент, нужно извлечь b байт, начиная с позиции в памяти s + (b × n).

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

Может оказаться практически нецелесообразным выделять большие непрерывные блоки памяти. Если вам нужно наращивать массив, то в памяти может не оказаться смежного с ним достаточного большого пространства. Удаление элемента из середины массива сопряжено с определенными проблемами: вам придется сдвинуть все последующие элементы на одну позицию к началу либо отметить пространство памяти удаленного элемента как свободное. Ни один из этих вариантов не желателен. Аналогично вставка элемента внутрь массива вынудит вас сдвинуть все последующие элементы на одну позицию к концу.

Cвязный список (linked list) позволяет хранить элементы в цепи ячеек, которые не обязательно должны находиться в последовательных адресах памяти. Память для ячеек выделяется по мере необходимости. Каждая ячейка имеет указатель, сообщающей об адресе следующей в цепи. Ячейка с пустым указателем (NULL) отмечает конец цепи (рис. 4.2).

Связные списки используются для реализации стеков, списков и очередей. При наращивании связного списка не возникает никаких проблем: любая ячейка может храниться в любой части памяти. Таким образом, размер списка ограничен только объемом имеющейся свободной памяти. Также не составит труда вставить элементы в середину списка или удалить их — достаточно просто изменить указатели ячеек (рис. 4.3).

Рис. 4.2. Связный список в памяти компьютера

Рис. 4.3. Добавление элемента между B и C. Удаление C

Связный список тоже имеет свои недостатки: мы не можем сразу получить n-й элемент. Сначала придется прочитать первую ячейку, извлечь из нее адрес второй ячейки, затем прочитать вторую ячейку, извлечь из нее указатель на следующую ячейку и т. д., пока мы не доберемся до n-й ячейки.

Кроме того, когда известен адрес всего одной ячейки, не так просто ее удалить или переместиться по списку назад. Не имея другой информации, нельзя узнать адрес предыдущей ячейки в цепи.

Двусвязный список (double linked list) — это связный список, где ячейки имеют два указателя: один на предыдущую ячейку, другой — на следующую (рис. 4.4).

Рис. 4.4. Двусвязный список в памяти компьютера

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

И тем не менее мы по-прежнему не имеем прямого доступа к n-му элементу. Кроме того, для поддержки двух указателей в каждой ячейке требуется более сложный код и больше памяти.

Языки программирования с богатым набором средств обычно включают встроенные реализации списка, очереди, стека и других АТД. Эти реализации часто основаны на некоторой стандартной структуре данных. Некоторые из них могут даже автоматически переключаться с одной структуры данных на другую во время выполнения программ, в зависимости от способа доступа к данным.

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

• нужно, чтобы операции вставки и удаления выполнялись чрезвычайно быстро;

• не требуется произвольный доступ к данным;

• приходится вставлять или удалять элементы между других элементов;

• заранее не известно количество элементов (оно будет расти или уменьшится по ходу выполнения программы).

Массивы предпочтительнее связных списков, когда:

• нужен произвольный доступ к данным;

• нужен очень быстрый доступ к элементам;

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

Как и связный список, дерево (tree) использует элементы, которым для хранения объектов не нужно располагаться в физической памяти непрерывно. Ячейки здесь тоже имеют указатели на другие ячейки, однако, в отличие от связных списков, они располагаются не линейно, а в виде ветвящейся структуры. Деревья особенно удобны для иерархических данных, таких как каталоги с файлами или система субординации (рис. 4.5).

В терминологии деревьев ячейка называется узлом, а указатель из одной ячейки на другую — ребром. Самая первая ячейка — это корневой узел, он единственный не имеет родителя. Все остальные узлы в деревьях должны иметь строго одного родителя[47].

Два узла с общим родителем называются братскими. Родитель узла, прародитель, прапрародитель (и т. д. вплоть до корневого узла) — это предки. Аналогично дочерние узлы, внуки, правнуки (и т. д. вплоть до нижней части дерева) называются потомками.

Узлы, не имеющие дочерних узлов, — это листья (по аналогии с листьями настоящего дерева ). Путь между двумя узлами определяется множеством узлов и ребер.

Уровень узла — это длина пути от него до корневого узла, высота дерева — уровень самого глубокого узла в дереве (рис. 4.6). И, наконец, множество деревьев называется лесом.

Рис. 4.5. Дерево происхождения индоевропейских языков

Рис. 4.6. Листья этого дерева представляют современные языки

Двоичное дерево поиска (binary search tree) — это особый тип дерева, поиск в котором выполняется особенно эффективно. Узлы в двоичном дереве поиска могут иметь не более двух дочерних узлов. Кроме того, узлы располагаются согласно их значению/ключу. Дочерние узлы слева от родителя должны быть меньше него, а справа — больше (рис. 4.7).

Рис. 4.7. Пример двоичного дерева поиска

Если дерево соблюдает это свойство, в нем легко отыскать узел с заданным ключом/значением:

function find_node(binary_tree, value)

node ← binary_tree.root_node

····while node

········if node.value = value

············return node

········if value > node.value

············node ← node.right

········else

············node ← node.left

····return "NOT FOUND"

Чтобы вставить элемент, находим последний узел, следуя правилам построения дерева поиска, и подключаем к нему новый узел справа или слева:

function insert_node(binary_tree, new_node)

····node ← binary_tree.root_node

····while node

········last_node ← node

········if new_node.value > node.value

············node ← node.right

········else

············node ← node.left

····if new_node.value > last_node.value

········last_node.right ← new_node

····else

········last_node.left ← new_node

Балансировка дерева. Если вставить в двоичное дерево поиска слишком много узлов, в итоге получится очень высокое дерево, где большинство узлов имеют всего один дочерний узел. Например, если последовательно вставлять узлы с ключами/значениями, которые всегда больше предыдущих, в итоге получится нечто, похожее на связный список. Однако мы можем перестроить узлы в дереве так, что его высота уменьшится. Эта процедура вызывается балансировкой дерева. Идеально сбалансированное дерево имеет минимальную высоту (рис. 4.8).

Рис. 4.8. Одно и то же двоичное дерево поиска с разной балансировкой: сбалансированное плохо, средне и идеально

Большинство операций с деревом требует обхода узлов по ссылкам, пока не будет найден конкретный узел. Чем больше высота дерева, тем длиннее средний путь между узлами и тем чаще приходится обращаться к памяти. Поэтому важно уменьшать высоту деревьев. Идеально сбалансированное двоичное дерево поиска можно создать из сортированного списка узлов следующим образом:

function build_balanced(nodes)

····if nodes is empty

········return NULL

····middle ← nodes.length/2

····left ← nodes.slice(0, middle — 1)

····right ← nodes.slice(middle + 1, nodes.length)

····balanced ← BinaryTree.new(root=nodes[middle])

····balanced.left ← build_balanced(left)

····balanced.right ← build_balanced(right)

····return balanced

Рассмотрим двоичное дерево поиска с n узлами и с максимально возможной высотой n. В этом случае оно похоже на связный список. Минимальная высота идеально сбалансированного дерева равняется log₂ n. Сложность поиска элемента в дереве пропорциональна его высоте. В худшем случае, чтобы найти элемент, придется опускаться до самого нижнего уровня листьев. Поиск в сбалансированном дереве с n элементами, следовательно, имеет O(log n). Вот почему эта структура данных часто выбирается для реализации множеств (где предполагается проверка присутствия элементов) и словарей (где нужно искать пары «ключ — значение»).

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

Для эффективной обработки двоичных деревьев, которые изменяются часто, были придуманы сбалансированные двоичные деревья (self-balancing binary tree)[48]. Их процедуры вставки или удаления элементов гарантируют, что дерево остается сбалансированным. Красно-черное дерево (red-black tree) — это хорошо известный пример сбалансированного дерева, которое окрашивает узлы красным либо черным цветом в зависимости от стратегии балансировки[49]. Красно-черные деревья часто используются для реализации словарей: словарь может подвергаться интенсивной правке, но конкретные ключи в нем по-прежнему будут находиться быстро вследствие балансировки.

AVL-дерево (AVL tree) — это еще один подвид сбалансированных деревьев. Оно требует немного большего времени для вставки и удаления элементов, чем красно-черное дерево, но, как правило, обладает лучшим балансом. Это означает, что оно позволяет получать элементы быстрее, чем красно-черное дерево. AVL-деревья часто используются для оптимизации производительности в сценариях, для которых характерна высокая интенсивность чтения.

Данные часто хранятся на магнитных дисках, которые считывают их большими блоками. В этих случаях используется обобщенное двоичное B-дерево (B-tree). В таких деревьях узлы могут хранить более одного элемента и иметь более двух дочерних узлов, что позволяет им эффективно оперировать данными в больших блоках. Как мы вскоре увидим, B-деревья обычно используются в системах управления базами данных.

Двоичная куча (binary heap) — особый тип двоичного дерева поиска, в котором можно мгновенно найти самый маленький (или самый большой) элемент. Эта структура данных особенно полезна для реализации очередей с приоритетом. Операция получения минимального (или максимального) элемента имеет сложность O(1), потому что он всегда является корневым узлом дерева. Поиск и вставка узлов здесь по-прежнему стоят O(log n). Кучи подчиняются тем же правилам размещения узлов, что и двоичные деревья поиска, но есть одно ограничение: родительский узел должен быть больше (либо меньше) обоих своих дочерних узлов (рис. 4.9).

Рис. 4.9. Узлы, организованные как двоичная куча max-heap (вверху) и двоичная куча min-heap (внизу)[50]

Обращайтесь к двоичной куче всегда, когда планируете часто иметь дело с максимальным (либо минимальным) элементом множества.

Граф (graph) аналогичен дереву. Разница состоит в том, что у него нет ни дочерних, ни родительских узлов (вершин) и, следовательно, нет корневого узла. Данные свободно организованы в виде узлов (вершин) и дуг (ребер) так, что любой узел может иметь произвольное число входящих и исходящих ребер.

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

Хеш-таблица (hash table) — это структура данных, которая позволяет находить элементы за O(1). Поиск занимает постоянное время вне зависимости от того, ищете вы среди 10 млн элементов или всего среди 10.

Так же, как массив, хеш для хранения данных требует предварительного выделения большого блока последовательной памяти. Но, в отличие от массива, его элементы хранятся не в упорядоченной последовательности. Позиция, занимаемая элементом, «волшебным образом» задается хеш-функцией. Это специальная функция, которая на входе получает данные, предназначенные для хранения, и возвращает число, кажущееся случайным. Оно интерпретируется как позиция в памяти, куда будет помещен элемент.

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

Однако с хеш-таблицами возникают проблемы: иногда хеш-функция возвращает одинаковую позицию для разных входных данных. Такая ситуация называется хеш-коллизией. Когда она происходит, все такие элементы должны быть сохранены в одной позиции в памяти (эта проблема решается, например, посредством связного списка, который начинается с заданного адреса). Хеш-коллизии влекут за собой издержки процессорного времени и памяти, поэтому их желательно избегать.

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

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

С другой стороны, для корректной работы хеш-таблицы требуют выделения очень большого блока непрерывной памяти.

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

Как найти узел в графе? Если структура графа не предоставляет никакой помощи в навигации, вам придется посетить каждую вершину, пока не обнаружится нужная. Есть два способа сделать это: выполнить обход графа в глубину и в ширину (рис. 5.2).

Рис. 5.2. Обход графа в глубину против обхода в ширину

Выполняя поиск в графе в глубину (DFS, depth first search), мы продвигаемся вдоль ребер, уходя все глубже и глубже в граф. Достигнув вершины без ребер, ведущих к каким-либо новым вершинам, мы возвращаемся к предыдущей и продолжаем процесс. Мы используем стек, чтобы запомнить путь обхода графа, помещая туда вершину на время ее исследования и удаляя ее, когда нужно вернуться. Стратегия поиска с возвратом (см. соответствующий раздел главы 3) выполняет обход решений точно так же.

function DFS(start_node, key)

····next_nodes ← Stack.new()

····seen_nodes ← Set.new()

····next_nodes.push(start_node)

····seen_nodes.add(start_node)

····while not next_nodes.empty

········node ← next_nodes.pop()

········if node.key = key

············return node

········for n in node.connected_nodes

············if not n in seen_nodes

················next_nodes.push(n)

················seen_nodes.add(n)

····return NULL

Если обход графа вглубь не кажется приемлемым решением, можно попробовать обход в ширину (BFS, breadth first search). В этом случае обход графа выполняется по уровням: сначала соседей начальной вершины, затем соседей его соседей и т. д. Вершины для посещения запоминаются в очереди. Исследуя вершину, мы ставим в очередь ее дочерние вершины, затем определяем следующую исследуемую вершину, извлекая ее из очереди.

function BFS(start_node, key)

····next_nodes ← Queue.new()

····seen_nodes ← Set.new()

····next_nodes.enqueue(start_node)

····seen_nodes.add(start_node)

····while not next_nodes.empty

········node ← next_nodes.dequeue()

········if node.key = key

············return node

········for n in node.connected_nodes

············if not n in seen_nodes

················next_nodes.enqueue(n)

················seen_nodes.add(n)

····return NULL

Обратите внимание, что алгоритмы DFS и BFS отличаются только способом хранения следующих исследуемых вершин: в одном случае это очередь, в другом — стек.

Итак, какой подход нам следует использовать? Алгоритм DFS более прост в реализации и использует меньше памяти: достаточно хра-

Рис. 5.3. Поиск в графе в глубину[53]

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

Когда есть основания предполагать, что искомая вершина не находится многими уровнями ниже начальной, обычно имеет смысл заплатить более высокую стоимость BFS, потому что так вы, скорее всего, закончите поиск быстрее. Если нужно исследовать абсолютно все вершины графа, лучше придерживаться алгоритма DFS из-за его простой реализации и меньшего объема потребляемой памяти.

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

Задачи раскраски графов возникают, когда есть фиксированное число «красок» (либо любой другой набор меток) и вы должны назначить «цвет» каждой вершине в графе. Вершины, которые соединены ребром, не могут иметь одинаковый «цвет». В качестве примера давайте рассмотрим следующую задачу.

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

Как назначить частоты приемлемым способом? Можно ли найти решение, которое использует всего три цвета? Или два? Определение минимально возможного количества цветов на самом деле является NP-полной задачей — для этого подходят только экспоненциальные алгоритмы.

Мы не покажем алгоритм для решения данной задачи. Используйте то, чему вы научились к настоящему моменту, и попробуйте решить задачу самостоятельно. Это можно сделать на сайте UVA[54] с онлайн-экспертом, который протестирует предложенное вами решение, выполнит ваш программный код и сообщит, работоспособен ли он. Если с кодом окажется все в порядке, эксперт также оценит время выполнения вашего кода в сравнении с тем, что написали другие люди. Дерзайте! Продумайте алгоритмы и стратегии решения данной задачи и испытайте их. Чтение книги может лишь подвести вас к решению. Взаимодействие с онлайновым экспертом даст вам практический опыт, необходимый для того, чтобы стать отличным программистом.

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

Для поиска кратчайшего пути вполне можно использовать стратегии BFS и DFS, но это плохая идея. Одним из хорошо известных и очень эффективных способов поиска кратчайшего пути является алгоритм Дейкстры. В отличие от BFS, для запоминания просматриваемых вершин алгоритм Дейкстры использует очередь с приоритетом. Когда исследуются новые вершины, их связи добавляются в эту очередь. Приоритетом вершины является вес ребер, которые приводят ее в стартовую вершину. Благодаря этому следующая исследуемая вершина всегда оказывается самой близкой к месту, откуда мы начали.

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

А что, если граф, в котором вы ищете, огромен? Для ускорения можно использовать двунаправленный поиск. Два процесса поиска выполняются одновременно: один начинает со стартовой вершины, другой — с конечной. Когда оказывается, что вершина, обнаруженная в одном пространстве поиска, также присутствует в другом, это значит, что у нас есть путь. Пространство поиска в таком случае вдвое меньше, чем в однонаправленным поиске. Посмотрите на рис. 5.4: серое пространство меньше белой области.

Рис. 5.4. Пространства однонаправленного и двунаправленного поиска

Рис. 5.5. Поиск кратчайшего маршрута от аэропорта JFK до аэропорта GVA при помощи алгоритма Дейкстры

Вы когда-нибудь задавались вопросом, как поисковой системе Google удается анализировать миллиарды веб-страниц и показывать вам самые подходящие? В этом процессе задействовано множество алгоритмов, но самым важным является алгоритм PageRank.

Прежде чем основать компанию Google, Сергей Брин и Ларри Пейдж работали научными сотрудниками в области computer science в Стэнфордском университете и занимались исследованием графовых алгоритмов. Они смоделировали Всемирную паутину в виде графа: веб-страницы — это вершины, и связи между ними — ребра.

Они решили, что если веб-страница получает много связей от других важных страниц, то она тоже должна быть важной. Опираясь на эту идею, они создали алгоритм PageRank. Он выполняется в несколько заходов. Вначале каждая веб-страница в графе имеет то же количество единиц значимости, что и остальные. После каждого захода она распределяет свои единицы среди страниц, ссылки на которые на ней размещены. Этот процесс повторяется до тех пор, пока все значения не стабилизируются. Стабилизированная оценка каждой страницы называется ее рангом, отсюда и название — PageRank (англ. «ранг страницы»). Используя этот алгоритм для определения важности веб-страниц, поисковая система Google быстро заняла доминирующую позицию среди других аналогичных сервисов.

Алгоритм PageRank применим и к другим типам графов. Например, мы можем смоделировать пользователей сети Twitter на графе, а затем вычислить ранг каждого. Как вы считаете, будут ли пользователи с более высоким рангом известными людьми?

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

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

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

Задачи, где целевой показатель и ограничения можно смоделировать с использованием линейных уравнений[55], называются задачами линейной оптимизации. Давайте посмотрим, как решаются эти задачи.

Прежде всего определим переменные нашей задачи. Мы хотим найти количество шкафов каждого типа, которые следует приобрести, поэтому:

• x — количество шкафов модели X;

• y — количество шкафов модели Y.

Мы хотим максимизировать емкость хранения. Дадим емкости хранения имя z и смоделируем это значение как функцию от x и y:

• z = 8x + 12y.

Теперь выберем значения x и y, которые дадут максимальное значение z. При этом мы должны соблюсти ограничение по бюджету (то есть уложиться в 140 долларов) и по площади (она должна быть меньше 72 квадратных футов). Смоделируем эти ограничения:

• 10x + 20y ≤ 140 (ограничение по бюджету);

• 6x + 8y ≤ 72 (ограничение по площади);

• x ≥ 0, y ≥ 0 (нельзя купить отрицательное количество шкафов).

Как бы вы решили эту задачу? Покупка максимального количества шкафов с наилучшим соотношением хранение/площадь не является правильным решением, потому что пространство под установку шкафов ограниченно. Можно пойти по пути полного перебора: написать программу, вычисляющую z для всех возможных x и y, и получить пару, дающую оптимальное z. Это решение годится для простых задач, но оно невыполнимо при большом количестве переменных.

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

Симплексные решатели требуют указать функцию для максимизации (или минимизации) и уравнения, моделирующие ограничения. Решатель сделает все остальное. В данной задаче максимальное значение z достигается при x = 8 и y = 3.

Рис. 5.6. Значения x и y, удовлетворяющие ограничениям задачи

Симплекс-метод отыскивает оптимальное значение в пространстве приемлемых решений. Чтобы понять механику его работы, представим все возможные значения x и y на двумерной плоскости (рис. 5.6). Ограничения по бюджету и площади представлены на графике линиями.

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

Многие задачи, касающиеся сетей и потоков, можно сформулировать с точки зрения линейных уравнений и, следовательно, решить при помощи симплекс-метода. Например, во время холодной войны армия США вычисляла маршруты пополнения материально-технических запасов, которые Советский Союз мог использовать в Восточной Европе (рис. 5.7).

Рис. 5.7. Рассекреченный военный отчет 1955 г., показывающий пропускную способность советской сети железных дорог

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

Чтобы смоделировать задачу с линейными уравнениями, каждой железной дороге нужно назначить переменную, представляющую объем грузов, который она сможет перевезти. Ограничения следующие: ни одна железная дорога не может перевезти больше своей пропускной способности; входящий поток грузов должен быть эквивалентен исходящему во всех населенных пунктах, кроме производящего и потребляющего городов. Затем нужно подобрать такие значения для переменных, которые позволят доставить в получающий город максимум грузов.

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

Появление реляционной модели в конце 1960-х стало огромным рывком в управлении информацией. Реляционные базы данных помогают избегать дублирования информации и противоречий. Большинство СУБД, которые используются сегодня, являются реляционными.

В реляционной модели данные разделены на таблицы. Таблица — это нечто вроде матрицы или листа Excel. Каждая запись в ней является строкой. Столбцы — различные свойства записей. Обычно столбцы определяют типы хранимых в них данных. Столбцы могут также определять другие ограничения: обязательно ли строка должна иметь в этом столбце значение, должно ли оно быть уникальным по всем строкам в таблице и т. д.

Столбцы обычно называются полями. Если столбец допускает только целые числа, то мы говорим, что это целочисленное поле. Разные таблицы используют разные типы полей. Организация таблицы базы данных задается ее полями и ограничениями, которые те налагают. Такая комбинация полей и ограничений называется схемой таблицы.

Все записи — строки, и СУБД не примет новую строку, если та нарушает схему таблицы. В этом состоит большой недостаток реляционной модели. Когда характеристики данных значительно варьируются, подгонка их к фиксированной схеме может создать много хлопот. Но если вы работаете с данными однородной структуры, то фиксированная схема гарантирует, что все они будут допустимыми.

Представим базу данных счетов-фактур, которая содержится в единственной таблице. По каждому счету мы должны хранить информацию о заказе и клиенте. Когда в базе данных хранится несколько счетов, относящихся к одному клиенту, информация повторяется (рис. 6.1).

Рис. 6.1. Данные о счетах-фактурах, хранящиеся в единственной таблице

Повторяющейся информацией трудно управлять, и ее сложно обновлять. Чтобы избежать таких сложностей, реляционная модель разбивает связанную информацию на разные таблицы. Например, разделим наши данные о счетах-фактурах на две таблицы — «Заказы» и «Клиенты» — и сделаем так, чтобы каждая строка в первой таблице ссылалась на строку во второй (рис. 6.2).

Рис. 6.2. Связи между строками позволяют избежать дублирования данных

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

Рис. 6.3. Специалисты, награжденные премией Тьюринга

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

Связь между специалистами в области computer science и премиями не настолько проста, как между клиентами и заказами в предыдущем примере. Премия может быть поделена между двумя специалистами, и нигде не сказано, что ученый имеет право получить ее всего один раз. Поэтому мы используем таблицу «Лауреаты», только чтобы хранить связи между специалистами и премиями.

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

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

В большинстве СУБД существуют готовые инструменты, которые помогают создавать и применять сценарии миграции схемы, а также возвращать базу данных к прежнему состоянию. Некоторые большие системы претерпевают сотни миграций за год, так что эти инструменты играют незаменимую роль. Если не делать миграцию схемы, а вручную вносить изменения в базу данных, ее потом будет трудно вернуть к конкретной рабочей версии. Такой «ручной» подход не гарантирует совместимости между локальными базами данных различных разработчиков ПО. Подобные проблемы часто случаются в больших программных проектах, где наплевательски относятся к работе с базами данных.

Почти каждая реляционная СУБД поддерживает язык запросов под названием SQL[58]. Мы не ставим перед собой задачи дать вам всесторонний курс по SQL, но в этой книге вы получите общее представление о том, как он работает. Важно разбираться в SQL хотя бы поверхностно, даже если вы непосредственно с ним не работаете. SQL-запрос — это команда, сообщающая, какие данные должны быть получены:

SELECT <field name> [, <field name>, <field name>,…]

FROM <table name>

WHERE <condition>;

Элементы, идущие после SELECT, — это поля, которые нужно получить. Чтобы получить все поля в таблице, можно написать: SELECT *. В базе данных может быть несколько таблиц, поэтому FROM уточняет, какую таблицу вы запрашиваете. После команды WHERE вы устанавливаете критерии отбора строк. Для перечисления многочисленных условий можно использовать булеву логику. Следующий запрос получает все поля из таблицы customers («клиенты»), фильтруя строки по полям name («имя») и age («возраст»):

SELECT * FROM customers

WHERE age > 21 AND name = "John";

Вы можете послать запрос: SELECT * FROM customers, без оператора WHERE. СУБД выдаст вам список всех клиентов. Помимо этого, имеются другие операторы запросов, о которых вам следует знать: оператор ORDER BY сортирует результаты по указанному полю (полям), а GROUP BY поможет выполнить группировку и получить агрегированные результаты для групп. Например, при наличии таблицы customers («клиенты») с полями country («страна») и age («возраст»), вы можете выполнить такой запрос:

SELECT country, AVG(age)

FROM customers

GROUP BY country

ORDER BY country;

Он вернет сортированный список стран, где проживают ваши клиенты, вместе со средним возрастом клиентов по каждой стране. SQL предоставляет и другие агрегатные функции. Например, замените AVG(age) на MAX(age), и вы получите возраст самого старого клиента в каждой стране.

Иногда бывает нужно изучить информацию из строки и строк, с которыми она связана. Представьте, что у вас есть таблица с заказами и таблица с клиентами. Таблица orders имеет внешний ключ для ссылки на клиентов. Чтобы найти информацию о клиентах, сделавших дорогостоящие заказы, придется выбрать данные из обеих таблиц. Но вам не нужно запрашивать их по отдельности и сопоставлять записи самостоятельно. Для этого в языке SQL имеется специальная команда:

SELECT DISTINCT customers.name, customers.phone

FROM customers

JOIN orders ON orders.customer = customers.id

WHERE orders.amount > 100.00;

Этот запрос вернет имена и телефонные номера клиентов, сделавших заказы на сумму более 100 долларов. Команда SELECT DISTINCT заставляет СУБД вернуть каждого клиента только один раз. JOIN позволяет делать очень гибкие запросы[59], но эта гибкость имеет свою цену. Соединения обходятся дорого. Базе данных придется рассмотреть все сочетания строк из таблиц, которые вы объединяете в своем запросе. Администратор базы данных должен всегда принимать во внимание произведение числа строк объединяемых таблиц. Для очень больших таблиц соединения становятся невыполнимыми. Оператор JOIN — это самый мощный инструмент и одновременно главная слабость реляционных баз данных.

Чтобы от первичного ключа таблицы была польза, необходимо иметь возможность быстро получить запись по ID. Для этого СУБД строит вспомогательный индекс, содержащий ID строк, и соответствующие им адреса в памяти (рис. 6.4). По сути, индекс — это сбалансированное двоичное дерево поиска (см. раздел «Структуры» предыдущей главы). Каждая строка в таблице соответствует узлу в дереве.

Рис. 6.4. Индекс, отображающий значения ID и расположение соответствующих строк

Ключи узлов — это значения в индексируемом поле. Чтобы найти запись с заданным значением, мы ищем его в дереве. Найдя узел, мы получаем адрес, который он хранит, и используем его для выборки записи. Поиск по двоичному дереву имеет сложность O(log n), поэтому нахождение записей в больших таблицах выполняется быстро.

Обычно СУБД создает индекс для каждого первичного ключа в базе данных. Но если часто приходится искать записи по другим полям (например, искать клиентов по именам), можно поручить СУБД создать для них дополнительные индексы.

Ограничения уникальности. Индексы часто создаются автоматически для полей, которые имеют ограничение уникальности. При вставке новой строки СУБД должна обследовать всю таблицу, чтобы удостовериться, что ни одно ограничение уникальности не нарушено. Не будь индекса, такая проверка означала бы, что нужно свериться со всеми строками в таблице. При помощи индекса мы можем быстро выполнить поиск и, например, обнаружить, что значение, которое мы пытаемся вставить, уже присутствует. Индексация полей, имеющих ограничение уникальности, необходима для быстрой вставки элементов.

Сортировка. Индексы помогают выбирать строки в порядке сортировки по индексированным полям. Например, если имеется индекс для поля name («имя»), мы можем получить строки, отсортированные по имени, без дополнительных вычислений. Если применить команду ORDER BY к полю без индекса, СУБД придется отсортировать данные в памяти, прежде чем выполнить запрос. Многие СУБД могут даже отказаться выполнять запрос, требующий произвести сортировку по неиндексированному полю, если в работу будет вовлечено слишком много строк.

Если вы должны отсортировать строки сначала по стране, а затем по возрасту, наличие индекса в поле age («возраст») или в поле country («страна») не сильно вам поможет. Индекс в country позволяет выбирать строки, отсортированные по стране, но затем вам потребуется вручную сортировать по возрасту элементы, которые имеют одинаковую страну. Когда требуется сортировка по двум полям, используются комбинированные, или объединенные, индексы. Они индексируют многочисленные поля и не способны помочь искать элементы быстрее, зато позволяют легко получать данные, отсортированные по нескольким полям.

Производительность. Итак, индексы — это круто: они позволяют делать сверхбыстрые запросы и мгновенно получать доступ к отсортированным данным. Тогда почему у нас нет индексов для всех полей в каждой таблице? Проблема в том, что, когда новая запись вставляется в таблицу или удаляется из нее, приходится обновлять все индексы, чтобы отразить это изменение. Если индексов много, то обновление, вставка или удаление строк могут стать в вычислительном плане дорогостоящими операциями (вспомним про балансировку дерева). Более того, индексы занимают ограниченное дисковое пространство.

Вы должны следить за тем, как ваше приложение использует базу данных. СУБД обычно поставляются вместе с инструментами, которые помогают это делать. Они могут «объяснять» запросы, сообщая, какие индексы использовались, а также сколько строк необходимо было последовательно просканировать, чтобы выполнить запрос. Если ваши запросы тратят впустую слишком много времени, последовательно сканируя данные в некоем поле, то добавьте для этого поля индекс и посмотрите, будет ли польза. Например, если вы часто ищете в базе данных людей конкретного возраста, то определение индекса для поля age позволит СУБД сразу отбирать строки, соответствующие конкретному возрасту. Вы сэкономите время, избежав последовательного просмотра базы данных с дальнейшей фильтрацией строк, не соответствующих требуемому возрасту.

Если вы хотите настроить базу данных, чтобы повысить ее производительность, чрезвычайно важно знать, какие индексы стоит сохранять, а какие — отбрасывать. Если доступ к БД главным образом осуществляется в режиме чтения, а обновляется она редко, может иметь смысл создать больше индексов. Плохая индексация — главная причина замедлений в коммерческих системах. Небрежные системные администраторы зачастую не задаются вопросом, как выполняются типичные запросы, — они просто индексируют произвольные поля, которые, по их мнению, будут способствовать производительности. Этого не стоит делать! Воспользуйтесь «объясняющими» инструментами, чтобы проверить свои запросы и создать индексы только там, где они нужны.

Представим, что скрытный швейцарский банк не ведет учета денежных переводов: его база данных просто хранит баланс счетов. Предположим, что кто-то хочет перечислить деньги со своего счета на счет друга в том же банке. Две операции должны быть выполнены в базе данных банка — денежную сумму нужно вычесть из одного баланса и прибавить к другому.

Сервер БД обычно позволяет многочисленным клиентам читать и записывать данные одновременно — исполнение операций в последовательном режиме сделало бы любую СУБД слишком медленной. Но вот подвох: если кто-то запросит общий баланс всех счетов после регистрации вычитания, но до соответствующего добавления, то какая-то сумма будет отсутствовать. Или вот вариант похуже: а что, если система окажется обесточена между этими двумя операциями? Когда сервер снова заработает, будет трудно выяснить причину расхождения в данных.

Нам нужны способы, которыми СУБД выполняла бы либо все изменения, входящие в многосоставную операцию, либо сохраняла данные неизменными. С этой целью системы баз данных поддерживают транзакции. Транзакция — список операций, которые должны быть выполнены атомарно[60]. Транзакции упрощают жизнь программиста: вместо него за обеспечение непротиворечивости данных отвечает СУБД. От программиста только требуется обертывать зависимые операции в соответствующие команды:

START TRANSACTION;

UPDATE vault SET balance = balance + 50 WHERE id=2;

UPDATE vault SET balance = balance — 50 WHERE id=1;

COMMIT;

Запомните: выполнение многосоставных обновлений без транзакций рано или поздно создаст беспорядочные, непредсказуемые и трудные в обнаружении противоречия в ваших данных.

Реляционные базы данных замечательны, однако у них есть некоторые недостатки. По мере усложнения приложения в его реляционную базу данных приходится добавлять все больше таблиц. Запросы становятся все менее понятными. И, главное, все чаще приходится прибегать к соединениям (JOIN), требующим большого объема вычислений и создающим в системе узкие места.

Рис. 6.5[61]

Нереляционная модель не использует табличные связи. Она почти никогда не требует объединять информацию из нескольких записей. Поскольку нереляционные СУБД используют языки запросов, отличные от SQL, они также называются базами данных NoSQL.

Наиболее известным типом баз данных NoSQL являются документные хранилища. В них записи хранятся в том виде, в котором они необходимы приложению. Рис. 6.6, приведенный ниже, сравнивает табличный и документный способы хранения постов в блоге.

Рис. 6.6. Данные в реляционной модели (вверху) и данные в NoSQL (внизу)

Заметили, что все данные о сообщении копируются в соответствующую ему запись? Нереляционная модель предполагает возможность дублирования информации при необходимости. Однако дублированные данные сложно своевременно обновлять и поддерживать их непротиворечивость. С другой стороны, группируя соответствующие данные, документное хранилище может предложить бо́льшую гибкость:

• вам не нужно соединять строки;

• можно обойтись без фиксированных схем;

• каждая запись может иметь собственное сочетание полей.

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

Документы имеют поле первичного ключа, поэтому их можно связывать друг с другом. Но операции JOIN в документных хранилищах неэффективны. Иногда они даже невозможны, в этом случае вам придется следить за связями между документами самостоятельно. И то и другое плохо — если документы имеют общие данные, их приходится дублировать.

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

Хранилище «ключ — значение» — это простейшая форма организованного хранения данных. В основном используется для кэширования. Например, когда некто запрашивает определенную веб-страницу на сервере, тот должен выбрать соответствующие ей данные из БД и использовать их для конструирования HTML-разметки, которую увидит пользователь. В сайтах с высокой посещаемостью, где случаются тысячи параллельных доступов, делать это становится невозможным.

Для решения проблемы мы используем хранилище «ключ — значение» как механизм кэширования. Ключом является требуемый URL-адрес, значением — HTML-разметка соответствующей веб-страницы. В следующий раз, когда кто-то запросит тот же URL-адрес, готовый код HTML просто будет извлечен из хранилища «ключ — значение» через ключ-адрес.

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

В графовой базе данных записи хранятся в виде вершин, а связи — в виде ребер. Вершины не привязаны к фиксированной схеме и могут содержать данные в разном формате. Графовая структура делает эффективной работу с записями в соответствии с их связями. Вот как информация из рис. 6.6 будет выглядеть в форме графа:

Рис. 6.7. Информация блога, хранящаяся в графовой базе данных

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

Если ваши данные похожи на сеть, подумайте об использовании графовой базы данных. Этот тип БД особенно полезен, когда между компонентами данных много важных связей. Графовые базы данных также позволяют выполнять различные типы граф-ориентированных запросов. Например, если вы храните данные об общественном транспорте в графе, можете прямо запросить лучший маршрут между двумя остановками в одну сторону или туда и обратно.

Популярный в последнее время термин «большие данные» (big data) описывает ситуации обработки данных, которые чрезвычайно сложны с точки зрения объема, скорости или разнообразия[62]. «Объем» больших данных — это, например, обработка тысяч терабайт информации в случае с БАК[63]. «Скорость» применительно к большим данным означает, что вы должны сохранять миллион записей в секунду без задержек или быстро выполнять миллиарды запросов на чтение. «Разнообразие» означает, что данные не имеют строгой структуры, и потому становится очень трудно с ними справляться, используя традиционные реляционные базы данных.

Каждый раз, когда вам требуется искать нестандартный подход к управлению данными по причине их объема, скорости или разнообразия, вы можете смело сказать, что имеете дело с большими данными. Для выполнения некоторых современных научных экспериментов (к примеру, связанных с БАК или SKA[64]) специалисты уже проводят исследования в области мегаданных, предполагающей хранение и анализ миллионов терабайт информации.

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

Реляционные БД ориентированы на данные: они максимизируют структурирование данных и устраняют их дублирование независимо от того, в каком виде те требуются. Нереляционные БД, напротив, ориентированы на применение: они облегчают доступ к данным и их использование в соответствии с вашими потребностями.

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

Однако нужно помнить: какой бы крутой ни была ваша нереляционная база данных, ответственность за обновление дублированной информации по всем документам и коллекциям лежит только на вас. Только вы должны принимать меры для поддержания информации в непротиворечивом состоянии. Запомните: большая мощь этих БД идет рука об руку с большой ответственностью.

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

• Базы данных объемом в нескольких сотен терабайт. Найти одиночный компьютер с таким большим пространством хранения нереально.

• СУБД, обрабатывающие несколько тысяч одновременных запросов в секунду[65]. Никакой одиночный компьютер не имеет достаточных возможностей по передаче данных по сети или по их обработке, чтобы справиться с такой нагрузкой.

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

Для таких ситуаций существуют СУБД, способные работать на нескольких скоординированных компьютерах, образующие распределенные базы данных. Давайте рассмотрим наиболее распространенные способы организации таких БД.

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

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

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

Если ваша СУБД должна обрабатывать большое количество одновременных запросов на запись, то один-единственный ведущий компьютер не справится с этой задачей. В таком случае все компьютеры в кластере становятся ведущими. Для равного распределения входящих запросов на чтение и запись между машинами используется балансировщик нагрузки (рис. 6.9).

Рис. 6.9. Распределенная база данных с многочисленными ведущими машинами

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

Если БД получает много запросов на запись с большими объемами данных, бывает чрезвычайно трудно синхронизировать ее везде в кластере. Некоторые компьютеры могут не иметь достаточного пространства для размещения всех данных полностью. Одно из решений состоит в том, чтобы поделить базу данных между компьютерами. Поскольку каждый из них владеет лишь ее частью, маршрутизатор направляет запросы соответствующей машине (рис. 6.10).

Такая конфигурация способна обрабатывать многочисленные запросы на чтение и запись в случае с очень большими базами данных. Но с ней возможна проблема: если машина в кластере выходит из строя, фрагмент данных, за который она отвечала, становится недоступен. Для снижения риска фрагментирование можно использовать в сочетании с репликацией (рис. 6.11).

Рис. 6.10. Пример фрагментации базы данных. Запросы направляются согласно первой букве в запрашиваемом ID

Рис. 6.11. Фрагментированная база данных с тремя репликами на фрагмент

В таком случае каждый фрагмент выполняется кластером «ведущий — ведомый». Это еще более увеличивает возможность СУБД обслуживать запросы на чтение. И если один из главных серверов во фрагменте отключается от сети, ведомое устройство автоматически занимает его место — это гарантирует, что система не развалится и не потеряет данные.

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

Предположим, вы продаете на сайте билеты в кино. Трафик слишком большой, поэтому база данных распределена на два сервера. Элис приобретает билет на сервере А. Боб обслуживается сервером Б и видит тот же самый свободный билет. Прежде чем информация о покупке Элис дойдет до сервера Б, Боб тоже заплатит за этот билет. Теперь два сервера имеют противоречивость в данных. Чтобы исправить ситуацию, вам придется отменить одну из продаж и принести извинения либо недовольной Элис, либо недовольному Бобу.

Системы баз данных часто содержат инструменты для снижения противоречивости данных. Например, где-то вам позволяют делать запросы, которые обеспечивают соблюдение непротиворечивости данных по всему кластеру. Однако это уменьшает производительность СУБД. В особенности сказанное касается транзакций: они могут вызывать серьезные проблемы производительности в распределенных базах данных, поскольку вынуждают выполнять координацию всех машин в кластере с блокировкой потенциально больших объемов информации.

Есть компромиссное решение между непротиворечивостью и производительностью. Если ваши запросы к БД не требуют соблюдения строгой непротиворечивости данных, то говорят, что они работают в условиях потенциальной непротиворечивости. Данные гарантированно будут непротиворечивыми в конечном счете — то есть через какое-то время. Это означает, что некоторые запросы на запись, вероятно, будут отклонены, а некоторые запросы на чтение могут вернуть устаревшую информацию.

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

Компьютер — машина, которая подчиняется командам, управляющим данными. Он имеет два главных компонента: процессор и память. Память, она же ОЗУ[67], — это то место, где мы пишем команды. Она также хранит данные, которыми компьютер оперирует. Процессор, или ЦП[68], получает команды и данные из памяти и выполняет соответствующие вычисления. Давайте разберемся, как работают эти два компонента.

Память поделена на множество ячеек. Каждая хранит крошечный объем данных и имеет числовой адрес. Чтение или запись данных в памяти выполняется посредством операций, которые воздействуют на одну ячейку за раз. Чтобы прочитать ячейку памяти или произвести запись в нее, мы должны передать ее числовой адрес (рис. 7.1).

Рис. 7.1. Сообщение для ОЗУ выполнить операцию в ячейке № 210 (11010010)

Поскольку память является электрической схемой, мы передаем адреса ячеек по проводам в виде двоичных чисел[69]. Каждый провод передает двоичную цифру. Высокое напряжение соответствует сигналу «единица», низкое — сигналу «ноль».

Рис. 7.2. Память может работать в режиме чтения или записи

Память способна выполнить с адресом ячейки две операции: получить хранящееся в ней значение или записать новое. Память имеет специальный входной контакт для установки ее рабочего режима (рис. 7.2).

Каждая ячейка памяти хранит 8-разрядное двоичное число, которое называется байтом. В режиме чтения память получает хранящийся в ячейке байт и выводит его по восьми проводам, которые передают данные (рис. 7.3).

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

Группа проводов, используемых для передачи одинаковых данных, называется шиной. Восемь проводов для передачи адресов формируют адресную шину. Другие восемь, используемых для передачи информации в ячейки памяти и обратно, формируют шину данных. Адресная шина является однонаправленной (используется только для получения данных), а шина данных — двунаправленной (используется для отправки и для получения данных).

Рис. 7.3. Чтение числа 32 из ячейки с адресом 211

Рис. 7.4. Запись числа 33 в ячейку с адресом 212

В любом компьютере ЦП и ОЗУ постоянно обмениваются данными: процессор выбирает команды и данные из памяти и иногда сохраняет туда данные для вывода и промежуточные результаты вычислений (рис. 7.5).

Рис. 7.5. ЦП подключен проводами к ОЗУ

Центральный процессор имеет несколько ячеек внутренней памяти, которые называются регистрами. Он может выполнять простые математические операции с числами, хранящимися в этих регистрах. Он также может перемещать данные между регистрами и ОЗУ. Вот примеры типичных операций, которые приходится исполнять центральному процессору:

• скопировать данные из ячейки памяти № 220 в регистр № 3;

• сложить число в регистре № 3 с числом в регистре № 1.

Набор всех операций, которые может выполнять ЦП, называется его набором команд. Каждой операции в наборе команд присвоено число. Машинный код по существу — последовательность чисел, представляющих операции центрального процессора. Они хранятся в виде чисел в ОЗУ. Мы сохраняем входные/выходные данные, промежуточные результаты и машинный код — все вперемешку — в ОЗУ[70].

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

Рис. 7.6. Часть технического описания Intel 4004, показывающая, как операциям ставятся в соответствие числа. Это был первый в мире ЦП, выпущенный в 1971 году

ЦП работает в бесконечном цикле, постоянно выбирая и исполняя команды из памяти. В ядре цикла находится регистр PC, или счетчик команд[71]. Это специальный регистр, который хранит адрес памяти следующей исполняемой команды. Вот что делает ЦП:

1) выбирает команду в адресе памяти, заданном регистром PC;

2) увеличивает PC на 1;

3) выполняет команду;

4) возвращается к шагу 1.

Когда ЦП включается, PC присваивается значение по умолчанию, то есть адрес первой команды, выполняемой машиной. Это обычно неизменяемая встроенная программа, ответственная за загрузку основных функций компьютера[72].

После включения ЦП начинает выполнять этот бесконечный цикл выборки и исполнения, пока вы не выключите компьютер. Однако если бы ЦП мог выполнять только упорядоченный, последовательный список операций, то компьютер был бы не более чем продвинутым калькулятором. ЦП удивителен, потому что ему можно поручить записать новое значение в регистр PC, заставив процесс исполнения команд выполнить переход — «перепрыгнуть» куда-то в другое место в памяти. Такое ветвление может быть условным выражением. Например, команда ЦП может сообщить: «Записать в PC адрес № 200, если регистр № 1 хранит ноль». Это позволяет компьютерам выполнять операторы, подобные следующему:

if x = 0

····compute_this()····# вычислить это

else

····compute_that()····# вычислить то

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

При помощи множества этих простых операций можно выражать запутанные процедуры. Например, код классической игры Space Invaders (рис. 7.7) включает порядка 3000 машинных команд.

Рис. 7.7. Игру Space Invaders, выпущенную в 1978 году, многие называют самой влиятельной за всю историю

Тактовая частота ЦП. В 1980-х годах чрезвычайно популярной стала игра Space Invaders. Люди играли в нее на игровых автоматах, оборудованных процессорами с тактовой частотой 2 МГц. Этот показатель — число базовых операций, которые процессор выполняет в секунду. Процессор с тактовой частотой 2 МГц выполняет примерно 2 млн базовых операций в секунду. Для выполнения машинной команды требуется от пяти до десяти базовых операций. Следовательно, винтажные игровые автоматы выполняли сотни тысяч машинных команд каждую секунду.

В условиях современного технологического прогресса обычные настольные компьютеры и смартфоны обычно имеют процессоры с тактовой частотой 2 ГГц. Они способны выполнять сотни миллионов машинных команд каждую секунду. А с недавних пор массовое применение получили многоядерные ЦП. Четырехъядерный процессор с тактовой частотой 2 ГГц может выполнять почти миллиард машинных команд в секунду. И, похоже, в перспективе у наших процессоров будет все больше ядер[73].

Архитектуры ЦП. Вы когда-нибудь задавались вопросом, почему нельзя вставить компакт-диск для Sony PlayStation в настольный компьютер и начать играть? Или почему приложения для iPhone не запускаются на Mac? Причина проста: разные архитектуры ЦП.

В наше время архитектура x86 является довольно стандартной, и потому одинаковый код может выполняться на большинстве персональных компьютеров. Однако сотовые телефоны, например, имеют процессоры с другой, более энергоэффективной архитектурой. Разные архитектуры означают разные наборы процессорных команд и, следовательно, разные способы их кодирования числами. Числа, которые транслируются как команды для ЦП вашего настольного компьютера, не являются допустимыми командами для ЦП в вашем сотовом телефоне, и наоборот.

32-разрядная архитектура против 64-разрядной. Первый ЦП под названием Intel 4004 был основан на 4-разрядной архитектуре. Это означает, что он мог оперировать двоичными числами (суммировать, сравнивать, перемещать их) до 4 разрядов в одной машинной команде. Шина данных и шина адресов на Intel 4004 состояли всего из четырех проводов каждая.

Вскоре после этого широкое распространение получили 8-разрядные ЦП. Они использовались в ранних персональных компьютерах, работавших под DOS[74]. Game Boy, популярный в 1980–1990-х годах переносной игровой компьютер, тоже имел 8-разрядный процессор. Одиночная команда в таких ЦП может оперировать 8-разрядными двоичными числами.

Быстрый технологический прогресс позволил занять доминирующее положение 16-разрядной, а затем — 32-разрядной архитектуре. Емкость регистров ЦП была увеличена до 32 разрядов. Для более емких регистров естественно потребовалось расширить шины данных и адресов. Адресная шина с 32 проводами позволяет адресовать 2³² байт (4 Гб) памяти.

А затем наша жажда вычислительной мощи стала просто неудержимой. Компьютерные программы быстро усложнялись и использовали все больше памяти. 4Гб ОЗУ оказалось слишком мало. И обращение к памяти большего объема с числовыми адресами, которые укладываются в 32-разрядные регистры, превратилась в непростой процесс. Это ознаменовало появление доминирующей сегодня 64-разрядной архитектуры. 64-разрядные процессоры могут оперировать в одной команде чрезвычайно большими числами. При этом 64-разрядные регистры хранят адреса в огромном пространстве памяти — 2⁶⁴ байт, что составляет более 17 млрд гигабайт.

Прямой порядок байтов против обратного. Некоторые разработчики компьютеров посчитали, что в ОЗУ и ЦП целесообразно хранить числа слева направо (от младших разрядов к старшим), способом, известным как обратный порядок байтов. Другие предпочли записывать данные справа налево, способом, который называется прямым порядком байтов. Двоичная последовательность 1-0-0-0-0-0-1-1 может представлять разные числа в зависимости от порядка байтов:

• прямой порядок байтов: 2⁷ + 2¹ + 2⁰ = 131;

• обратный порядок байтов: 2⁰ + 2⁶ + 2⁷ = 193.

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

Эмуляторы. Иногда бывает полезно на своем компьютере выполнить некоторый программный код, разработанный для другого ЦП. Это позволяет протестировать приложение для iPhone без iPhone или сыграть в вашу любимую старинную игру для Super Nintendo. Для этих задач существуют компоненты программного обеспечения, которые называются эмуляторами.

Эмулятор имитирует целевую машину: компьютер притворяется, что имеет тот же ЦП, ОЗУ и другие аппаратные средства. Команды декодируются программой эмулятора и выполняются в эмулированной машине. Как вы понимаете, очень сложно эмулировать одну машину внутри другой, когда у них разная архитектура. Но поскольку наши компьютеры намного быстрее старых, это стало возможным. Если вы раздобудете эмулятор Game Boy и позволите своему компьютеру создать виртуальную игровую приставку, то сможете играть в игры точно так же, как если бы вы играли на настоящем Game Boy.

Мы программируем компьютеры, чтобы они могли делать МРТ, распознавать речь, исследовать далекие планеты и выполнять много других сложных задач. Удивительно, но все, на что способен компьютер, в конечном счете осуществляется посредством простых команд ЦП, которые просто суммируют и сравнивают числа. Сложные приложения, например интернет-браузер, требуют миллионов или миллиардов таких машинных команд.

Но мы редко пишем программы непосредственно как команды ЦП. Человеку не под силу написать реалистичную трехмерную компьютерную игру подобным образом. Чтобы выражать свои предписания более естественным и компактным образом, люди создали языки программирования. Мы пишем программный код на этих языках[75], а затем используем программу, которая называется компилятором, для перевода наших предписаний в машинные команды, понятные процессору.

Чтобы объяснить, что делает компилятор, давайте представим простую математическую аналогию. Если мы хотим попросить кого-то вычислить факториал числа 5, мы можем задать вопрос:

5! =?

Однако если человек, которого мы спрашиваем, не знает, что такое факториал, то вопрос не будет иметь смысла. Нам придется его перефразировать, используя более простые операции:

5 × 4 × 3 × 2 × 1 =?

А вдруг человек, которого мы спрашиваем, умеет только суммировать? Нам придется упростить наше выражение еще больше:

5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5+

5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 =?

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

Алан Тьюринг, основоположник компьютерных вычислений, обнаружил, что простые машины способны вычислить все, что в принципе поддается вычислению. Чтобы обладать универсальными вычислительными возможностями, машина должна уметь выполнять программу, которая содержит команды:

• чтения и записи данных в памяти;

• условного ветвления (если адрес памяти имеет заданное значение, то перейти к другой точке в программе).

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

Недавно было показано, что команда ЦП под названием MOV («перемещение») является полной по Тьюрингу. Это значит, что ЦП, который выполняет только команду MOV, способен делать все то, что может полноценный ЦП. Другими словами, любой тип программного кода вполне реально выразить исключительно с помощью команды MOV[76].

Важный вывод из этой новости состоит в том, что если программу можно записать на языке программирования, то ее можно переписать для выполнения на любой полной по Тьюрингу машине, какой бы простой та ни была. Компилятор — это волшебная программа, которая автоматически транслирует код из сложного языка в более простой.

Рис. 7.8[77]

Скомпилированные компьютерные программы по существу являются последовательностями команд ЦП. Как мы выяснили, код, скомпилированный для настольного компьютера, не станет работать на смартфоне, потому что эти машины имеют процессоры различной архитектуры. Но скомпилированная программа может не работать и на одном из двух компьютеров, имеющих одинаковую архитектуру ЦП. Дело в том, что программы, чтобы запускаться без проблем, должны взаимодействовать с операционной системой (ОС) компьютера.

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

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

Однако разные ОС часто используют несовместимые системные вызовы. Системный вызов печати чего-либо на экране в Windows отличается от такового в Mac OS или Linux.

Вот почему, если вы компилируете программу для выполнения в Windows с процессором x86, она не будет работать в Mac с таким же процессором. Скомпилированный программный код должен быть ориентирован не только на конкретную архитектуру процессора, но и на конкретную операционную систему.

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

Именно поэтому вам не следует жертвовать простотой чтения кода в пользу его микрооптимизации. Компилятор так или иначе применит все тривиальные оптимизации. Посмотрите на этот фрагмент кода:

function factorial(n)

····if n > 1

········return factorial(n — 1) * n

····else

········return 1

Кто-то скажет, что его лучше заменить на этот эквивалент:

function factorial(n)

····result ← 1

····while n > 1

········result ← result * n

········n ← n — 1

····return result

Да, выполнение процедуры factorial без рекурсии использует меньше вычислительных ресурсов. Но это еще не повод менять программный код. Современные компиляторы автоматически перепишут простые рекурсивные функции. Вот еще один пример:

i ← x + y + 1

j ← x + y

Компиляторы избавятся от повторного вычисления x + y и сделают вот такое преобразование:

t1 ← x + y

i ← t1 + 1

j ← t1

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

Впрочем, иногда этап компиляции просто отсутствует. Давайте посмотрим, что это за ситуации.

Некоторые языки программирования, так называемые языки сценариев, выполняются без прямой компиляции в машинный код. К ним относятся JavaScript, Python и Ruby. Код на этих языках выполняет не центральный процессор непосредственно, а интерпретатор — программа, которая должна быть установлена на компьютере.

Так как интерпретатор переводит программный код в машинный в режиме реального времени, тот обычно работает намного медленнее скомпилированного кода. С другой стороны, программист может выполнить код, не ожидая окончания компиляции. Когда проект очень большой, компиляция иногда занимает несколько часов.

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

Рис. 7.9. Компиляция[78]

Восстановить исходный код скомпилированной программы — тот, что был до момента компиляции, — нельзя[79]. Но можно декодировать бинарную программу, трансформировав числа, в которых закодированы команды ЦП, в последовательность команд, более-менее понятную для человека. Этот процесс называется дизассемблированием.

Затем можно рассмотреть команды ЦП и попытаться выяснить, что они делают, — такой процесс называется обратным инженерным анализом. Некоторые программы дизассемблирования значительно помогают в этом, автоматически обнаруживая и аннотируя системные вызовы и часто используемые функции. Благодаря инструментам дизассемблирования хакер может разобраться в любом аспекте работы двоичного кода. Я уверен, что многие лучшие компании в области ИТ имеют секретные лаборатории обратного инженерного анализа, где изучают программное обеспечение конкурентов.

Хакеры часто анализируют двоичный код лицензируемых программ, таких как Microsoft Windows, Adobe Photoshop и Grand Theft Auto, чтобы определить, какая часть кода проверяет лицензию. Они модифицируют двоичный код, помещая команду JUMP для прямого перехода в ту часть кода, которая выполнятся после проверки лицензии. Когда модифицированный двоичный файл выполняется, он добирается до введенной команды JUMP прежде, чем будет сделана проверка достоверности лицензии. Таким образом люди запускают незаконные пиратские копии программы, не платя за лицензию.

Исследователи и инженеры по безопасности, работающие на секретные правительственные структуры, также имеют лаборатории для изучения популярного потребительского программного обеспечения, такого как iOS, Microsoft Windows или Internet Explorer. Они идентифицируют потенциальные нарушения защиты в этих программах, чтобы обезопасить людей от кибератак или предотвратить взлом целей, имеющих большую ценность. Самой известной атакой такого рода был Stuxnet — кибероружие, созданное агентствами из США и Израиля. Оно замедлило ядерную программу Ирана, инфицировав компьютеры, которые управляли подземными термоядерными реакторами.

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

Не имея исходного кода, вы можете лишь слегка изменить двоичный код, но у вас не выйдет внести в программу какое-либо существенное изменение, например добавить новый функционал. Некоторые люди считают, что намного лучше разрабатывать программы сообща. Они оставляют свой код открытым для других людей, чтобы те могли вносить свои изменения. Главная идея здесь — создавать программное обеспечение, которое всякий может свободно использовать и модифицировать. Основанные на Linux операционные системы (такие как Ubuntu, Fedora и Debian) являются открытыми, тогда как Windows и Mac OS — закрытыми.

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

Надзор за ПО с открытым исходным кодом осуществляет куда больше глаз, поэтому лицам с дурными намерениями и правительственным учреждениям становится все труднее находить лазейки для слежки. Когда вы используете Mac OS или Windows, вам приходится доверять Microsoft или Apple, что они не поставят под угрозу вашу безопасность и приложат все усилия для предотвращения любого серьезного дефекта. А вот системы с открытым исходным кодом открыты для общественного контроля, потому в случае с ними меньше вероятность, что брешь в системе безопасности останется незамеченной.

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

Если доступ к памяти медленный, то ЦП приходится простаивать, ожидая, пока ОЗУ выполнит свою работу. Время, которое требуется, чтобы прочитать и записать данные в память, непосредственно отражается на производительности компьютера. Увеличение скорости памяти может разогнать ваш компьютер так же, как увеличение скорости ЦП. Данные в регистрах ЦП выбираются почти моментально самим процессором всего в одном цикле[80]. А вот ОЗУ гораздо медленнее.

Недавние технические разработки позволили экспоненциально увеличивать скорость ЦП. Быстродействие памяти тоже растет, но гораздо медленнее. Эта разница в производительности между ЦП и ОЗУ называется разрывом между памятью и процессором: команды ЦП «дешевы» — мы можем выполнять их в огромном количестве, тогда как получение данных из ОЗУ занимает намного больше времени и потому обходится «дорого». По мере увеличения этого разрыва возрастала важность эффективного доступа к памяти (рис. 7.10).

В современных компьютерах требуется приблизительно тысяча циклов ЦП, чтобы получить данные из ОЗУ, — около 1 микросекунды[81]. Это невероятно быстро, но составляет целую вечность по сравнению со временем доступа к регистрам ЦП. Программистам приходится искать способы сократить количество операций с ОЗУ.

Рис. 7.10. Разрыв в быстродействии между памятью и процессором в последние десятилетия

Пытаясь свести к минимуму количество обращений к ОЗУ, специалисты в области computer science стали замечать две закономерности, получившие следующие названия:

• временна́я локальность — если выполняется доступ к некоему адресу памяти, то вполне вероятно, что к нему вскоре обратятся снова;

• пространственная локальность — если выполняется доступ к адресу памяти, то вполне вероятно, что к смежным с ним адресам вскоре обратятся тоже.

Если исходить из вышеприведенных наблюдений, можно подумать, что хранить такие адреса памяти в регистрах ЦП — отличная идея. Это позволило бы избежать большинства дорогостоящих операций с ОЗУ. Однако отраслевые инженеры не нашли надежного способа разработать микросхемы ЦП с достаточным количеством внутренних регистров. И тем не менее они обнаружили отличный способ опереться на временную и пространственную локальность. Давайте посмотрим, как он работает.

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

При помощи кэша L1 мы можем копировать содержимое адресов памяти, причем скорость доступа с высокой вероятностью будет близка к скорости регистров ЦП. Данные очень быстро загружаются в регистры ЦП. Требуется где-то 10 циклов ЦП, чтобы переместить данные из кэша L1 в регистры. Это в сто раз быстрее ситуации, когда их приходится брать из ОЗУ.

Более половины обращений к ОЗУ можно выполнить за счет кэша L1 объемом 10 Кб и умного использования временной и пространственной локальности. Это новаторское решение привело к коренному изменению вычислительных технологий. Оборудование ЦП кэшем L1 позволило кардинально сократить время, которое процессору прежде приходилось тратить на ожидание данных. Вместо простоев он теперь занят выполнением фактических вычислений.

Можно было бы дальше увеличивать размер кэша L1 — выборка данных из ОЗУ тогда стала бы еще более редкой операцией, а время ожидания ЦП еще больше сократилось бы. Однако такое усовершенствование сопряжено с трудностями. Когда кэш L1 достигает размера около 50 Кб, его дальнейшее увеличение становится очень дорогостоящим. Куда лучшее решение состоит в том, чтобы сформировать дополнительный кэш памяти — кэш второго уровня, или кэш L2. Он будет медленнее, зато намного больше кэша L1 по объему. Современный ЦП имеет кэш L2 объемом около 200 Кб. Чтобы переместить данные из кэша L2 в регистры, требуется примерно 100 циклов процессора.

Рис. 7.11. Микрофотография процессора Intel Haskell-E. Квадратные структуры в центре — это кэш L3 объемом 20 Мб

Адреса, имеющие очень высокую вероятность доступа, мы копируем в кэш L1. Адреса с относительно высокой вероятностью — в кэш L2. Если адреса нет в кэше L1, процессор может попытаться найти его в кэше L2, и только если этот поиск закончится неудачей, ему придется обращаться к ОЗУ.

Многие производители теперь поставляют процессоры с кэшем L3: он больше и медленнее, чем L2, но по-прежнему быстрее ОЗУ. Кэши L1/L2/L3 имеют настолько важное значение, что занимают бо́льшую часть кремниевого пространства внутри микросхемы ЦП (рис. 7.11).

Использование кэшей L1/L2/L3 существенно увеличивает производительность компьютеров. Благодаря кэшу L2 емкостью 200 Кб менее 10 % запросов к памяти, которые делает ЦП, приходятся на выборку непосредственно из ОЗУ.

В следующий раз, когда вы пойдете покупать компьютер, не забудьте сравнить размеры кэшей L1/L2/L3 процессоров. Более хорошие ЦП будут иметь кэш большей емкости. Лучше взять ЦП с меньшей тактовой частотой, но с более объемным кэшем.

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

После регистров ЦП и кэшей в иерархии памяти находится ОЗУ. Она отвечает за хранение данных и кода всех выполняющихся процессов. По состоянию на 2017 год компьютер обычно имеет ОЗУ емкостью от 1 до 10 Гб. Во многих случаях этого недостаточно, чтобы разместить операционную систему со всеми другими выполняющимися программами.

Рис. 7.12. Диаграмма иерархии памяти

В этих случаях приходится спускаться ниже по иерархической лестнице и использовать жесткий диск. По состоянию на 2017 год компьютеры обычно имеют жесткие диски емкостью в сотни гигабайт — этого более чем достаточно, чтобы уместить данные из всех выполняющихся программ. Когда ОЗУ заполнено, мы перемещаем временно не используемые данные на жесткий диск, чтобы высвободить немного оперативной памяти.

Но проблема в том, что жесткие диски работают чрезвычайно медленно. Как правило, на перемещение данных между диском и ОЗУ требуется миллион циклов ЦП — целая миллисекунда[82]. Может показаться, что это все равно быстро, но не забывайте: в то время как доступ к ОЗУ занимает всего 1000 циклов, на доступ к диску их уходит миллион. ОЗУ нередко носит название первичной памяти, а программы и данные, хранящиеся на жестком диске, являются вторичной памятью.

ЦП не может обращаться к вторичной памяти напрямую. Программы, которые хранятся во вторичной памяти, нужно скопировать в первичную — только тогда они будут исполнены. В действительности всякий раз, когда вы загружаете компьютер, даже операционную систему приходится копировать с диска в ОЗУ, прежде чем ЦП сможет ее выполнить.

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

Когда компьютер постоянно перемещает данные с диска в ОЗУ, мы говорим, что он вошел в режим интенсивной подкачки. Эту ситуацию необходимо постоянно отслеживать — особенно в случае с серверами: если они начинают обрабатывать данные, не умещающиеся в ОЗУ, такой режим работы может вывести их из строя. Следствием этого, например, становится длинная очередь в банке или у кассового аппарата, — и оператору ничего не останется, кроме как валить все на сбой компьютерной системы. Недостаточный объем ОЗУ, возможно, является одной из главных причин отказа серверов.

Спустимся еще ниже по иерархической лестнице памяти. Если компьютер подключить к локальной или Глобальной сети, он может получить доступ к памяти, управляемой другими компьютерами. Но этот процесс требует еще больше времени: если на чтение локального диска уходит миллисекунда, то получение данных из сети может занимать сотни миллисекунд. Только на то, чтобы сетевой пакет переместился с одного компьютера на другой, требуется порядка десяти миллисекунд. Если сетевой пакет проходит через Интернет, то он часто движется намного дольше, от двухсот до трехсот миллисекунд — столько времени у нас уходит, чтобы моргнуть .

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

Технология, используемая в быстродействующих устройствах памяти (которые находятся в верхней части иерархической лестницы), с большим трудом поддается качественному улучшению. С другой стороны, «медленные» устройства памяти становятся быстрее и дешевле. Стоимость хранения данных на жестком диске десятилетиями падала, и, по всей видимости, эта тенденция будет продолжаться (рис. 7.13).

Кроме того, новые технологии приводят к ускорению дисков. Мы переключаемся с магнитных вращающихся дисков на твердотельные (SSD). Отсутствие подвижных частей делает их быстрее, надежнее и менее затратными в энергетическом плане.

SSD-диски становятся дешевле и быстрее каждый день, но они по-прежнему стоят дорого. Некоторые производители выпускают гибридные диски, сочетающие технологии SSD и магнитных дисков. Данные, к которым приходится обращаться часто, хранятся в SSD, а те, что бывают нужны реже, — в более медленном магнитном разделе. Когда последние начинают запрашиваться часто, они копируются в SSD-раздел гибридного диска — точно так же, как в случае с ОЗУ и кэшами в процессоре.

Рис. 7.13. Стоимость дисковой памяти в расчете на гигабайт объема

Языки программирования очень сильно отличаются, но все они были созданы, чтобы делать одно: управлять информацией. С этой целью все они опираются на три основных структурных элемента. Значение представляет информацию. Выражение производит значение. Инструкция использует значение, чтобы дать команду компьютеру.

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

Значения настолько важны, что их также называют объектами первого класса языка программирования. Языки допускают разнообразные виды операций со значениями: они могут создаваться во время выполнения функции, могут передаваться как параметры, возвращаться ею.

Вы можете создать значение двумя способами: написав литерал либо вызвав функцию. Вот пример выражения с литералом:

3

Бум! Мы буквально только что создали значение 3, написав: «3». Довольно прямолинейно. Как литералы можно создавать и другие типы значений. Большинство языков программирования позволит вам создать строковое значение Привет мир, набрав на клавиатуре «Привет мир». Функции же генерируют значение согласно методу или процедуре, которые запрограммированы в каком-то другом месте. Например:

getPacificTime()

Это выражение создало значение, равное текущему времени в Лос-Анджелесе. Если сейчас 4 часа утра, то метод вернет 4.

Еще одним базовым элементом любого языка программирования является оператор. Оператор может объединять простые выражения для формирования более сложных. Например, оператор + позволяет создать значение, равное времени в Нью-Йорке:

Когда в Лос-Анджелесе 4 часа утра, наше выражение сведется к 7. В действительности выражение — это любая запись, которую компьютер сможет свести к единственному значению. Большие выражения могут сочетаться с другими выражениями посредством операторов, формируя еще более крупные выражения. В конечном счете даже самое сложное выражение всегда будет вычислено и сведено к единственному значению.

Наряду с литералами, операторами и функциями выражения могут также содержать круглые скобки. Они позволяют управлять порядком выполнения операторов: (2 + 4)² сводится к 6², которое, в свою очередь, сводится к 36. Выражение 2 + 4² сводится к 2 + 16, а затем к 18.

В то время как выражение представляет значение, инструкция используется, чтобы дать компьютеру команду сделать что-то. Например, эта инструкция заставит его показать сообщение:

print("привет мир").

Рис. 8.1.[84]

Более сложные примеры включают условная инструкция if, инструкции циклов while и for. Разные языки программирования поддерживают разные типы инструкций.

Определения. Некоторые языки программирования имеют специальные инструкции, именуемые определениями. Они изменяют состояние программы, добавляя не существовавшие ранее объекты, такие как новые значения или функции[85]. Чтобы обратиться к объекту, который мы определили, мы должны назвать его. Этот процесс называется привязкой имен. Например, имя getPacificTime должно быть привязано к определению функции, заданному где-то в другом месте.

Переменные — это самая важная привязка имен: она устанавливает отношения между именами и значениями. Переменная связывает имя с адресом памяти, где значение хранится, и, таким образом, выступает в качестве его псевдонима. Чаще всего переменная создается при помощи оператора присваивания. В псевдокоде этой книги присвоения обозначаются символом ←:

pi ← 3.142

В большинстве языков программирования присвоения записываются при помощи символа =. Некоторые языки даже требуют, чтобы вы объявляли имя как переменную, перед тем как она будет определена. В итоге у вас получится нечто вроде этого:

var pi

pi = 3.142

Эта инструкция резервирует блок памяти, записывает в него значение 3,142 и привязывает имя "pi" к адресу блока памяти.

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

Существуют два способа проверки типа: статический и динамический. Статическая проверка требует, чтобы разработчик кода объявлял тип каждой переменной перед ее использованием. Например, языки программирования вроде C и C++ вынуждают нас писать:

float pi;

pi = 3.142;

Такое объявление сообщает, что переменная с именем pi может хранить только данные, представляющие числа с плавающей точкой. Статически типизированные языки могут применять дополнительную оптимизацию во время компиляции кода и обнаруживать потенциальные ошибки еще до первого запуска программы. Однако объявление типов для всех переменных может быстро наскучить.

Некоторые языки предпочитают проверять типы динамически. Благодаря такой проверке любая переменная может хранить любой тип значения, и потому объявление типа не требуется. Однако во время выполнения кода производится дополнительная проверка типов переменных, чтобы гарантировать, что все операции между ними имеют смысл.

Если бы все привязки имен были доступны и допустимы во всех точках в коде, то программирование считалось бы чрезвычайно трудным процессом. По мере того как программы становятся больше, одинаковые имена переменных (такие как time, length либо speed) все чаще начинают использоваться в разных частях программного кода.

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

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

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

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

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

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

В программировании, как и в физике, подходы к решению задач полностью меняются в зависимости от парадигмы. Парадигма программирования — это определенная точка зрения на стиль программирования и методику.

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

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

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

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

Рис. 8.2. Типичная задача[86]

Императивное программирование — это, безусловно, самая известная парадигма. По сути, многие программисты знакомы только с ней. Она также является естественным отражением способа, которым работают люди: мы используем эту парадигму для описания кулинарного рецепта, плана ремонта и других повседневных процедур. Когда нам лень выполнять скучную работу, мы переносим инструкции в программу, и компьютер выполняет их за нас. Программистская лень серьезно помогла прогрессу.

Программирование машинного кода. Первым программистам приходилось вводить код в компьютер вручную, используя единицы и нули, но они тоже были ленивы. Они решили, что будет намного лучше записывать последовательность команд ЦП при помощи мнемоник, таких как CP для команды «копировать», MOV для команды «переместить», CMP для команды «сравнить» и т. п. Затем они написали программу, преобразующую мнемонический код в соответствующие ему двоичные числа процессорного кода. Так родился язык ассемблера (или ASM).

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

ASM используется, например, для программирования микроволновых печей или компьютерных систем в автомобиле. Этот язык также идеален для создания частей программы, где необходима предельная производительность и имеет значение экономия даже нескольких циклов ЦП.

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

Структурное программирование. Когда-то давно программисты использовали команду GOTO для управления потоком выполнения. Она заставляет процесс перепрыгивать в другую часть кода. По мере того как программы усложнялись, стало почти невозможно понимать, что она делает. Различные потоки выполнения переплетались с командами GOTO и JUMP, создавая то, что называется запутанным кодом или спагетти-кодом[87]. В 1968 году Дейкстра написал свой знаменитый манифест «О вреде оператора GOTO», и это вызвало революцию. Программный код стали разделять на логические части. Вместо ситуативных GOTO программисты начали использовать управляющие структуры (if, else, while, for). Это позволило намного упростить написание и отладку программ.

Процедурное программирование. Следующим шагом в искусстве программирования стало процедурное программирование. Оно позволяет организовать код в процедуры, избежать повторов и сделать более удобным его многократное использование. Например, вы можете создать функцию, преобразующую единицы метрической системы мер в единицы британской системы, принятые в США, а затем вызывать свою функцию, многократно используя один и тот же код, когда это потребуется. Процедуры усовершенствовали структурное программирование еще больше. Их использование сильно упростило разбиение связанных кусков программного кода на группы.

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

Функциональное программирование. В парадигме функционального программирования функции — это больше, чем просто процедуры. Они используются для объявления связи между двумя или более элементами, почти как математические уравнения. В функциональной парадигме первоклассными объектами являются функции. Они обрабатываются так же, как любой другой примитивный тип данных, например строки и числа.

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

Например, большинство языков функционального программирования поставляются вместе с универсальной функцией sort. Она может сортировать любую последовательность элементов. Функция sort на входе принимает другую функцию, которая определяет, как элементы будут сравниваться в процессе сортировки. Например, переменная coordinates содержит список географических точек. При наличии двух точек функция closer_to_home сообщает, какая из них находится ближе к вашему дому. Вы можете отсортировать список точек по критерию близости к вашему дому, как это сделано тут:

sort(coordinates, closer_to_home)

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

odd_numbers ← filter(numbers, number_is_odd)

number_is_odd — это функция, которая получает число и возвращает True, если число является нечетным, и False в противном случае.

Еще одна типичная задача, которая возникает во время программирования, — применение специальной функции ко всем элементам в списке. В функциональном программировании она называется отображением. Многие языки имеют встроенную функцию map, предназначенную для этой задачи. Например, вычисление квадрата каждого числа в списке можно организовать так:

squared_numbers ← map(numbers, square)

Функция square возвращает квадрат заданного числа. Операции отображения и фильтрации встречаются так часто, что многие языки программирования предлагают возможность записи этих выражений в более простой форме. Например, в языке программирования Python вычислить квадраты чисел в списке можно так:

squared_numbers = [x**2 for x in numbers]

Эта форма записи называется «синтаксическим сахаром»: дополнительной синтаксической конструкцией, позволяющей записывать выражения короче и понятнее. Многие языки программирования предоставляют несколько форм «синтаксического сахара». Применяйте их и злоупотребляйте ими.

Наконец, когда нужно обработать список значений так, чтобы свести процесс к единственному результату, вы можете воспользоваться функцией reduce. На входе она получает список, начальное значение и редуцирующую функцию. Начальное значение инициирует «аккумуляторную» переменную, которая будет обновляться редуцирующей функцией для каждого элемента в списке, а в конце — возвращена:

function reduce(list, initial_val, func)

····accumulator ← initial_val

····for item in list

········accumulator ← func(accumulator, item)

····return accumulator

Например, с помощью reduce можно просуммировать элементы в списке:

sum ← function(a, b): a + b

summed_numbers ← reduce(numbers, 0, sum)

Использование функции reduce упростит ваш программный код и сделает его более читаемым. Еще пример: если sentences — это просто список предложений, и вы хотите подсчитать общее количество слов в них, это можно реализовать так:

wsum ← function(a, b): a + length(split(b))

number_of_words ← reduce(sentences, 0, wsum)

Функция split разбивает строку на список слов, а функция length подсчитывает количество элементов в списке.

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

Используя замыкания, можно разбить исполнение функции, принимающей множество аргументов, на несколько шагов. Это называется каррингом. Предположим, что ваш программный код имеет такую функцию sum:

sum ← function(a, b): a + b

Функция sum ожидает два параметра, но ее можно вызвать с одним аргументом. Выражение sum(3) вернет не число, а новую каррированную функцию. При обращении к ней она вызовет sum и передаст ей 3 в первом аргументе. Ссылка на значение 3 замыкается в каррированной функции. Например:

sum_three ← sum(3)

print sum_three(1) # печатает "4".

Всегда, когда вашей задачей является решение ряда логических формул, вы можете воспользоваться логическим программированием. Разработчик перечисляет логические высказывания о ситуации, например такие, как в разделе «Логика» главы 1. Затем выполняются запросы, чтобы получить ответы из предоставленной модели. Компьютер отвечает за интерпретацию логических переменных и запросов. Он также создает пространство решений из высказываний и занимается поиском ответов на запросы, которые удовлетворяют всем этим высказываниям.

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

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