Алгоритмы и платформы

Лучший, средний и худший случаи

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

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

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

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

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

3.5.1 Виртуализация памяти

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

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

Если же приложение считывает блоки в произвольном порядке, например, сначала из блока 56, затем из блоков 123, 12, 234 и т. д., то частота ошибок отсутствия страницы увеличивается. Индикатор работы диска будет гореть почти постоянно, а скорость работы приложения заметно упадет. Это и есть пробуксовка – непрерывный обмен страницами между диском и ОЗУ, вызванный запросами приложения страниц в произвольном порядке.

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

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

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

Говоря «один элемент располагается рядом с другим элементом», мы используем понятие локальности в смысле расстояния. С другой стороны это понятие можно трактовать по отношению ко времени. Воплощением локальности ссылок во времени является кэш-память.

3.5.2 Использование кэша

Кэш память работает по принципу «если элемент недавно использовался, он скоро будет использоваться снова» или «элемент Х всегда используется с элементом Y». Кэш-память представляет собой небольшой блок памяти для некоторого процесса, содержащий элементы, которые использовались недавно. При каждом использовании элемента он копируется в кэш-память. Если кэш заполнен, то применяется алгоритм удаления наиболее давно использованных элементов, который элемент, давно не использовавшийся, замещается элементом, который использовался недавно. Таким образом, кэш-память содержит несколько близких в пространственном смысле элементов, которые близки и в смысле времени их использования.

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

3.5.3 Выравнивание данных

Современные процессоры устроены таким образом, что они считывают данные отдельными кусками по 32 бита (4 байта). Это означает, что адреса памяти, передаваемые от процессора в его кэш-память, всегда делятся на 4 без остатка, т. е. два младших бита адреса являются нулевыми. В 64-разрядных процессорах адресация является 64-битной и выравнивание производится по границе 8 байт.

Если внутреннее представление данного неструктурированного типа переходит в памяти границу 4 байт, например, процессору придется выдавать две команды на считывание кэша: первая команда для считывания части данного, расположенной в первой четырехбайтной ячейке, вторая команда для считывания второй части. Затем процессору потребуется соединить две части данного и отбросить ненужные биты. Это замедляет процесс вычислений. Современные системы программирования автоматически выполняют выравнивание. Например, 32-разрядные версии компилятора Delphi автоматически выравнивают не только глобальные и локальные примитивные данные, а также и поля типа record (если этим типом описывается неупакованная запись).

Дата добавления: 2014-01-07