Пространство или время

Пространство или время

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

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

Листинг 1.3. Первоначальная функция определения количества установленных битов в байте

function CountBitsl(B : byte):byte;

begin

Result := 0;

while (B <> 0) do

begin

if Odd(B) then

inc(Result);

B := B shr 1;

end;

end;

Как видите, в этой функции не используются промежуточные переменные. Она просто считает установленные биты путем деления значения на 2 (сдвиг целого значения на один бит вправо эквивалентно делению на 2) и определения количества полученных нечетных результатов. Цикл завершается, когда будет получено значение 0, поскольку в этом случае очевидно, что установленных битов больше нет. Значение О большого для приведенного алгоритма зависит от количества установленных битов в параметре, и в худшем случае внутренний цикл будет выполнен восемь раз. Таким образом, это алгоритм класса O(n).

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

Тем не менее, давайте рассмотрим назначение алгоритма с другой точки зрения. В качестве входного значения функция принимает 1-байтный параметр, с помощью которого можно передать всего 256 значений. В таком случае, почему бы нам заранее не вычислить все возможные ответы и не записать их в статический массив? Реализация нового алгоритма приведена в листинге 1.4.

Листинг 1.4. Улучшенная функция определения количества установленных битов в байте const

BitCounts : array [0..255] of byte =

(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8);

function CountBits2(B : byte): byte;

begin

Result := BitCounts[B];

end;

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

На компьютере автора книги последний алгоритм оказался в 10 раз быстрее, чем первый: 10 вызовов второй функции занимает столько же времени, сколько один вызов первой. (Обратите внимание, что здесь речь идет о среднем случае. В лучшем случае для первой функции значение параметра равно 0 и функция практически не будет требовать времени на выполнение.)

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

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Пространство имен XSL

Из книги автора

Пространство имен XSL Заметьте, что элементы XSLT, такие как <xsl:stylesheet>, используют префикс пространства имен (namespace) xsl, который теперь, после стандартизации XSLT, всегда установлен в «http://www.w3.org/1999/XSL/Transform». Это пространство имен обычно устанавливается с атрибутом xmlns (это не


Адресное пространство процесса

Из книги автора

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


Организуем рабочее пространство

Из книги автора

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


Пространство модели и пространство листа

Из книги автора

Пространство модели и пространство листа Пространство модели (Model Space) – это пространство AutoCAD, где формируются модели объектов как при двумерном, так и при трехмерном моделировании. О том, что в окне AutoCAD на текущий момент установлено пространство модели, говорят


Пространство для трехмерного моделирования

Из книги автора

Пространство для трехмерного моделирования Чтобы воспользоваться всеми возможностями трехмерного черчения, предоставляемыми программой, следует переключиться из пространства AutoCAD Classic (Классический AutoCAD) или 2D Drafting & Annotation (Двухмерное черчение и аннотирование) в 3D


Пространство модели и пространство листа

Из книги автора

Пространство модели и пространство листа Пространство модели (Model Space) – это пространство AutoCAD, где формируются модели объектов как при двумерном, так и при трехмерном моделировании. О том, что в окне AutoCAD на текущий момент установлено пространство модели, говорят


Виртуальное пространство

Из книги автора

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


Пространство имен оболочки

Из книги автора

Пространство имен оболочки BrowseCallbackProc Функция BrowseCallbackProc представляет собой определяемую приложением функцию обратного вызова, используемую совместно с функцией SHBrowseForFolder . Диалоговое окно выбора папки вызывает эту функцию для уведомления о событиях. Тип BFFCALLBACK


Пространство модели и пространство листа

Из книги автора

Пространство модели и пространство листа Пространство модели (Model Space) – это пространство AutoCAD, где формируются модели объектов как при двумерном, так и при трехмерном моделировании. О том, что в окне AutoCAD на текущий момент установлено пространство модели, говорят


Пространство модели и пространство листа

Из книги автора

Пространство модели и пространство листа Пространство модели (Model Space) – это пространство AutoCAD, где формируются модели объектов как при двумерном, так и при трехмерном моделировании. О том, что в окне AutoCAD на текущий момент установлено пространство модели, говорят


Пространство имен XSLT

Из книги автора

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


5 Официальное пространство

Из книги автора

5 Официальное пространство Ваш коллега в офисе жует жевательную резинку, проигрывает на персональном компьютере «Where-in-the-World-is-Carmen-San-Diego?», охает и задает глупые вопросы. А в это время вы пытаетесь разобраться с ка-ким-то непонятным багом. В этой компании вы работаете


2.4.2. Время установки Windows 7 и время жизни аккумулятора

Из книги автора

2.4.2. Время установки Windows 7 и время жизни аккумулятора Если вы устанавливаете Windows 7 на ноутбук или нетбук, желательно подключить его к сети питания. Если это невозможно, тогда лучше не начинать установку Windows. Хотя весь процесс установки занимает около 20–25 минут (во всяком