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

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

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

3. Выравнивание данных

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

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

6. Рандомизированные алгоритмы

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

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

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

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

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