7. Кодирование с учетом масштабируемости

7. Кодирование с учетом масштабируемости

Резюме

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

Обсуждение

Эта рекомендация иллюстрирует важную точку равновесия между рекомендациями 8 и 9 — не оптимизируйте преждевременно и не пессимизируйте преждевременно. Это делает данный материал трудным в написании, поскольку он может быть неверно истолкован как совет о "преждевременной оптимизации". Это не так.

Вот предпосылки для данной рекомендации. Память и дисковая емкость растут экспоненциально; например, с 1988 по 2004 год емкость дисков росла примерно на 112% в год (почти в 1900 раз за десятилетие). Очевидным следствием этого факта является то, что любой ваш сегодняшний код завтра может иметь дело с большими объемами данных — намного большими! Плохое (хуже линейного) асимптотическое поведение алгоритма рано или поздно поставит на колени даже самую мощную систему, просто завалив ее достаточным количеством данных.

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

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

Данный совет состоит из двух частей. Во-первых, даже до того, как станет известно, будут ли объемы данных достаточно велики, чтобы для конкретных вычислений возникла проблема, по умолчанию следует избегать использования алгоритмов, которые работают с пользовательскими данными (которые могут расти), но не способны к масштабированию, если только использование менее масштабируемого алгоритма не приводит к существенному повышению понятности и удобочитаемости кода (см. рекомендацию 6). Но все мы часто сталкиваемся с сюрпризами. Мы пишем десять фрагментов кода, думая, что они никогда не будут иметь дела с большими наборами данных. И это действительно оказывается так — в девяти случаях из десяти. В десятом случае мы сталкиваемся с проблемами производительности. Это не раз случалось с нами, и мы знаем, что это случалось (или случится) и с вами. Конечно, мы вносили исправления и передавали их потребителям, но лучше было бы избежать таких затруднений и выполнения лишней работы. Так что при прочих равных условиях (включая понятность и удобочитаемость) воспользуйтесь следующими советами.

• Используйте гибкие динамически распределяемые данные вместо массивов фиксированного размера. Массив "больший, чем наибольший массив, который мне когда-либо потребуется" приводит к ошибкам и нарушению безопасности (см. рекомендацию 77). Массивы можно использовать только тогда, когда размеры данных фиксированы и известны во время компиляции.

• Следует точно знать сложность используемого алгоритма. Не забывайте о такой ловушке, как линейный алгоритм, который вызывает другую линейную операцию, что в результате делает алгоритм квадратичным (см., например, рекомендацию 81).

• По возможности используйте линейные или более быстрые алгоритмы. Идеальны алгоритмы с константной сложностью, такие как push_back или поиск в хэш-таблице (см. рекомендации 76 и 80). Неплохи алгоритмы со сложностью O(log N), такие как операции с контейнерами set/map и lower_bound или upper_bound с итераторами произвольного доступа (см. рекомендации 76, 85 и 86). Допустима линейная сложность O(N), как, например, у vector::insert или for_each (см. рекомендации 76, 81 и 84).

• Пытайтесь избежать применения алгоритмов с более чем линейной сложностью, где это возможно. Например, по умолчанию следует затратить определенные усилия на поиск замены имеющегося алгоритма со сложностью O(N log N) или O(N) (если таковая возможна), чтобы избежать непропорционального падения производительности при существенном увеличении объема данных. Так, именно в этом заключается основная причина, по которой в рекомендации 81 советуется предпочитать операции с диапазонами (которые обычно линейны) их копиям для работы с отдельными элементами (которые обычно квадратичны, так как одна линейная операция вызывает другую линейную операцию; см. пример 1 в рекомендации 81).

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

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

Итак, предпочтительно использовать линейные (или лучшие) алгоритмы там, где только это возможно. Избегайте, где можете, алгоритмов с более чем линейной сложностью, и уж тем более — экспоненциальных.

Ссылки

[Bentley00] §6, §8, Appendix 4 • [Cormen01] • [Kernighan99] §7 • [Knuth97a] • [Knuth97b] • [Knuth98] • [McConnell93) §5.1-4, §10.6 • [Murray93] §9.11 • [Sedgewick98] • [Stroustrup00] §17.1.2