Файл: Think likea programmer.pdf

88 Глава 3
фразы на простом английским представляют собой замечательные комментарии. Я продемонстрировал это в приведенном здесь коде.
Вы можете забыть точный смысл условных выражений в инструк- ции if
Y
, однако комментарий на предыдущей строке прекрасно все проясняет
X
Что касается самого кода, он справляется со своей задачей, од- нако помните, что это требует группировки наших данных опроса.
Группировка этих данных сама по себе может представлять пробле- му за исключением случая, когда мы сортируем массив. На самом деле мы не нуждаемся в сортировке, однако сортировка осуществит не- обходимую группировку. Поскольку мы не собираемся производить какой-то особый вид сортировки, давайте просто добавим вызов функции qsort в начало нашего кода: qsort(surveyData, ARRAY_SIZE, sizeof(int), compareFunc);
Обратите внимание, что мы используем тот же метод compareFunc, который писали ранее для использования с функцией qsort. Доба- вив этап сортировки, мы получили полное решение исходной зада- чи. Итак, работа выполнена. Не так ли?
Рефакторинг
Некоторые программисты говорят о коде, который «дурно пахнет».
Они говорят о работающем коде, в котором нет ошибок, но есть какие-то проблемы. Иногда это означает, что код слишком сложен или предусматривает слишком много специфических случаев, что затрудняет его модификацию и обслуживание. Бывает, что код не так эффективен, как мог бы быть, и хотя он подходит для решения тестовых задач, программист опасается, что производительность снизится, когда дело дойдет до более масштабных задач. Именно это заботит меня в данном случае. В нашем примере с крошечным масси- вом сортировка осуществляет почти мгновенно, но что, если массив будет огромным? Кроме того, я знаю, что алгоритм быстрой сорти- ровки, который может использовать функция qsort, имеет самую низкую производительность, когда в массиве присутствует много по- вторяющихся значений, и весь смысл этой задачи состоит в том, что все наши значения находятся в диапазоне от 1 до 10. Поэтому я пред- лагаю произвести рефакторинг кода. Рефакторинг означает улучше- ние работающего кода, изменение не того, что он делает, а того, как он это делает. Мне нужно решение, которое было бы эффективным даже для огромных массивов, допуская, что их значения находятся в диапазоне от 1 до 10.
Давайте еще раз подумаем об операциях, которые мы умеем про- изводить с помощью массивов. Мы уже изучили несколько версий кода для нахождения наибольшего значения. Мы знаем, что при- менение этого кода непосредственно к нашему массиву surveyData не даст нужных результатов. Есть ли массив, к которому мы могли

Решение задач с массивами 89
бы применить имеющийся у нас вариант кода для нахождения наи- большего значения, чтобы определить моду среди значений данных опроса? Ответ — да. Нужный нам массив — это гистограмма масси- ва surveyData. Гистограмма представляет собой график, показываю- щий, как часто различные значения появляются в наборе данных, на котором он основан. Наш массив будет представлять собой набор данных для такой гистограммы. Другими словами, мы будем хранить в массиве из 10 элементов данные о том, как часто каждое из значе- ний от 1 до 10 встречается в массиве surveyData. Ниже показан код для создания гистограммы: const int MAX_RESPONSE = 10;
X int histogram[MAX_RESPONSE];
Y for (int i = 0; i < MAX_RESPONSE; i++) {
histogram[i] = 0;
}
Z for (int i = 0; i < ARRAY_SIZE; i++) {
[ histogram[surveyData[i] — 1]++;
}
В первой строке мы объявляем массив для хранения данных ги- стограммы
X
. Вы заметите, что мы объявляем массив с 10 элемен- тами, но значения данных опроса находятся в диапазоне от 1 до
10, а индексы для элементов этого массива — в диапазоне от 0 до
9. Таким образом, мы должны будем внести коррективы, поместив количество значений 1 в histogram[0] и так далее. (Некоторые программисты могут объявить массив с 11 элементами, оставив позицию[0] неиспользованной, чтобы индекс каждого элемента фактически соответствовал его позиции.) Мы явно инициализиру- ем значения массива нулем с помощью цикла
Y
, после чего гото- вы подсчитать количество каждого значения в массиве surveyData с помощью другого цикла
Z
. Инструкцию внутри цикла
[
следует прочитать очень тщательно; значение в текущей позиции массива surveyData говорит о том, какую позицию в массиве histogram необ- ходимо инкрементировать. Чтобы было ясно, давайте рассмотрим пример. Предположим, что i присвоено значение 42. Мы обраща- емся к surveyData[42] и обнаруживаем, допустим, значение 7. Та- ким образом, нам нужно инкрементировать значение счетчика 7.
Мы вычитаем 1 из 7, чтобы получить 6, поскольку счетчик значе- ний 7 находится в позиции [6] в массиве histogram, итак, мы уве- личиваем на 1 значение histogram[6].
Теперь, когда данные гистограммы на месте, мы можем запи- сать остальную часть кода. Обратите внимание, что код гистограм- мы создавался отдельно, чтобы его можно было отдельно протести- ровать. Невозможно сэкономить время, записывая весь код сразу в ситуации, когда задача легко разделяется на части, которые мо- гут быть написаны и протестированы отдельно. Проверив приве- денный выше код, мы теперь ищем наибольшее значение в массиве histogram:

90 Глава 3
X int mostFrequent = 0;
for (int i = 1; i < MAX_RESPONSE; i++) {
if (histogram[i] >
Y histogram[mostFrequent]) Z mostFrequent = i;
}
[ mostFrequent++;
Несмотря на то, что этот код представляет собой адаптацию кода для нахождения наибольшего значения, он имеет некоторые отличия. Хотя мы ищем наибольшее значение в массиве histogram, в конечном итоге, нам нужно не само значение, а его позиция. Други- ми словами, в случае с массивом в примере мы хотим знать, что зна- чение 3 встречается чаще, чем любое другое среди данных опроса, однако фактическое количество раз, когда оно встречается, для нас не важно. Таким образом, mostFrequent будет обозначать позицию наибольшего значения в массиве histogram, а не само это значение.
Поэтому мы инициализируем его 0
X
, а не значением в позиции [0].
Это также означает, что в инструкции if мы производим сравнение с histogram[mostFrequent]
Y
, а не с mostFrequent, и присваиваем зна- чение i, а не histogram[i] переменной mostFrequent
Z
при нахожде- нии большего значения. Наконец, мы инкрементируем переменную mostFrequent
[
. Эта операция противоположна тому, что мы делали в предыдущем цикле, вычитая 1, чтобы получить правильную по- зицию в массиве. Например, если значение mostFrequent сообщает нам, что наивысшей позицией массива является 5, это означает, что наиболее часто встречающейся записью среди данных опроса явля- ется 6.
Решение с использованием гистограммы масштабируется линей- но с увеличением числа элементов в нашем массиве surveyData, что соответствует нашим самым смелым ожиданиям. Следовательно, это решение лучше, чем наш исходный подход. Это не означает, что первый подход был ошибкой или пустой тратой времени. Конечно, можно было бы написать этот код, не прибегая к предыдущей вер- сии, и нас можно простить за желание направиться к месту назначе- ния напрямую, а не в обход. Однако я бы предостерег от битья себя по лбу в тех случаях, когда первое решение оказывается не оконча- тельным. Написание оригинальной программы (помните, что это означает оригинальной для пишущего ее программиста) — это процесс обучения, который не может всегда продвигаться вперед прямоли- нейно. Кроме того, часто бывает так, что более длинный путь при решении одной задачи помогает найти более короткий путь для ре- шения задач в будущем. В данном конкретном случае обратите вни- мание на то, что наше исходное решение (хотя оно не масштабиру- ется достаточно хорошо для нашей конкретной задачи) могло бы быть правильным, если бы данные опроса не были строго ограниче- ны небольшим диапазоном 1 — 10. Или предположим, что в дальней- шем вам потребуется написать код для нахождения медианы в наборе целочисленных значений ( медиана — это значение, находящиеся в середине так, что половина значений набора больше него, а другая

Решение задач с массивами 91
половина меньше). Подход с использованием гистограммы никуда вас не приведет в случае с медианой, чего нельзя сказать о нашем первом подходе для нахождения моды.
Урок в данном случае заключается в том, что долгий путь — это не пустая трата времени, если вы научились чему-то такому, чему не на- учились бы, пойдя коротким путем. Это еще одна причина методич- но хранить весь код, который вы пишете, чтобы вы могли позднее легко найти его и повторно использовать. Даже код, который оказы- вается «тупиком», может стать ценным ресурсом.
Массивы фиксированных данных
В большинстве задач массив представляет собой хранилище данных, внешних по отношению к программе, например введенных пользо- вателем, хранящихся на локальном диске или полученных с серве- ра. Однако чтобы получить максимальную отдачу от такого инстру- мента, как массив, вам нужно уметь распознавать другие ситуации, в которых его можно использовать. Часто бывает полезно создать массив, значения которого остаются неизменными после инициали- зации. Такой массив может допускать использование простого цик- ла или даже осуществление прямого поиска в массиве с целью заме- ны всего блока управляющих инструкций.
В окончательном коде для решения задачи декодирования со- общения в конце предыдущей главы мы использовали инструкцию switch для замены декодированного входного числа (в диапазоне от
1 до 8) соответствующим знаком препинания, поскольку связь между числом и символом была произвольной. Несмотря на то, что это сра- ботало, данная часть кода оказалась длиннее, чем эквивалентный код для режимов верхнего и нижнего регистра, кроме того, этот код не будет хорошо масштабироваться при увеличении количества знаков препинания. Для решения этой задачи вместо инструкции switch мы можем использовать массив. Во-первых, мы должны на постоянной основе назначить массиву знаки препинания в том же порядке, в ка- ком они появляются в схеме кодирования:
const char punctuation[8] = {'!', '?', ',', '.', ' ', ';', '"', '\''};
Обратите внимание на то, что этот массив объявлен как констан- та, поскольку значения в нем никогда не изменятся. Благодаря этому объявлению мы можем заменить весь код инструкции switch одной инструкцией присваивания, которая ссылается на массив: outputCharacter = punctuation[number — 1];
Поскольку входное число находится в диапазоне от 1 до 8, а ну- мерация элементов массива начинается с 0, то нам необходимо вы- честь 1 из входного числа, прежде чем сослаться на массив. Эта кор- ректировка аналогична той, что мы делали в версии программы

92 Глава 3
для нахождения моды с использованием гистограммы. Вы можете использовать тот же массив, чтобы пойти в другом направлении.
Предположим, что вместо декодирования сообщения нам нужно его закодировать, т.е. дан ряд символов, которые требуется преоб- разовывать в числа, которые могут быть декодированы с использо- ванием правил исходной задачи. Чтобы преобразовать знак препи- нания в соответствующее ему число, мы должны найти этот символ в массиве. Это операция извлечения, выполняемая с использованием приема последовательного поиска. Предположив, что символ дол- жен быть преобразован и сохранен в переменной targetValue масси- ва char, мы могли бы адаптировать код для осуществления последо- вательного поиска следующим образом:
const int ARRAY_SIZE = 8;
int targetPos = 0;
while (punctuation[targetPos] != targetValue && targetPos < ARRAY_SIZE)
targetPos++;
int punctuationCode = targetPos + 1;
Обратите внимание на то, что так же, как нам пришлось вычи- тать 1 из значения number в предыдущем примере, чтобы получить правильную позицию в массиве, в данном примере необходимо до- бавить 1 к позиции массива, чтобы получить код из знаков препина- ния, преобразуя значение массива в диапазоне от 0 до 7 в значения нашего кода из знаков препинания в диапазоне от 1 до 8. Хотя этот код состоит не из одной строки, он все-таки намного проще, чем се- рия операторов switch, и хорошо масштабируется. Если бы мы удво- или количество знаков препинания в нашей схеме кодирования, это привело бы к удвоению количества элементов массива, однако длина кода осталась бы прежней.
В общем случае массивы const могут использоваться в качестве таблиц поиска вместо громоздкой серии управляющих инструк- ций. Предположим, вы пишете программу для вычисления стоимо- сти бизнес-лицензии, которая зависит от значения валового объ- ема продаж.
Табл. 3.1. Стоимость бизнес-лицензии
j=2%!, K,ƒ…“=
c!=…, = %KA= C!% =›
q2%,%“2 , …ƒ,,
I
$ 0
$ 25
II
$ 50000
$ 200
III
$ 150000
$ 1000
IV
$ 500000
$ 5000
В этой задаче мы могли бы использовать массивы как для опреде- ления категории бизнеса на основе валовых продаж компании, так и для присвоения стоимости лицензии на основе категории бизнеса.
Предположим, что в переменной типа double с именем grossSales хранится значение валового объема продаж компании и, исходя из этого показателя объема продаж, мы хотим присвоить подходящие значения переменным int category и double cost:

Решение задач с массивами