Питер Макоуэн - Вычислительное мышление - Метод решения сложных задач

Получается, что в двоичной записи второй символ меняется только в том случае, если в первой позиции уже были и 0, и 1. Но если убрать каждую вторую карту в этой последовательности, у нас остается не 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1 ..., а 0, 1, 0, 1, 0, 1, ... И мы получаем:

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

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

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

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

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

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