Это вторая часть из серии заметок об оптимизации программ. Первая часть находится здесь. Сегодня мы поговорим о том, как правильно выбирать алгоритмы и структуры данных, основываясь на Big O notation.
Теория
Какой алгоритм быстрее - O(n) или O(1)? Правильный ответ - "это зависит от набора данных, над которым работает алгоритм, и от платформы, на которой работает данный алгоритм". При выборе алгоритма следует помнить, что O(f(n)) означает C1 + C2*f(n), где:- С1 - время, необходимое на "старт" алгоритма. Это время не зависит от n. Это время может быть существенным для алгоритмов, требующих большого объема предварительных вычислений.
- С2 - время, затрачиваемое на каждую итерацию алгоритма. В теории C2 не зависит от n, но на практике это не так. C2 для маленьких n часто бывает меньше, чем C2 для больших n. Также C2 может сильно варьироваться для одного и того же набора данных в зависимости от того, где эти данные расположены и в каком порядке осуществляется к ним доступ. Основной вклад в варьирование C2 вносит прозрачное кэширование на различных уровнях. Например, если весь набор данных плотно сгруппирован в небольшой области памяти (например, на одной странице памяти), то C2 может быть на несколько порядков меньше, чем если бы этот же набор данных был разбросан по произвольным адресам памяти. Это объясняется следующими причинами:
- Прозрачное кэширование основано на принципе locality of reference, поэтому велика вероятность, что данные, плотно сгруппированные в небольшой области памяти, окажутся в самом быстром кэше.
- Translation lookaside buffer (TLB) может не содержать записей для некоторых страниц памяти с нашими данными, поэтому CPU будет вынужден тратить дополнительное время на поиск физических адресов страниц, отсутствующих в TLB.
- Некоторые страницы памяти могут быть вытеснены из основной памяти, поэтому при обращении к ним будет затрачено много времени на поиск и чтение страниц из более медленной памяти.
- Если весь набор данных находится в кэше L1, то время доступа к нему находится в районе 0.5 нс.
- Если набор данных помещается лишь в кэш L2, то время доступа становится равным 7 нс, т.е. увеличивается в 14 раз. Во столько же раз может возрасти и C2 для нашего алгоритма.
- Если набор данных раскидан по основной памяти и целиком находится в RSS, то время доступа к произвольному элементу этого набора увеличивается до 100 нс, т.е. C2 возрастает в 200 раз по сравнению с самым первым вариантом.
- Если набор данных не помещается в RSS, то время доступа может увеличиться до 10.000.000 нс, т.е. С2 увеличивается в 20 миллионов раз по сравнению с первым вариантом.
Практика
Рассмотрим три классических алгоритма.-
Поиск по ключу
Всем известно, что время поиска по ключу в хэш-таблице в общем случае не зависит от количества элементов, среди которых осуществляется поиск, т.е. оно эквивалентно O(1). Означает ли это, что хэш-таблицы нужно использовать во всех случаях, когда требуется осуществить поиск по ключу? Нет! Если количество элементов, по которым производится поиск, невелико, то полный перебор всех элементов может оказаться быстрее поиска в хэш-таблице. Время поиска в хэш-таблице является константой C11, которая в общем случае включает в себя три составляющие:
- время, затрачиваемое на вычисление хэш-функции от ключа
- время, затрачиваемое на доступ к элементу в хэш-таблице по индексу
- время, затрачиваемое на сравнение ключа для выбранного из таблицы элемента с заданным ключом
- время, затрачиваемое на последовательный доступ к следующему элементу массива
- время, затрачиваемое на сравнение ключа для выбранного из массива элемента с заданным ключом
- Сортировка Какой метод сортировки быстрее - heapsort или сортировка пузырьком? Согласно Big O notation, heapsort имеет вычислительную сложность O(n*ln(n)), а сортировка пузырьком - O(n*n). Очевидно, что heapsort должна одержать победу при сравнительно больших n :) Но это не так. Если сравнить последовательности обращения к элементам в этих алгоритмах, то можно увидеть, что heapsort обращается к элементам в "произвольном" порядке, а сортировка пузырьком проходит все элементы последовательно. Отсюда напрашивается вывод, что сортировка пузырьком победит в случае, если произвольный доступ к элементам существенно медленнее последовательного доступа. Это бывает на практике, если вспомнить про locality of reference и data prefetching.
- Стек Какая структура данных будет работать быстрее при организации стека - linked list или динамический массив? Обе структуры данных позволяют добавлять и удалять элементы со стека за O(1) в общем случае, но динамический массив иногда требует дополнительное время O(n) на расширение и сжатие. Обычно на практике побеждает динамический массив, т.к. при работе со стеком обращение к его элементам в памяти осуществляется последовательно. Значит, высока вероятность, что эти элементы уже будут находиться в самом быстром кэше. При работе же с linked list элементы могут быть разбросаны по всей памяти, что может привести к тормозам.
Релоцировались? Теперь вы можете комментировать без верификации аккаунта.