Реальные условия — насколько быстро?

Хотя при исследовании сложности алгоритма обычно полезно отбросить малые члены уравнения и постоянные множители, иногда их все‑таки необходимо учитывать, особенно если размерность данных задачи N мала, а постоянные множители достаточно велики.

Допустим, мы рассматриваем два алгоритма решения одной задачи. Один выполняется за время порядка O(N), а другой — порядка O(N²). Для больших N первый алгоритм, вероятно, будет работать быстрее.

Тем не менее, если взять конкретные функции оценки времени выполнения для каждого из двух алгоритмов, например, для первого f(N)=30*N+7000, а для второго f(N)=N², то в этом случае при N меньше 100 второй алгоритм будет выполняться быстрее. Поэтому, если известно, что размерность данных задачи не будет превышать 100, возможно будет целесообразнее применить второй алгоритм.

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

 

 

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

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

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

Обращение к файлу подкачки

Важным фактором при работе в реальных условиях является частота обращения к файлу подкачки (page file). Операционная система Windows отводит часть дискового пространства под виртуальную память (virtual memory). Когда исчерпывается оперативная память, Windows сбрасывает часть ее содержимого на диск. Освободившаяся память предоставляется программе. Этот процесс называется подкачкой, поскольку страницы, сброшенные на диск, могут быть подгружены системой обратно в память при обращении к ним.

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

Приведенная в числе примеров программа Pager запрашивает все больше и больше памяти под создаваемые массивы до тех пор, пока программа не начнет обращаться к файлу подкачки. Введите количество памяти в мегабайтах, которое программа должна запросить, и нажмите кнопку Page (Подкачка). Если ввести небольшое значение, например 1 или 2 Мбайт, программа создаст массив в оперативной памяти, и будет выполняться быстро.

Если же вы введете значение, близкое к объему оперативной памяти вашего компьютера, то программа начнет использовать файл подкачки. Вполне вероятно, что она будет при этом обращаться к диску постоянно. Вы также заметите, что программа выполняется намного медленнее. Увеличение размера массива на 10 процентов может привести к 100‑процентному увеличению времени исполнения.

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

 

Если же вы нажмете на кнопку Thrash (Пробуксовка), программа будет случайно обращаться к разным участкам памяти. При этом вероятность того, что нужная страница находится в этот момент на диске, намного возрастает. Это избыточное обращение к файлу подкачки называется пробуксовкойпамяти (thrashing). В табл. 1.4 приведено время исполнения программы Pager на компьютере с процессором Pentium с тактовой частотой 90 МГц и 24 Мбайт оперативной памяти. В зависимости от конфигурации вашего компьютера, скорости работы с диском, количества установленной оперативной памяти, а также наличия других запущенных параллельно приложений время выполнения программы может сильно различаться.

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

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

Иногда можно написать код так, что программа будет обращаться к блокам памяти последовательно. Алгоритм сортировки слиянием, описанный в 9 главе, манипулирует большими блоками данных. Эти блоки сортируются, а затем сливаются вместе. Упорядоченная работа с памятью уменьшает число обращений к диску.

 

@Таблица 1.4. Время выполнения программы Pager в секундах

Память (Мбайт)

Подкачка

Пробуксовка

2

3,79

3,73

4

7,58

7,47

6

11,37

11,2

8

15,49

14,94

10

18,9

18,62

12

22,85

22,36

14

26,47

26,15

16

30,26

29,88

18

34,51

37,46

20

132,37

12,155 (оценка)

 

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