Герб Саттер - Стандарты программирования на С++. 101 правило и рекомендация

• Следует точно знать сложность используемого алгоритма. Не забывайте о такой ловушке, как линейный алгоритм, который вызывает другую линейную операцию, что в результате делает алгоритм квадратичным (см., например, рекомендацию 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

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

В [Stroustrup00] §6 имеется замечательная цитата:

Преждевременная оптимизация — корень всех бед.

С другой стороны, мы не можем игнорировать эффективность.

Хоар и Кнут совершенно правы (см. рекомендацию 6 и эту). Но прав и Бентли (рекомендация 9).

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

Всегда помните:

Гораздо, гораздо проще сделать корректную программу быстрой, чем быструю — корректной.

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

Имеются две основные причины, почему преждевременная оптимизация зачастую не делает программу быстрее. Во-первых, общеизвестно, что программисты обычно плохо представляют, какой код будет быстрее или меньше по размеру, и где будет самое узкое место в разрабатываемом коде. В число таких программистов входят и авторы этой книги, и вы. Подумайте сами — современные компьютеры представляют собой исключительно сложные вычислительные модели, зачастую с несколькими работающими параллельно процессорами, глубокой иерархией кэширования, предсказанием ветвления, конвейеризацией и многим- многим другим. Компилятор, находящийся над всем этим аппаратным обеспечением, преобразует ваш исходный код в машинный, основываясь на собственном знании аппаратного обеспечения и его особенностей, с тем чтобы этот код в максимальной степени использовал все возможности аппаратного обеспечения. Над компилятором находитесь вы, с вашими представлениями о том, как должен работать тот или иной код. У вас практически нет шансов внести такую микрооптимизацию, которая в состоянии существенно повысить производительность генерируемого интеллектуальным компилятором кода. Итак, оптимизации должны предшествовать измерения, а измерениям должна предшествовать выработка целей оптимизации. Пока необходимость оптимизации не доказана — вашим приоритетом №1 должно быть написание кода для человека. (Если кто-то потребует от вас оптимизации кода — потребуйте доказательств необходимости этого.)

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

Само собой разумеется, настанет день, когда вам действительно придется заняться оптимизацией вашего кода. Когда вы займетесь этим — начните с оптимизации алгоритмов (рекомендация 7) и попытайтесь инкапсулировать оптимизацию (например, в пределах функции или класса, см. рекомендации 5 и 11), четко указав в комментариях причину проводимой оптимизации и ссылку на использованный алгоритм.

Обычная ошибка новичка состоит в том, что когда он пишет новый код, то — с гордостью! — старается сделать его оптимальным ценой понятности. Чаще всего это приводит к милям "спагетти" (говоря проще — к "соплям" в программе), и даже корректно работающий код становится очень трудно читать и модифицировать (см. рекомендацию 6).