Совершенный код. Совершенный код. Мастер-класс. Стив Макконнелл. Руководство по стилю программирования и конструированию по
 Скачать 5.88 Mb.
|
|
ГЛАВА 26 Методики оптимизации кода 605 Эти строки обрабатывают случай, который может быть упущен из-за увеличении счетчика цикла на 2, а не на 1. if ( i == count ) { a[ count 1 ] = count 1; } Как видите, мы заменили первоначальную строку a[ i ] = i на две строки и увели# чиваем счетчик цикла на 2, а не на 1. Дополнительный код после цикла while ну# жен на случай нечетных значений переменной count, при которых цикл завер# шается, так и не обработав один элемент массива. Конечно, девять строк хитрого кода труднее читать и сопровождать, чем пять строк простого. Что греха таить: после развертывания цикла качество кода ухудшилось. Однако любой подход к проектированию предполагает поиск компромиссных решений, и, даже если конкретная методика обычно плоха, в определенных об# стоятельствах она может стать оптимальной. Вот результаты развертывания цикла: Время выполнения Время выполнения Экономия Язык кода до оптимизации оптимизированного кода времени C++ 1,75 1,15 34% Java 1,01 0,581 43% PHP 5,33 4,49 16% Python 2,51 3,21 #27% Примечание: тестирование выполнено для случая count = 100. Возможность ускорения кода на 16–43% заслуживает внимания, хотя, как пока# зывает тест кода, написанного на Python, тут тоже не все однозначно. Главная опасность при развертывании цикла — ошибка завышения или занижения на единицу в коде, обрабатывающем последнюю итерацию. Что, если мы продолжим развертывание цикла? Принесет ли дополнительную выгоду двойное развертывание? Пример двукратного развертывания цикла (Java) i = 0; while ( i < count 2 ) { a[ i ] = i; a[ i + 1 ] = i+1; a[ i + 2 ] = i+2; i = i + 3; } if ( i <= count 1 ) { a[ count 1 ] = count 1; } if ( i == count 2 ) { a[ count 2 ] = count 2; } > 606 ЧАСТЬ V Усовершенствование кода Развертывание цикла во второй раз привело к таким результатам: Время выполнения Время выполнения кода после второго Экономия Язык кода до оптимизации развертывания цикла времени C++ 1,75 1,01 42% Java 1,01 0,581 43% PHP 5,33 3,70 31% Python 2,51 2,79 #12% Примечание: тестирование выполнено для случая count = 100. Итак, дальнейшее развертывание цикла может принести дополнительную пользу, а может и не принести, как показывает случай языка Java. В то же время сложность кода быстро возрастает. Если предыдущий фрагмент не кажется вам таким уж сложным, вспомните, что в самом начале он был циклом из пяти строк, и сами оцените компромисс между производительностью и удобочитаемостью. Минимизация объема работы, выполняемой внутри циклов Одной из методик повышения эффективности циклов является минимизация объема работы, выполняемой внутри цикла. Если вы можете вычислить выраже# ние или его часть вне цикла и использовать внутри цикла результат вычисления, сделайте это. Это хорошая методика программирования, которая иногда улучша# ет удобочитаемость кода. Допустим, у вас есть цикл, включающий сложное выражение с указателями: Пример цикла, включающего сложное выражение с указателями (C++) for ( i = 0; i < rateCount; i++ ) { netRate[ i ] = baseRate[ i ] * rates>discounts>factors>net; } Присвоив результат выражения удачно названной переменной, вы улучшите удо# бочитаемость кода, а может, и ускорите его выполнение: Пример упрощения сложного выражения с указателями (C++) quantityDiscount = rates>discounts>factors>net; for ( i = 0; i < rateCount; i++ ) { netRate[ i ] = baseRate[ i ] * quantityDiscount; } Дополнительная переменная quantityDiscount (оптовая скидка) ясно показывает, что элементы массива baseRate умножаются на показатель скидки. В первом фраг# менте это совсем не было очевидно. Кроме того, вынесение сложного выражения за пределы цикла устраняет три разыменования указателей при каждой итерации, что приводит к таким результатам: ГЛАВА 26 Методики оптимизации кода 607 Время выполнения Время выполнения Экономия Язык кода до оптимизации оптимизированного кода времени C++ 3,69 2,97 19% C# 2,27 1,97 13% Java 4,13 2,35 43% Примечание: тестирование выполнено для случая rateCount = 100. За исключением компилятора Java экономия времени не так уж и велика, поэто# му при первоначальном кодировании вы можете применить любую методику, улучшающую удобочитаемость кода, и отложить работу над быстродействием на потом. Сигнальные значения Если цикл включает проверку сложного условия, время его выполнения часто можно сократить, упростив проверку. В случае циклов поиска это можно сделать, использовав сигнальное значение (sentinel value) — значение, которое распола# гается сразу после окончания диапазона поиска и непременно завершает поиск. Классический пример сложной проверки, которую можно упростить с помощью сигнального значения, — условие цикла поиска, включающее проверки обнару# жения нужной переменной и выхода за пределы диапазона поиска. Вот код тако# го цикла: Пример проверки сложного условия цикла (C#) found = FALSE; i = 0; Проверка сложного условия. while ( ( !found ) && ( i < count ) ) { if ( item[ i ] == testValue ) { found = TRUE; } else { i++; } } if ( found ) { При каждой итерации этого цикла проверяются два условия: !found и i < count. Проверка !found служит для определения того, найден ли нужный элемент. Про# верка i < count нужна для предотвращения выхода за пределы массива. Кроме того, внутри цикла проверяются отдельные значения массива item[], так что на самом деле при каждой итерации цикла выполняются три проверки. > 608 ЧАСТЬ V Усовершенствование кода Этот вид циклов поиска позволяет объединить три проверки и выполнять при каждой итерации только одну проверку: для этого нужно поместить в конце диа# пазона поиска «сигнальное значение», завершающее цикл. В нашем случае мож# но просто присвоить искомое значение элементу, располагающемуся сразу пос# ле окончания диапазона поиска (объявляя массив, не забудьте выделить место для этого элемента). Далее вы проверяете по очереди каждый элемент: если вы дос# тигаете сигнального значения, значит, нужного вам значения в массиве нет. Вот соответствующий код: Пример использования сигнального значения для ускорения цикла (C#) // Установка сигнального значения с сохранением начальных значений. initialValue = item[ count ]; Не забудьте зарезервировать в конце массива место для сигнального значения. item[ count ] = testValue; i = 0; while ( item[ i ] != testValue ) { i++; } // Обнаружено ли значение? if ( i < count ) { Если item содержит целые числа, выгода может быть весьма существенной: Время выполнения Время выполнения оптимизированного Экономия Соотношение Язык кода до оптимизации кода времени быстродействия C# 0,771 0,590 23% 1,3:1 Java 1,63 0,912 44% 2:1 Visual Basic 1,34 0,470 65% 3:1 Примечание: поиск выполнялся в массиве из 100 целых чисел. Результаты, полученные для Visual Basic, особенно впечатляют, но и остальные тоже очень неплохи. Однако при изменении типа массива результаты также изменя# ются. Если item включает числа с плавающей запятой, результаты таковы: Время выполнения Время выполнения Экономия Язык кода до оптимизации оптимизированного кода времени C# 1,351 1,021 24% Java 1,923 1,282 33% Visual Basic 1,752 1,011 42% Примечание: поиск выполнялся в массиве из 100 четырехбайтовых чисел с плаваю# щей запятой. > ГЛАВА 26 Методики оптимизации кода 609 Как обычно, многое зависит от языка. Сигнальное значение можно использовать почти в любой ситуации, требующей выполнения линейного поиска, причем не только в массивах, но и в связных спис# ках. Вы только должны тщательно выбирать сигнальные значения и с осторож# ностью включать их в структуры данных. Вложение более ресурсоемкого цикла в менее ресурсоемкий Если вы имеете дело с вложенными циклами, подумайте, какой из них должен быть внешним, а какой внутренним. Вот пример вложенного цикла, который можно улучшить: Пример вложенного цикла, который можно улучшить (Java) for ( column = 0; column < 100; column++ ) { for ( row = 0; row < 5; row++ ) { sum = sum + table[ row ][ column ]; } } Ключ к улучшению цикла в том, что внешний цикл состоит из гораздо большего числа итераций, чем внутренний. С выполнением любого цикла связаны наклад# ные расходы: в начале цикла индекс должен быть инициализирован, а при каж# дой итерации — увеличен и проверен. Общее число итераций равно 100 для внеш# него цикла и 100 * 5 = 500 для внутреннего цикла, что дает в сумме 600 итераций. Просто поменяв местами внешний и внутренний циклы, вы можете снизить чис# ло итераций внешнего цикла до 5, тогда как число итераций внутреннего цикла останется тем же. В итоге вместо 600 итераций будут выполнены только 505. Можно ожидать, что перемена циклов местами приведет примерно к 16%#ому улучшению: (600 – 505) / 600 = 16%. На самом деле результаты таковы: Время выполнения Время выполнения Экономия Язык кода до оптимизации оптимизированного кода времени C++ 4,75 3,19 33% Java 5,39 3,56 34% PHP 4,16 3,65 12% Python 3,48 3,33 4% Значительные различия в очередной раз доказывают, что по поводу следствий оптимизации нельзя сказать ничего определенного, не оценив их в конкретной среде. Снижение стоимости операций Под снижением стоимости (strength reduction) понимают замену дорогой опера# ции на более дешевую, например, умножения на сложение. Иногда внутри цикла выполняется умножение индекса на какие#то другие значения. Сложение обычно выполняется быстрее, чем умножение, и, если вы можете вычислить то же число, 610 ЧАСТЬ V Усовершенствование кода заменив умножение на прибавление значения при каждой итерации цикла, это скорее всего приведет к ускорению выполнения кода. Вот пример кода, основан# ного на умножении: Пример умножения с использованием индекса цикла (Visual Basic) For i = 0 to saleCount 1 commission( i ) = (i + 1) * revenue * baseCommission * discount Next Этот код прост, но дорог. В то же время цикл можно переписать так, чтобы при каждой итерации выполнялось более дешевое сложение: Пример замены умножения на сложение (Visual Basic) incrementalCommission = revenue * baseCommission * discount cumulativeCommission = incrementalCommission For i = 0 to saleCount 1 commission( i ) = cumulativeCommission cumulativeCommission = cumulativeCommission + incrementalCommission Next Этот вид изменения похож на купон, предоставляющий скидку со стоимости цикла. В первоначальном коде при каждой итерации выполнялось умножение выраже# ния revenue * baseCommission * discount на счетчик цикла, увеличенный на едини# цу: сначала на 1, затем на 2, затем на 3 и т. д. В оптимизированном коде значение выражения revenue * baseCommission * discount присваивается переменной incre% mentalCommission. После этого при каждой итерации цикла значение incremental% Commission прибавляется к cumulativeCommission. При первой итерации оно при# бавляется один раз, при второй — два, при третьей — три и т. д. Эффект тот же, что и при умножении incrementalCommission на 1, на 2, на 3 и т. д., но оптими# зированный вариант дешевле. Чтобы этот вид оптимизации оказался возможным, первоначальное умножение должно зависеть от индекса цикла. В данном примере индекс цикла был единствен# ной изменяющейся частью выражения, поэтому мы и смогли сделать выражение более эффективным. Вот к чему это привело: Время выполнения Время выполнения Экономия Язык кода до оптимизации оптимизированного кода времени C++ 4,33 3,80 12% Visual Basic 3,54 1,80 49% Примечание: тестирование выполнено для saleCount = 20. Все используемые в вычис# лении переменные были переменными с плавающей запятой. ГЛАВА 26 Методики оптимизации кода 611 26.3. Изменения типов данных Изменение типов данных может быть эффективным способом сокращения кода и повышения его быстродействия. Проектирование структур данных в этой кни# ге не рассматривается, но умеренные изменения реализации отдельных типов данных также могут повышать производительность. Ниже описано несколько способов оптимизации типов данных. Использование целых чисел вместо чисел с плавающей запятой Сложение и умножение целых чисел, как правило, выпол# няются быстрее, чем аналогичные операции над числами с плавающей запятой. Например, циклы выполняются быст# рее, если индекс имеет целочисленный тип. Пример неэффективного цикла с индексом с плавающей запятой (Visual Basic) Dim x As Single For x = 0 to 99 a( x ) = 0 Next Сравните этот код с аналогичным циклом, в котором явно используется целочис# ленный индекс: Пример эффективного цикла с целочисленным индексом (Visual Basic) Dim i As Integer For i = 0 to 99 a( i ) = 0 Next Насколько выгоден этот вид оптимизации? Вот результаты выполнения указанных фрагментов кода Visual Basic и аналогичных циклов, написанных на C++ и PHP: Соотношение Время выполнения Время выполнения Экономия быстродействия Язык кода до оптимизации оптимизированного времени кода C++ 2,80 0,801 71% 3,5:1 PHP 5,01 4,65 7% 1:1 Visual Basic 6,84 0,280 96% 25:1 Использование массивов с минимальным числом измерений Использовать массивы, имеющие несколько измерений, накладно. Если вы сможете структурировать данные так, чтобы их можно было хранить в одномерном, а не двумер# Перекрестная ссылка Об ис- пользовании целых чисел и чи- сел с плавающей запятой см. главу 12. Перекрестная ссылка О масси- вах см. раздел 12.8. 612 ЧАСТЬ V Усовершенствование кода ном или трехмерном массиве, вы скорее всего ускорите выполнение программы. Допустим, у вас есть подобный код инициализации массива: Пример стандартной инициализации двумерного массива (Java) for ( row = 0; row < numRows; row++ ) { for ( column = 0; column < numColumns; column++ ) { matrix[ row ][ column ] = 0; } } При инициализации массива из 50 строк и 20 столбцов этот код выполняется вдвое дольше, чем код инициализации аналогичного одномерного массива, сгенериро# ванный тем же компилятором Java. Вот как выглядел бы исправленный код: Пример одномерного представления массива (Java) for ( entry = 0; entry < numRows * numColumns; entry++ ) { matrix[ entry ] = 0; } А вот результаты тестирования этого кода и похожего кода, написанного на не# скольких других языках: Время выполнения Время выполнения оптимизированного Экономия Соотношение Язык кода до оптимизации кода времени быстродействия C++ 8,75 7,82 11% 1:1 C# 3,28 2,99 9% 1:1 Java 7,78 4,14 47% 2:1 PHP 6,24 4,10 34% 1,5:1 Python 3,31 2,23 32% 1,5:1 Visual Basic 9,43 3,22 66% 3:1 Примечание: временные показатели, указанные для Python и PHP, получены в резуль# тате более чем в 100 раз меньшего числа итераций, чем показатели, приведенные для других языков, поэтому их непосредственное сравнение недопустимо. Результаты этого вида оптимизации прекрасны для Visual Basic и Java, хороши для PHP и Python, но довольно заурядны для C++ и C#. Правда, время выполнения не# оптимизированного кода C# было лучшим, так что на это едва ли можно жаловаться. Широкий разброс результатов лишь подтверждает недальновидность слепого сле# дования любым советам по оптимизации. Не испытав методику в конкретных об# стоятельствах, ни в чем нельзя быть уверенным. Минимизация числа обращений к массивам Кроме минимизации числа обращений к двумерным или трехмерным массивам часто выгодно минимизировать число обращений к массивам вообще. Подходя# щий кандидат для применения этой методики — цикл, в котором повторно ис# ГЛАВА 26 Методики оптимизации кода 613 пользуется один и тот же элемент массива. Вот пример необязательного обраще# ния к массиву: Пример необязательного обращения к массиву внутри цикла (C++) for ( discountType = 0; discountType < typeCount; discountType++ ) { for ( discountLevel = 0; discountLevel < levelCount; discountLevel++ ) { rate[ discountLevel ] = rate[ discountLevel ] * discount[ discountType ]; } } При изменении индекса discountLevel по мере выполнения внутреннего цикла обращение к массиву discount[ discountType ] остается все тем же. Вы можете вы# нести его за пределы внутреннего цикла, и тогда у вас будет одно обращение к массиву на одну итерацию внешнего, а не внутреннего цикла. Вот оптимизиро# ванный код: Пример вынесения обращения к массиву за пределы цикла (C++) for ( discountType = 0; discountType < typeCount; discountType++ ) { thisDiscount = discount[ discountType ]; for ( discountLevel = 0; discountLevel < levelCount; discountLevel++ ) { rate[ discountLevel ] = rate[ discountLevel ] * thisDiscount; } } Результаты: Время выполнения Время выполнения Экономия Язык кода до оптимизации оптимизированного кода времени C++ 32,1 34,5 #7% C# 18,3 17,0 7% Visual Basic 23,2 18,4 20% Примечание: тестирование выполнено для typeCount = 10 и levelCount = 100. Как обычно, результаты зависят от конкретного компилятора. Использование дополнительных индексов Использование дополнительного индекса предполагает добавление данных, свя# занных с основным типом данных и повышающих эффективность обращений к нему. Связанные данные можно добавить к основному типу или хранить в парал# лельной структуре. Индекс длины строки Примером использования дополнительного индекса может служить одна из форм представления строк. В языке C строки заканчиваются нулевым байтом. Что каса# ется строк Visual Basic, то их длина хранится в начальном байте. Чтобы опреде# лить длину строки C, нужно начать с начала строки и продвигаться по ней, под# считывая байты, до достижения нулевого байта. Для определения длины строки Visual Basic, нужно просто прочитать байт длины. Байт длины строки Visual Basic 614 ЧАСТЬ V Усовершенствование кода — наглядный пример дополнения типа данных индексом, ускоряющим выполне# ние определенных операций, таких как вычисление длины строки. Идею индексации длины можно приспособить к любому типу данных перемен# ной длины. Слежение за длиной структуры часто — более эффективный подход, чем вычисление длины каждый раз, когда она требуется. Независимая параллельная структура индексации Иногда выгоднее работать с индексом типа данных, а не с самим типом данных. Если элементы типа данных велики или их накладно перемещать (скажем, на диск), сортировка и поиск по индексам будут выполняться быстрее, чем непосредственные операции над данными. Если каждый элемент данных велик, вы можете создать вспомогательную структуру, состоящую из ключевых значений и указателей на подробную информацию. Если различие размеров элемента структуры данных и элемента вспомогательной структуры достаточно велико, элемент#ключ можно хранить в памяти, а сами данные — на внешнем носителе. Все операции поиска и сортировки будут выполняться в памяти, а к диску можно будет обращаться толь# ко после определения точного расположения нужного вам элемента. Кэширование Кэширование — это такой способ хранения нескольких значений, при котором значения, используемые чаще всего, получить легче, чем значения, используемые реже. Так, если программа случайным образом читает записи с диска, метод мо# жет хранить в кэше записи, считываемые наиболее часто. Получив запрос запи# си, метод проверяет, имеется ли запись в кэше. Если да, запись возвращается не# посредственно из памяти, а не считывается с диска. Кэширование можно применять и в других областях. В программе обработки шрифтов Microsoft Windows узким местом было получение ширины символа при его отображении на экране. Кэширование ширины символа, использованного последним, позволило примерно вдвое ускорить отображение. Вы можете кэшировать и результаты ресурсоемких вычислений, особенно если их параметры просты. Пусть, например, вам нужно найти длину гипотенузы пря# моугольного треугольника по длинам двух катетов. Простая реализация этого метода была бы примерно такой: Пример метода, напрашивающегося на кэширование (Java) double Hypotenuse( double sideA, double sideB ) { return Math.sqrt( ( sideA * sideA ) + ( sideB * sideB ) ); } Если вы знаете, что те же значения скорее всего будут переданы в метод повтор# но, их можно кэшировать: |