Программное обеспечение
Хорошая новость: компьютер – это машина общего назначения, способная выполнять любые вычисления. Хотя у него есть только несколько типов инструкций, он может прогонять их очень быстро и в значительной степени контролировать свою работу.
Плохая новость: сам он не предпринимает никаких действий, пока кто-то ему не скажет, что делать, при этом в мучительно мелких подробностях. Компьютер – настоящий «ученик чародея», способный неустанно и безошибочно следовать инструкциям, но требующий со скрупулезной точностью описывать ему, что делать.
Программное обеспечение – это общий термин, обозначающий последовательности инструкций, которые заставляют компьютер выполнять что-то полезное. Слово soft (англ, software – программное обеспечение) противоположно по смыслу слову hard[25] (англ, hardware – аппаратное обеспечение), потому что ПО неосязаемо, к нему сложно прикоснуться. «Железо» осязаемо: если вы уроните ноутбук себе на ногу, то ощутите это. Но для «софта» такую ситуацию представить невозможно.
В следующих нескольких главах мы будем говорить о ПО, то есть о средстве указать компьютеру, что нужно сделать. В главе 4 мы обсудим теорию программных средств с упором на алгоритмы – по сути, схематические программы для решения узких задач. В главе 5 мы поговорим о программировании и его языках (ЯП): мы применяем их, чтобы задавать последовательности вычислительных операций. В главе 6 описываются основные виды программных систем, которыми мы пользуемся, порой даже не зная о них. В последней части данного раздела, главе 7, вы кратко познакомитесь с двумя наиболее популярными на сегодня ЯП – JavaScript и Python.
В ходе чтения стоит помнить кое о чем. Современные технологические системы все более обширно задействуют оборудование общего назначения (процессоры, память, средства коммуникации с окружающей средой), а определенное поведение создают с помощью программных средств. Вот вам прописная истина: по сравнению с оборудованием, ПО более дешево и приспособляемо, а также его легче изменить, особенно когда устройство уже покинуло завод. Например, если в машине подачей мощности и торможением управляет компьютер (встроенная система), очевидно, что различные функции вроде антиблокировки тормозов и электронного контроля устойчивости реализуются на программном уровне.
Поезда, корабли и самолеты также все больше зависят от ПО. К сожалению, с помощью программных средств не всегда просто изменить поведение оборудования.
После того как в октябре 2018 года и марте 2019 года разбились два «Боинга-737 МАХ», что привело к гибели 346 человек, в новостях часто обсуждали программное обеспечение для самолетов. Компания Boeing начала производство серии 737 в 1967 году, и с годами машины постоянно совершенствовались. Самолеты модели 737 МАХ, выпущенные в 2017 году, представляли собой обширную модификацию оригинала с более объемными и экономичными двигателями.
Вследствие такого обновления машины приобрели существенно иные летные характеристики. Вместо того чтобы модифицировать аэродинамические параметры и обеспечить тем самым поведение самолета, близкое к ранним версиям, инженеры Boeing разработали программную систему автоматического контроля полета под названием Maneuvering Characteristics Augmentation System[26], или MCAS. Ее задача состояла в том, чтобы МАХ летал так же, как и другие модели серии 737, ведь тогда удалось бы избежать крупных затрат на повторную сертификацию и переобучение пилотов. В каком-то смысле ПО сделало бы новый самолет неотличимым от старого.
Говоря простым языком, из-за более тяжелых двигателей, к тому же перемещенных в другое положение, у МАХ поменялись летные характеристики. При определенных обстоятельствах, когда программа MCAS считала, что нос самолета находится слишком высоко, она интерпретировала это как возможное сваливание и опускала нос. Ее решение основывалось на показаниях одного (возможно, неисправного) входного датчика, хотя на «Боинге» их стояло два. Когда пилоты пытались поднять нос, программа отменяла эту команду. В результате самолет раскачивался вверх и вниз, что неизбежно приводило к авиакатастрофам. Что еще хуже, Boeing не уведомляла о существовании MCAS, поэтому пилоты даже не знали о возможной проблеме. Их не обучали тому, как ее устранить36.
Вскоре после второго крушения авиационные органы власти по всему миру приостановили эксплуатацию самолета МАХ. Репутация Boeing серьезно пострадала, а убытки компании оценивались в более чем 20 миллиардов долларов. В конце ноября 2020 года Федеральное управление гражданской авиации США снова разрешило полеты на МАХ, так как в подготовку пилотов и в саму машину внесли изменения. Впрочем, неясно, когда эти самолеты снова будут регулярно подниматься в воздух.
Компьютеры занимают центральное место в критически важных системах, а ПО управляет ими. Беспилотные автомобили (или обычные помощники, встроенные в современные машины) находятся под контролем программного обеспечения. Вот простой пример: в моей машине Subaru Forester установлены две камеры, которые смотрят наружу через лобовое стекло. Благодаря компьютерному зрению автомобиль предупредит меня, если я перестроюсь, не включив поворотники, или если в опасной близости окажутся машина или человек. Нередко эта информация ошибочна, и частые ложные срабатывания больше отвлекают, чем помогают, но несколько раз данная функция выручала меня.
В медицинских системах визуализации тоже применяются компьютеры: они управляют сигналом и формируют изображения, которые анализируют врачи, так что цифровые картинки вытеснили пленочные снимки. Схожая ситуация теперь и в таких областях инфраструктуры, как система управления воздушным движением, навигационные средства, электрические и телефонные сети. Но в вычислительных устройствах для голосования нашли серьезные недостатки. Так, в начале 2020 года подсчет голосов на предварительных выборах Демократической партии в Айове сорвался из-за неполадок с компьютерной системой, и для устранения ошибки понадобилось несколько дней37. Идея интернет-голосования стала популярной во время пандемии COVID-19, но она несет в себе рисков больше, чем осознают сотрудники избирательных комиссий. Очень сложно разработать систему, которая надежно даст людям сделать выбор, сохранив при этом тайну голосования38.
Военные системы полностью зависят от компьютеров как по части вооружений, так и в аспекте снабжения. То же самое относится и к финансовым системам по всему миру. Кибервойна и шпионаж – это реальные угрозы. Например, червь Stuxnet 2010 года разрушил иранские центрифуги по обогащению урана. Крупное отключение электроэнергии на территории Украины в декабре 2015 года было вызвано российской вредоносной программой, хотя правительство РФ отрицает свою причастность39. Два года назад (в 2018-м) произошла вторая серия атак с использованием программы-вымогателя Petya, которая повлияла на работу различных украинских организаций. Когда атака программы-вымогателя WannaCry нанесла ущерб в миллиарды долларов по всему миру, правительство США официально возложило ответственность на Северную Корею40. В июле 2020 года несколько стран обвинили российскую группу кибершпионажа в попытке украсть сведения о разрабатываемых вакцинах против COVID-1941.
Нападениям, как криминальным, так и поддерживаемым государством, вполне могут подвергнуться самые разнообразные цели. Если наше ПО недостаточно устойчиво и надежно, то у нас проблемы, а по мере роста зависимости от компьютеров ситуация будет только усугубляться. Как мы увидим далее, сложно написать «софт», который совершенно надежен. Любая ошибка или недосмотр в логике или реализации способны привести к сбоям в работе программы, и даже если их не происходит при обычном использовании, возможно, что возникшая лазейка пригодится злоумышленникам.
4Алгоритмы
Алгоритм Фейнмана42:
1. Запишите проблему.
2. Подумайте над ней как следует.
3. Запишите решение.
Когда люди хотят объяснить, что такое программное обеспечение, то часто сравнивают его с кулинарным рецептом. В поваренных книгах описываются ингредиенты, последовательность действий, которые нужно выполнить, и ожидаемый результат. По аналогии, в программе для решения какой-либо задачи необходимо указать данные и прописать, что с ними делать. Правда, в реальности советы кулинарам настолько расплывчатые и неопределенные, что никакую программу при всем желании так не составить, поэтому аналогия не слишком удачна. Например, в рецепте шоколадного торта сказано: «Выпекайте в духовке 30 минут или до затвердевания. Проверьте, аккуратно положив ладонь на поверхность»43. На что повар должен обратить внимание – на колебание, упругость или что-то еще? «Аккуратно» – это как именно? Выпекать нужно не больше или не меньше 30 минут?
Более удачная метафора – бланки налоговых деклараций, так как в них описывается множество подробностей того, что нужно сделать («Вычтите строку 30 из строки 29. Если получилось ноль или меньше, укажите 0. Умножьте строку 31 на 0,25…»). Аналогия все еще не совершенна, но тут намного лучше, чем в варианте с рецептами, отражаются вычислительные аспекты. Здесь проводятся арифметические операции, значения данных копируются из одного места в другое, проверяются условия, последующие расчеты зависят от результатов предыдущих.
Также важно, что при заполнении форм процесс должен дойти до конца, то есть у вас в любом случае обязан получиться результат – сумма причитающегося налога. Он должен четко определяться правилами: все люди, которые вводят одни и те же исходные данные, должны получить одинаковый итог. И расчеты должны завершиться через конечный промежуток времени. Исходя из моего личного опыта, это все идеализация, потому что терминология не всегда понятна, инструкции более туманны, чем кажется налоговой инспекции, и зачастую непонятно, какие значения данных следует использовать.
Алгоритм — это компьютерная версия тщательно составленного, точного и недвусмысленного рецепта или налоговой формы. По сути, последовательность шагов, которые гарантируют правильное вычисление результата. Каждый этап описывается в терминах базовых операций, значение которых четко определено: например, «сложить два целых числа». Нет никаких расплывчатых терминов. Указан характер входных данных. Рассмотрены все возможные ситуации: никогда не бывает такого, что при работе с алгоритма становится непонятно, какие действия производить дальше. Если специалисты по информатике склонны к педантизму, то обычно добавляют еще одно условие: алгоритм не может выполняться бесконечно. Согласно такому стандарту, классическая инструкция к шампуню «намылить, смыть, повторить»[27] – это не алгоритм.
На разработке, анализе и внедрении эффективных алгоритмов зиждется академическая информатика. Кроме того, в реальном мире существуют алгоритмы, имеющие огромное значение. Я вовсе не собираюсь точно объяснять или описывать алгоритмы, но хочу донести до вас, что речь идет о последовательностях операций, заданных достаточно подробно и точно. Настолько, чтобы не возникло сомнений в том, какие действия имелись в виду и как их выполнять, даже если совершает их сущность без интеллекта и воображения. Мы также обсудим алгоритмическую эффективность – то, как время вычислений зависит от объема обрабатываемых данных. В качестве примеров мы возьмем несколько базовых алгоритмов, которые хорошо известны и понятны.
В этой главе вам не обязательно вникать во все подробности или иногда всплывающие формулы, но изложенные здесь принципы важны.
4.1. Линейные алгоритмы
Предположим, мы хотим выяснить, кто самый высокий человек в помещении. Люди могут просто осмотреться и прикинуть, но алгоритм должен прописать все шаги настолько точно, чтобы даже глупый компьютер сумел им следовать.
Простейший метод – поочередно узнать рост всех присутствующих, отмечая, кто самый высокий на текущий момент. То есть мы по очереди спрашиваем каждого человека: «Джон, какой у тебя рост? Мэри, какой у тебя рост?» – и так далее. Если Джон – первый из опрошенных, то пока он будет самым высоким. Если Мэри выше, то теперь она будет самой высокой, в противном случае Джон сохранит лидерство. Дальше мы спросим третьего человека и т. д.
В конце, опросив всех людей, мы узнаем, кто самый высокий и какой у него рост. Если внести вполне очевидные вариации, то тем же способом мы определим, кто из присутствующих самый богатый, чье имя идет первым по алфавиту или чей день рождения ближе всего к концу года.
Но тут есть сложности. Как мы справимся с повторами – например, если окажется, что у двух людей одинаковый рост? Придется выбирать, кого указывать в результате: первого, второго, обоих или определить случайным образом.
Заметьте, что поиск большой группы людей с одинаковым ростом – еще более сложная проблема, так как от нас потребуется непрерывно помнить имена всех, кто соответствует условию, и до самого конца опроса мы не будем знать, кто попадет в финальный список. Этот пример подразумевает использование структуры данных, то есть способа представления информации, необходимой для вычисления. Такой фактор важен для многих алгоритмов, хотя здесь мы не будем подробно обсуждать данную тему.
А что, если мы захотим вычислить средний рост? Можно узнавать у каждого человека его или ее рост, складывать получаемые значения по мере их поступления (возможно, используя программу Игрушки для суммирования последовательности чисел) и потом разделить итог на количество опрошенных. Если у нас на листочке записано N значений роста, то, выразив процесс расчета более «алгоритмически», мы получим:
Однако если мы попросим компьютер выполнить эту работу, надо будет проявить внимательность. Что произойдет, например, если на листочке нет никаких чисел? Если расчеты ведет человек, то это не проблема: нам понятно, что пока вычислять нечего. Компьютеру же нужно сказать, чтобы он проверил, не возникла ли такая ситуация, и описать ему порядок действий на такой случай. Если машина не проведет проверку, то будет пытаться разделить сумму на ноль, а это неопределенная операция. Алгоритмы и компьютеры обязаны обрабатывать все возможные ситуации. Если вы когда-нибудь получали чек на «О долларов и 00 центов» или счет, где к оплате указана сумма, равная нулю, то сталкивались с примером того, что кто-то не учел все вероятные случаи должным образом.
Что, если мы не знаем заранее, сколько будет элементов данных, как чаще всего и бывает? Можно подсчитывать элементы по мере вычисления суммы:
Как видите, в конце добавлено условие отсутствия записей, при соблюдении которого машина сообщает, что значения роста не введены. Это один из способов решения проблемы с возможным делением на ноль – целевая проверка, не возникло ли такое «неудачное» состояние.
Один из важнейших параметров алгоритма – эффективность его работы: быстрый он или медленный, сколько времени ему понадобится для обработки определенного количества данных. В приведенных выше примерах количество шагов для выполнения задачи (или время, которое понадобится для этого компьютеру) прямо пропорционально объему поступающей информации. Если в комнате соберется вдвое больше людей, то компьютер будет в два раза дольше определять самого высокого человека или средний рост, а если вдесятеро больше – то в десять раз. Когда время вычисления прямо или линейно пропорционально количеству данных, алгоритм называется линейно-временным или просто линейным. Если бы мы построили график зависимости срока обработки от количества элементов данных, то у нас получилась бы прямая линия, направленная вверх и вправо. Многие алгоритмы, с которыми мы сталкиваемся в повседневной жизни, линейные, поскольку они предполагают выполнение одной и той же базовой операции или операций над какой-либо информацией. И чем больше данных, тем больше работы (в прямо пропорциональной зависимости).
Многие линейные алгоритмы принимают одну и ту же базовую форму. В них есть некий этап инициализации – например, текущую сумму устанавливают равной 0 или задают для «самого высокого роста» какое-либо малое значение. Затем проверяется каждый элемент по очереди, и с ним производятся те или иные простые вычисления: его учитывают, сравнивают с предыдущим значением, элементарно преобразовывают, возможно, печатают. В конце могут потребоваться некоторые шаги для завершения работы – например, вычисление среднего значения, вывод суммы или самого высокого роста. Если операция с каждым элементом занимает примерно одинаковое время, то общий срок будет пропорционален количеству элементов.
4.2. Двоичный поиск
Есть ли что-то лучше линейного поиска? Предположим, у нас имеется несколько имен и телефонных номеров в распечатанном списке или стопка визитных карточек. Если мы хотим найти номер Майка Смита, но имена расположены беспорядочно, то нам нужно просматривать все визитки подряд, пока не отыщется нужная. А возможно, такой карточки там вообще нет. Если же имена стоят в алфавитном порядке, то совсем другое дело.
Представьте, что мы ищем имя в бумажной телефонной книге, ныне устаревшей. Мы начинаем с середины. Если интересующее нас имя идет по алфавиту раньше, чем имена на страницах в середине, то мы можем вообще не заглядывать во вторую половину справочника и пере-листнуть к середине первой половины (то есть к первой четверти от начала книги). В ином случае мы игнорируем первую половину справочника и проверяем середину последней части книги (то есть третью четверть от начала). И так далее. Поскольку имена приведены в алфавитном порядке, то на каждом шаге нам будет известно, какую половину оставшихся страниц нужно просматривать. В итоге мы или найдем искомое имя, или убедимся, что его нет в справочнике.
Данный алгоритм поиска называется двоичным поиском, потому что при каждой проверке или сравнении элементы разбиваются на две группы, одну из которых можно исключить из дальнейшего рассмотрения. Это пример более общей стратегии, называемой «разделяй и властвуй». Насколько быстр такой алгоритм? На каждом шаге мы исключаем половину оставшихся элементов, поэтому количество шагов равняется тому, сколько раз нужно разделить первоначальный объем на 2, чтобы получить один элемент.
Допустим, мы начали с 1024 имен (я выбрал это число, потому что так проще считать). При первом сравнении мы исключаем 512 имен. На втором шаге объем уменьшается до 256, затем до 128, далее до 64, 32, 16, 8, 4, 2 и, наконец, до 1. Итого получается 10 сравнений. Очевидно, это не совпадение, что 210 равно 1024. Количество сравнений – это степень двойки, что возвращает нас к исходному числу: идя в обратном направлении, мы каждый раз умножаем на 2 и получаем последовательность 1, 2, 4… 1024.
Если у вас сохранился в памяти школьный курс логарифмов (как ни поразительно, большинство их забывают!), возможно, вы вспомните, что логарифм числа – это степень, в которую надо возвести основание (в данном случае 2), чтобы получить само число. Таким образом, логарифм по основанию 2 для 1024 равен 10, поскольку 210 = 1024. В нашем случае можно считать логарифмом количество делений числа на 2, необходимых, чтобы получить 1, – или, что эквивалентно, количество умножений на 2 до получения искомого числа. В книге будут использоваться только логарифмы по основанию 2. Нам не нужна точность или дроби: приблизительных чисел и целых значений вполне достаточно в рамках наших упрощений.
Важно, что при использовании двоичного поиска объем выполняемой работы медленно увеличивается с ростом количества данных. Если у нас есть 1000 имен в алфавитном порядке, нам нужно просмотреть 10 имен, чтобы найти искомое. Если имен насчитывается 2000, то мы должны просмотреть 11 имен, так как на первом же шаге будет исключена тысяча из них и мы вернемся к проверке 1000 оставшихся (на что нужно 10 шагов). Миллион имен – это 1000 раз по 1000. После первых 10 проверок мы возвращаемся к 1000, а после еще 10 приходим к 1 имени, то есть в сумме требуется всего 20 шагов. Миллион – это 106, что близко к 220, поэтому логарифм 1 000 000 по основанию 2 составляет около 20.
Отсюда вам уже наверняка очевидно, что при поиске имени в каталоге с миллиардом записей (телефонной книге почти всей Земли) вам пришлось бы провести лишь 30 сравнений, поскольку миллиард – это примерно 230. Вот почему можно утверждать, что объем работы растет медленно по сравнению с увеличением количества информации: если данных становится в тысячу раз больше, требуется всего 10 дополнительных шагов.
Чтобы быстро подтвердить это на практике, я однажды решил найти моего друга Гарри Льюиса в старом телефонном справочнике Гарварда, который тогда содержал около 20 000 имен на 224 страницах. (Разумеется, бумажные телефонные книги давно исчезли, поэтому сегодня я не смогу повторить эксперимент.) Тогда я начал со страницы 112 и увидел фамилию Лоуренс. Значит, Льюис встречается позже, во второй половине. Поэтому на следующем шаге я открыл страницу 168, расположенную посередине между 112 и 224, и мне встретилось Ривера. «Льюис» находится перед этой фамилией, поэтому я перелистнул на 140-ю страницу (середина между 112 и 168) и нашел фамилию Морита. Далее я перешел к 126-й (посередине между 112 и 140) и фамилии Марк. Следующая проверка привела меня на страницу 119 (Литтл), затем 115 (Лейтнер), затем 117 (Ли)[28], и в итоге я остановился на 116-й.
На этой странице находилось около 90 фамилий, и после еще 7 сравнений (уже не переходя со 116-й) я отыскал Гарри среди дюжины других Льюисов. Всего в ходе эксперимента потребовалось 14 шагов, что примерно соответствует ожиданиям, поскольку 20 000 находятся между 214 (16 384) и 215 (32 768).
В повседневной жизни этот вид двоичного деления используется в круговых турнирах на выбывание. Вначале в соревновании участвует много спортсменов – например, 128 в мужском одиночном разряде на Уимблдоне. В каждом раунде вылетает половина участников, и в последнем матче сходятся два игрока, которые определяют между собой одного победителя. Уимблдон не случайно состоит из семи кругов, ведь 128 – это степень двойки (27). Если вообразить всемирный турнир на выбывание, то для того, чтобы выявить победителя даже среди семи миллиардов участников, нам понадобилось бы провести всего 33 раунда. Если вы помните обсуждение степеней 2 и 10 в главе 2, то сможете проверить результат с помощью простых расчетов в уме.
4.3. Сортировка
Но как нам с самого начала расположить имена в алфавитном порядке? Без такого предварительного шага мы не сможем провести двоичный поиск. Это подводит нас к еще одной фундаментальной проблеме теории алгоритмов – сортировке, то есть расположению элементов в определенном порядке, что существенно ускоряет поиск.
Предположим, что мы хотим отсортировать какое-то количество имен по алфавиту, чтобы затем быстро находить нужные с помощью двоичного поиска. Есть алгоритм под названием «сортировка методом выбора», в ходе которого мы выбираем еще не отсортированные элементы один за другим. Он основан на методе, ранее использованном нами для поиска самого высокого человека в комнате.
Для наглядности давайте возьмем 16 знакомых названий и расположим их в алфавитном порядке.
Intel Firefox Zillow Yahoo Pinterest Twitter Verizon Bing Apple Google Microsoft Sony PayPal Skype IBM Ebay
Пойдем слева направо. Intel стоит первым, так что пока оно будет первым и в алфавитном порядке. Сравним его со следующим названием – Firefox. F по алфавиту идет раньше I, так что это слово временно становится первым. Zillow не стоит перед Firefox, как и другие названия вплоть до Bing, которое забирается на первое место, но затем его сразу же сменяет Apple. Мы проверим и остальные названия, но ни одно из них не стоит перед Apple, так что оно сохраняет лидерство по алфавиту. Передвинем его в начало, а прочие названия оставим на прежних местах. Теперь список выглядит так:
Apple
_________
Intel Firefox Zillow Yahoo Pinterest Twitter Verizon Bing Apple Google Microsoft Sony PayPal Skype IBM Ebay
Теперь мы повторим процесс и найдем второе по алфавиту название, начиная с Intel, которое стоит первым в неотсортированной группе. Снова его сместит Firefox, а затем первым станет Bing. После завершения второго прохода мы получим такой результат:
Apple Bing
____________
Intel Firefox Zillow Yahoo Pinterest Twitter Verizon Google Microsoft Sony PayPal Skype IBM Ebay
Выполнив данный алгоритм еще 14 раз, мы получим полностью отсортированный список.
Какой объем работы здесь пришлось выполнить? На каждом проходе алгоритм перебирает оставшиеся элементы и всякий раз находит следующее по алфавиту название. Когда их было 16, для того чтобы найти первое, понадобилось просмотреть все. Поиск второго названия занял 15 шагов, поиск третьего – 14 и так далее. В итоге мы должны проверить 16 + 15 +14+…+3 + 2+1 названий, всего 136. Конечно, «умный» алгоритм сортировки мог бы обнаружить, что названия уже стоят в определенном порядке, но специалисты по информатике, которые изучают алгоритмы, довольно пессимистичны: они рассматривают худший вариант, когда срезать углы нельзя и надо проделать всю работу целиком.
Количество проходов по названиям прямо пропорционально их изначальному количеству (16 в нашем примере или N в общем случае). В каждом последующем проходе алгоритм обрабатывает на один элемент меньше, поэтому объем работы в общем случае равен:
N + (N– l) + (N-2) + (N-3) +… + 2+ 1
Этот ряд сумм можно выразить так: N × (N + 1)/2 (что легко увидеть, если складывать числа попарно, по одному с каждого конца) или N2/2 + N И. Если опустить деление на 2, то объем работы пропорционален N2 + N. По мере того как увеличивается N, N2 быстро становится больше, чем N (например, если N равно тысяче, N2 равно миллиону), поэтому можно принять, что объем работы примерно пропорционален N2, или N в квадрате. Такой темп прироста называется квадратичным. Он хуже линейного, а если точнее, то намного хуже. Если элементов вдвое больше, то их сортировка будет выполняться в четыре раза дольше, если вдесятеро – в сто раз дольше, а если увеличить количество в тысячу раз, то потребуется в миллион раз больше времени! Это нехорошо.
К счастью, сортировать можно гораздо быстрее. Давайте рассмотрим один умный способ – алгоритм под названием Quicksort[29], который изобрел английский ученый-компьютерщик Тони Хоар примерно в 1959 году. (А в 1980-м Хоар получил премию Тьюринга за многочисленные вклады в науку, в том числе Quicksort.) Это элегантный алгоритм и отличный пример принципа «разделяй и властвуй».
Перед нами снова несортированные названия:
Intel Firefox Zillow Yahoo Pinterest Twitter Verizon Bing Apple Google Microsoft Sony PayPal Skype IBM Ebay
Чтобы отсортировать названия с помощью упрощенной версии Quicksort, просмотрим их один раз и отберем в одну колонку имена, которые начинаются с буквы в диапазоне от А до М, а в другую – от N до Z. В результате мы получим две группы, каждая из которых содержит примерно половину названий. Допустим, что распределение имен не слишком асимметрично, и тогда на каждом этапе в обе колонки будет попадать примерно по половине названий. В нашем случае получатся две группы, содержащие по восемь названий:
Intel Firefox Bing Apple Google Microsoft IBM Ebay
Zillow Yahoo Pinterest Twitter Verizon Sony PayPal Skype
Теперь проверим группу A-M: отсортируем названия с первой буквой от А до F в одну колонку, и от G до М – в другую. Затем проверим группу N-Z и перенесем названия, начинающиеся с буквы от N до S в одну колонку, а от Т до Z – в другую. На данном этапе мы сделали два прохода по названиям и получили четыре колонки, в каждой из которых содержится четверть названий:
Firefox Bing Apple Ebay
Intel Google Microsoft IBM
Pinterest Sony PayPal Skype
Zillow Yahoo Twitter Verizon
На следующем этапе мы проходим по каждой из новых групп, разделяя A – F на ABC и DEF, G – M на GHIJ и KLM, и то же самое для N-S и Т-Z. Теперь у нас есть восемь колонок, и в каждой содержится в среднем два названия:
Bing Apple
Firefox Ebay
Intel Google IBM
Microsoft
Pinterest PayPal
Sony Skype
Twitter Verizon
Zillow Yahoo
На каком-то этапе, конечно, нам придется проверять не только первую букву в названии, чтобы, например, поместить IBM перед Intel и Skype перед Sony. Но после еще одного или двух проходов мы получим 16 колонок по одному имени в каждой, и все они расположены в алфавитном порядке.
Сколько нам потребовалось действий? Мы проверили каждое из 16 названий в каждом проходе. Если всякий раз получалось идеально равномерное деление, то колонки содержали сначала по 8 названий, затем по 4, по 2 и по 1. Количество проходов равно количеству делений 16 на 2 до получения 1. Это логарифм 16 по основанию 2, то есть 4. Таким образом, объем работы равен 16 log2 16 для шестнадцати имен. Совершив четыре прохода по данным, мы получаем 64 операции против 136 при сортировке методом выбора. И это для 16 названий, а когда их больше, преимущества Quicksort гораздо заметнее, что показано на рис. 4.1.
Рис. 4.1. Рост log N, N, N log N и N2
Этот алгоритм всегда подходит для сортировки данных, но его применение эффективно только в том случае, если при каждом делении будут получаться примерно одинаковые колонки. При настоящих вычислениях алгоритм Quicksort должен догадаться, где находится срединное значение данных, чтобы всякий раз делить их на две примерно равных по размеру группы. На практике это удается довольно точно оценить, выбрав несколько пробных элементов. В целом Quicksort требуется около N × log N операций для сортировки N элементов, то есть объем работы пропорционален N × log N. Эта зависимость хуже, чем линейная, но не во много раз, и значительно лучше, чем квадратичная.
График на рис. 4.1 показывает, как log N, N, N log N и N2 растут по мере увеличения объема данных. Первые три построены для 20 значений, но квадратичное – только для 10, иначе линия графика вышла бы за пределы рисунка.
В качестве эксперимента я сгенерировал 10 миллионов случайных 9-значных чисел, аналогичных номерам социального страхования США, и замерил время, которое заняла сортировка групп разного размера с помощью метода выбора (зависимость N2, или квадратичная) и алгоритма Quicksort (зависимость Nlog N). Результаты представлены на рис. 4.2. Прочерк в таблице означает, что я опускал эти вычисления.
Точно измерить время для программы, которая быстро выполняет операции, сложно, поэтому относитесь к полученным цифрам с большой долей скептицизма. Впрочем, вы всё же можете увидеть примерный рост ожидаемого затраченного времени в пропорции N log N для Quicksort, а также то, что сортировка методом выбора приемлема до объема, скажем, в 10 000 элементов, хотя и не способна составить конкуренцию другому способу. На каждом этапе она безнадежно уступает Quicksort.
Вероятно, вы также заметили, что время сортировки методом выбора для 100 000 элементов примерно в 200 раз больше, чем для 10 000 (вместо ожидаемого стократного увеличения). Скорее всего, дело в кэшировании: не все числа помещаются в кэш, и сортировка ведется медленнее.
Это хорошая иллюстрация различий между вычислительными усилиями в теории и реальностью конкретного вычисления с помощью настоящей программы.
Рис. 4.2. Сравнение времени сортировки
4.4. Трудности и сложности
Мы рассмотрели несколько вопросов, относящихся к темам «сложности» алгоритмов или времени их выполнения. На одном конце диапазона находится log N, зависимость для двоичного поиска, где с увеличением количества данных объем работы возрастает медленно. Наиболее распространенный алгоритм – линейный, с простой зависимостью N, где объем работы прямо пропорционален количеству данных. У алгоритма Quicksort зависимость Nlog N, и это хуже, чем N (число операций увеличивается быстрее), но он все же исключительно удобен для больших значений N, потому что в целом значения логарифма растут медленно. Есть еще алгоритм с квадратичной зависимостью N2, где объем работы увеличивается так быстро, что получается нечто среднее между томительным и непрактичным.
Существует много других вариантов сложности. Какие-то из них легко понять – например, кубические, или N3, которые еще хуже, чем квадратичные, хотя идея та же, – а другие настолько мудреные, что разобраться в них способны только специалисты. Вам стоит знать еще один показатель, так как он встречается на практике. Он особенно тяжеловесный, но важный. Речь об экспоненциальной сложности, где затраты времени увеличиваются примерно в пропорции 2N (не то же самое, что N2). Здесь объем работы растет исключительно быстро – удваивается при добавлении всего одного элемента. В некотором смысле экспоненциальный алгоритм (ЭА) находится в противоположном конце спектра от алгоритма log N, где при удвоении количества элементов прибавляется только один шаг.
Пропорции вида 2N возникают в ситуациях, когда мы должны проверить на практике все возможности одну за другой. К счастью, есть один положительный момент в существовании проблем, для решения которых требуются ЭА. Некоторые алгоритмы, особенно в криптографии, основываются на экспоненциальной сложности выполнения какой-либо вычислительной задачи. Для таких алгоритмов выбирают настолько большие значения N, что задачу невозможно решить напрямую в разумные сроки, не зная секретный ускоренный метод. Тем самым обеспечивается защита от злоумышленников. Криптографию мы рассмотрим в главе 13.
Но сейчас у вас должно появиться интуитивное понимание того, что одни проблемы решить легко, а другие – тяжело. Мы можем охарактеризовать это различие более точно. «Легкие» задачи «полиномиальные» по своей сложности, то есть время их решения можно выразить в виде какого-либо полинома вроде N2. Впрочем, если показатель степени больше 2, то проблемы становятся тяжелее. (Не волнуйтесь, если вы забыли, что означает «полиномиальный», – здесь это выражение употребляется только для обозначения целых степеней переменной, например, N2 или Ж) Специалисты по информатике определяют этот класс задач как Р (polynomial), потому что их можно решить за полиномиальное время.
Для решения большого количества задач и проблем, возникающих на практике, требуются ЭА, то есть мы не знаем для них ни одного полиномиального алгоритма. Эти задачи называются NP. Их свойства таковы, что мы не способны быстро найти для них решение, но можем быстро проверить правильность предложенного решения. NP расшифровывается как «недетерминированный полином». Если объяснять упрощенно, то такие задачи можно решить за полиномиальное время с помощью алгоритма, который всегда угадывает правильно, когда ему приходится делать выбор. В реальной жизни такого везения не бывает, так что это всего лишь теоретическая концепция.
Многие NP-задачи довольно узкоспециальные, но одну из них легко объяснить и представить, как она применяется на практике. В задаче коммивояжера (TSP, Travelling Salesman Problem) продавец должен начать со своего родного города, посетить ряд определенных городов в любом порядке, а затем вернуться домой. Его или ее цель – посетить каждый город только один раз (без повторений), преодолев наименьшее расстояние44. По аналогии можно разработать эффективный маршрут для школьного автобуса или мусоровоза, а когда я давным-давно занимался TSP, на нее опирались для решения таких разнообразных задач, как распределение дырок в печатных платах и отправка лодок для отбора проб воды в определенных точках Мексиканского залива.
На рис. 4.3 показана случайно сгенерированная задача с 10 городами. Ее решение находят по интуитивно привлекательной эвристической процедуре «ближайшего соседа»: начните с любого города и затем переходите к ближайшему месту, где еще не побывали. «Длина» (маршрут оценивается по заранее заданному критерию выгодности, например: кратчайший, самый дешевый, совокупный критерий и т. п.) этого маршрута составляет 12,92. Заметьте, что путь зависит от выбора первого города. Маршрут на рис. 4.3 – самый короткий из возможных при использовании данного метода.
Рис. 4.3. Решение по методу «ближайшего соседа» для TSP с 10 городами (длина 12,92)
Задачу коммивояжера, впервые описанную в XIX веке, старательного изучали на протяжении многих лет. Мы научились хорошо справляться с решением даже более сложных примеров, но методы поиска кратчайшего пути все еще сводятся к хитроумным способам анализа всех возможных маршрутов. Для сравнения, на рис. 4.4 показан самый короткий маршрут, найденый методом перебора всех 180 000 возможных путей. Его длина составляет 11,86, что примерно на 8 % короче лучшего маршрута «ближайшего соседа».
То же самое верно для широкого спектра задач: у нас нет более удачного метода для эффективного решения, чем перебор всех имеющихся вариантов. Это огорчает людей, которые занимаются изучением алгоритмов. Нам до сих пор неизвестно, сложны ли эти проблемы по своей природе или мы просто глупы и еще не придумали решения для них. Впрочем, сегодня чаще всего ставят на «сложные по природе».
Рис. 4.4. Наилучшее решение для TSP из 10 городов (длина 11,86)
Стивен Кук в 1971 году получил замечательное математическое доказательство того, что многие из этих задач эквивалентны в следующем смысле: если мы найдем алгоритм с полиномиальным временем выполнения (что-то вроде N2) для одной из них, это позволит нам найти алгоритмы для всех остальных. За свою работу Кук в 1982 году удостоился премии Тьюринга.
В 2000 году Математический институт Клэя[30] предложил премию в миллион долларов тому, кто найдет решение для одной из семи нерешенных проблем (так называемых Задач тысячелетия). Один из этих вопросов касался определения того, равны ли P и NP, то есть эквивалентны ли на самом деле «тяжелые» и «легкие» задачи45. Гипотеза Пуанкаре – еще одна задача в списке, она датируется началом 1900-х годов. Ее решил российский математик Григорий Перельман, которого наградили премией в 2010 году, но ученый отказался ее принять. Осталось только шесть проблем – лучше поторопитесь, а то вас кто-нибудь опередит!
Говоря о сложности алгоритмов, надо держать в уме еще пару фактов. Хотя вопрос равенства P и NP важен, он скорее теоретический, чем практический. Большинство результатов по сложности, о которых говорят ученые-информатики, относятся к наихудшему случаю. То есть примеры некоторых задач потребуют для вычисления ответа максимально возможного времени, но не все они настолько тяжелы. Кроме того, это асимптотические оценки, применимые только для больших значений N. В повседневной жизни N бывает настолько маленьким, что асимптотическое поведение не имеет значения. Например, если у вас есть только несколько десятков или даже сотен элементов, то сортировка по методу выбора получится достаточно быстрой, хотя ее сложность квадратична, и асимптотически такая зависимость намного хуже, чем N log N в Quicksort. Если вы посещаете только 10 городов, то вполне возможно перебрать все возможные маршруты, однако данный метод вряд ли осуществим для 100 городов и совершенно невозможен для 1000. Наконец, в большинстве реальных ситуаций достаточно будет найти примерное решение, так как в поиске абсолютно оптимального ответа нет необходимости.
С другой стороны, некоторые важные приложения, такие как криптографические системы, основываются на убеждении, что задействованная в них задача действительно сложна. Поэтому возможность обнаружения атаки, пусть и выглядящая нецелесообразной в краткосрочной перспективе, может оказаться очень важной.
4.5. Краткие выводы
Информатика как область науки потратила годы на изучение концепции «как быстро мы можем вычислять». Квинтэссенцией таких поисков стала идея выражать время выполнения задачи в зависимости от количества данных (например, N, log N, N2, или N log N). Здесь опускаются такие моменты, как скорость работы разных компьютеров и разница в таланте программистов. Однако тут затрагивается проблема сложности самой задачи или алгоритма, и поэтому данный метод хорошо подойдет для того, чтобы провести сравнение и сделать вывод, будут ли какие-либо вычисления выполнимыми. (Необязательно, чтобы объективная сложность задачи и алгоритма для ее решения совпадали. Например, сортировка – это проблема сложности N log N, но для нее применимы и Quicksort, алгоритм N log N, и сортировка по методу выбора, алгоритм N2.)
Изучение алгоритмов и сложности – важная часть информатики как в теории, так и на практике. Нас интересует, что можно вычислить, а что нет, и как это сделать быстро, да еще не занять больше необходимого объема памяти (или, возможно, отыскать баланс между скоростью и памятью). Мы постоянно ищем принципиально новые и лучшие способы вычислений: Quicksort здесь хороший пример, пусть и давний.
Многие алгоритмы более специализированны и сложны, чем базовый поиск и сортировка. Например, алгоритмы сжатия пытаются уменьшить объем памяти, занимаемый текстом, музыкой (MP3, AAC), изображениями (PNG, JPEG) и фильмами (MPEG). Также важны алгоритмы обнаружения ошибок и их исправления, ведь данные могут повреждаться при хранении и передаче: в беспроводных каналах возникают зашумления, а на CD появляются царапины. Алгоритмы, которые вносят в данные управляемую избыточность, позволяют обнаружить и даже исправить некоторые виды ошибок. Мы еще вернемся к этим алгоритмам в главе 8, поскольку они будут важны в разрезе коммуникационных сетей.
От алгоритмов сильно зависит криптография – искусство отправлять секретные сообщения таким образом, чтобы их удалось прочесть только надлежащим адресатам. В главе 13 мы обсудим криптографию подробно, так как она очень важна для безопасного обмена конфиденциальной информацией между компьютерами.
Еще одна область, где алгоритмы играют решающую роль, – поисковые системы вроде Bing и Google. В принципе, многое из того, что они делают, устроено просто: система собирает какое-то количество веб-страниц, упорядочивает информацию так, чтобы ее легче получалось найти, а затем выполняет эффективный поиск по ней. Проблема в масштабе: веб-страниц миллиарды, и каждый день появляются миллиарды запросов. Даже зависимость N log N здесь недостаточно хороша, поэтому применяется множество алгоритмических и программных ухищрений, направленных на то, чтобы поисковые системы работали достаточно быстро, успевая за увеличением масштабов интернета и ростом нашего интереса к отысканию в нем того, что нам нужно. Более тщательно мы обсудим данную тему в главе 11.
Кроме того, алгоритмы лежат в основе таких сервисов, как машинное понимание речи, распознавание лиц и изображений, автоматический перевод языков и так далее. Все они основываются на огромном количестве данных, добытых для реализации соответствующих функций. Значит, тут требуются линейные или даже более легкие алгоритмы, чаще всего с возможностью параллельной работы, чтобы отдельные их фрагменты могли выполняться на нескольких процессорах одновременно. Подробнее об этом в главе 1246.