Керниган Б., Пайк Р. Практика программирования
Подождите немного. Документ загружается.
В чем бы ни крылась причина несоответствия, комментарий, противоречащий коду,
сильно сбивает читателя с толку. Страшно представить, сколько времени и сил было
потрачено на отладку программ впустую только из-за того, что некорректный или
устаревший комментарий принимался на веру. Поэтому запомните: каждый раз,
изменив код, убедитесь в том, что комментарии ему
соответствуют.
Комментарии должны не только соответствовать коду, но и. поддерживать его. В
следующем примере комментарий помещен грамотно — он поясняет назначение
следующих за ним строк, но противоречит коду, поскольку в нем говорится о
переводе строки, в то время как код относится к пробелам:
time(&now);
strcpy(date, ctime(&now));
/* избавляемся от замыкающего символа
перевода строки,
скопированного
из ctime */ 1 = .0;
while(date[i] >= ' ') i++; date[i] - 0;
Первое, что надо сделать, это переписать код в более привычном идиоматическом
виде:
time(&now);
strcpy(date, ctime(&now));
/* избавляемся от замыкающего символа перевода строки,
скопированного из ctime */ for (i = 0; date[i] != Дп'; i++)
date[i] = '\0';
Теперь код и комментарий соответствуют друг другу, но и тот и другой можно
улучшить, сделав их более прямолинейными. Задача фрагмента — удалить символ
перевода строки, который
функция ctime помещает в конец возвращаемой ею
строки. Собственно, это комментарий и должен сообщить, а код сделать:
time(&now);
strcpy(date, ctime(&now));
/* ctimeQ помещает символ перевода строки в конец
возвращаемой строки; его надо удалить'*/
date[strlen(date)-1] =' \О';
Последнее выражение — идиома языка С, предназначенная для удаления
последнего символа из строки. Теперь наш код стал коротким, стандартизованным и
понятным,
а комментарий поясняет причину, по которой в этом коде возникла
необходимость.
Вносите ясность, а не сумятицу. Комментарии предназначены для того, чтобы
помочь читателю разобраться в критических местах кода, а не для того, чтобы
создавать дополнительные препятствия. В следующем примере выполнены наши
рекомендации по комментированию функций и разъяснению необычных участков
кода; однако
речь идет о функции strcmp, и все такие необычные участки не имеют
никакого отношения к тому, что на самом деле нужно сделать — реализовать
стандартный и всем привычный интерфейс:
? int strcmp(char *s1, char *s2)
? /* процедура сравнения строк возвращает -1, если */ /*
s1 стоит выше
s2 в списке по возрастанию, */ /* 0, если строки равны, и 1,
если s1 ниже
s2 */
? {
? while(*s1==*s2) {
? if(*s1=='\0') return(O);
? S1++;
? s2++;
? }
if(*s1>*s2) return(l);
? return(-1);
? }
Если нескольких слов недостаточно для пояснения происходящего, то скорее всего
код стоит переписать. В рассматриваемом примере код, наверное, можно несколько
улучшить, но главная беда кроется все же в комментарии, который почти того же
размера, что и вся реализация, да к тому же еще и не совсем понятен
(что значит
"выше", например?). Мы так подробно разбираем этот пример, чтобы подчеркнуть:
если во фрагменте реализуется стандартная функция, комментарий должен лишь
обобщать сведения о ее поведении и сообщать, откуда взялось ее определение, вот
и все:
/* strcmp: возвращает <
0 если s1<s2,
> 0 если s1>s2
и 0 если s1=s2 */
/* ANSI С, раздел 4.11,4.2 */ ,
int strcmp(const char *s1, const char *s2)
{
....
}
Студентам внушают, что
комментировать надо все подряд; профессиональным
программистам часто вменяется в обязанность комментировать весь созданный ими
код. Однако если слепо следовать правилам, то смысл написания комментариев
может потеряться. Комментарии должны помогать читателю разобраться в тех
частях программы, смысл и назначение которых нельзя (или просто трудно) понять
из самого кода. Всюду, где это возможно
, старайтесь писать код, который было бы
просто понять; чем лучше вам это удастся, тем меньше комментариев вам
потребуется. Хороший код меньше нуждается в комментариях, чем плохой.
Упражнение 1-11
Прокомментируйте эти комментарии.
?void diet::insert(string& w)
?// возвращает 1, если w в словаре, в противном случае - О
?if (п > МАХ || п % 2 > 0) // проверка на четность
?// Пишем сообщение
?// Увеличить счетчик
строк для каждой написанной строки
? void writejnessage()
? // увеличить счетчик строк
? line_number =,line_number + 1;
? fprintf(fout, "%d %s\n%d %s\n%d %s\rv",
? line^number, HEADER,
7 line_number + 1, BODY,
? line_number + 2, TRAILER);
? // увеличить счетчик строк
? line_number = line_number + 2;
7 }
Стоит ли так беспокоиться?
В этой главе мы поговорили об основных составляющих хорошего стиля
программирования: информативных именах, ясности в выражениях, прозрачной
логике, читабельности кода и комментариев, а также обсудили важность
использования соглашений и идиоматических блоков для достижения всего
вышеперечисленного.
Однако стоит ли так беспокоиться о стиле? Кому какая разница, как программа
выглядит изнутри, если она
работает? Не слишком ли много времени придется
тратить на ее "причесывание"? Не слишком ли расплывчаты рекомендуемые
правила?
Ответ на эти вопросы состоит в следующем: хорошо и красиво написанный код
проще читать и воспринимать; в нем, без сомнения, содержится меньше ошибок, и
он почти наверняка будет короче, чем код, бездумно скомпонованный
и оставленный
без улучшений. Когда программа пишется в спешке, когда и так трудно успеть к
установленным срокам, кажется вполне естественным не обращать внимания на
стиль, оставив заботы о нем на потом. Однако подобное решение может оказаться
весьма накладным. Некоторые примеры из этой главы уже дали вам представление
о том, что может
случиться, если пренебрегать хорошим стилем. Небрежно
оформленный код — плохой код, и не только потому, что выглядит он некрасиво и
читать его трудно; как правило, в таком коде содержатся и ошибки.
Основная мысль состоит в том, что хороший стиль должен просто войти в привычку.
Если вы будете задумываться о стиле при
написании кода, если вы будете
выкраивать время для того, чтобы проверять и улучшать его стиль, вы выработаете
у себя очень полезную привычку. После того как все это вы будете проделывать
автоматически, ваше подсознание позаботится о многих деталях, и даже код,
который вы будете писать в спешке, станет гораздо лучше.
Дополнительная литература
Как мы уже заявляли в начале главы, писать хороший код и просто хорошо писать
по-английски — достаточно схожие понятия. "Элементы стиля" В. Странка и Э. Б.
Уайта (W. Strunk, E. В. White. The Elements of Style. Allyn & Bacon) — самый хороший
из небольших учебников письменного английского.
Эта глава во многом взята из книги Брайана Кернигана и П. Дж. Пла-угера
"Элементы
стиля программирования" (Brian Kernighan, P. J. Plau-ger. The Elements of
Programming Style. McGraw-Hill, 1978). "Создание надежного кода" Стива Магьюира
(Steve Maguire. Writing Solid Code. Microsoft Press, 1993) — идеальный источник
советов по программированию. Кроме того, интересное обсуждение стиля имеется в
книгах Мак-Коннелла "Все о коде" (Steve McConnell. Code Complete. Microsoft Press,
1993) и Питера ван дер Линдена "Профессиональное программирование на С:
Секреты С" (Peter van der Linden. Expert С Programming: Deep С Secrets. Prentice Hall,
1994).
Алгоритмы и структуры данных
• Поиск
• Сортировка
• Библиотеки
• Быстрая сортировка на языке Java
• "О большое"
• Динамически расширяемые массивы
• Списки
• Деревья
• Хэш-таблицы
• Заключение
• Дополнительная литература
В конце концов, только знание инструментов и технологий обеспечит
правильное решение поставленной задачи, и только определенный
уровень опыта обеспечит устойчиво профессиональные результаты.
Реймонд Филдинг. Технология специальных эффектов в
кинематографе
Исследование алгоритмов и структур данных является одной из основ
программирования, а также богатым полем элегантных технологий и сложных
математических изысканий. И
это — что-то большее, чем развлечение для
теоретически подготовленных: хороший алгоритм или структура данных могут
позволить решить в течение нескольких секунд проблему, которая без них решалась
бы годы.
В таких специальных областях, как графика, базы данных, синтаксический разбор,
цифровой анализ и моделирование, возможность решения задачи целиком и
полностью зависит от наличия
специальных алгоритмов и структур данных. Если вы
разрабатываете программы в новых для вас областях программирования, то вы
должны выяснить, какие наработки уже существуют, иначе вы потратите свое время
впустую в попытках плохо сделать то, что уже кем-то было сделано хорошо.
Каждая программа зависит от алгоритмов и структур данных, но
редко бывает нужно
изобретать новые алгоритмы. Даже в сложной программе, например в компиляторе
или Web-браузере, структуры данных по большей части являются массивами,
списками, деревьями и хэш-таб-лицами. Когда программе нужна более изощренная
структура, она, скорее всего, будет основываться на этих более простых структурах.
Соответственно, задача программиста — знать, какие алгоритмы и
структуры
доступны, а также понимать, как выбрать среди них нужные.
Такова, вкратце, ситуация. Есть лишь горстка основных алгоритмов, которые
применяются практически в каждой программе, — это, прежде всего, поиск и
сортировка, и даже эти алгоритмы зачастую включены в библиотеки. Почти все
структуры данных также сделаны на основе нескольких фундаментальных структур.
Поэтому
материал данной главы знаком почти всем программистам. Мы написали
работающие версии программ, чтобы дискуссия была более конкретной, и при
желании вы можете обратиться непосредственно к исходному коду, но делайте это,
только если вы разобрались в том, что вам могут предложить ваш язык
программирования и его библиотеки.
Поиск
Ничто не сравнится с массивом, если нам нужно хранить статические табличные
данные. Инициализация во время компиляции делает задачу конструирования таких
массивов простой и легкой. (В Java инициализация происходит во время
выполнения, но это можно считать незначительной деталью реализации, пока
массивы не слишком велики.) В программе для распознания слов, слишком часто
употребляемых в
плохой прозе, мы можем написать:
char *flab[] = {
"actually",
"just",
"quite",
"really",
NULL
};
Функция поиска должна знать, сколько в массиве элементов. Один из способов
сообщить ей это — передать длину массива в виде аргумента; второй способ,
использованный здесь, — поместить в конце массива элемент-маркер NULL:
/* lookup: последовательный поиск слова в массиве */
int lookup(char *word, char *array[])
{
int i;
for (i = 0; array[i] != NULL; i++)
if (strcmp(word, array[i]) ==-
0) return i;
return -1;
}
В С и C++
для передачи в качестве параметра массив строк можно описать как char
*array[] или char **array. Эти две формы эквивалентны, но в первой сразу видно, как
будет использоваться параметр.
Предлагаемый поисковый алгоритм называется последовательным, поиском, потому
что он просматривает по очереди все элементы, сравнивая их с искомым. Когда
данных немного, последовательный поиск работает достаточно быстро.
Есть
стандартные библиотечные функции, которые выполняют последовательный поиск
для определенных типов данных. Например, в языках С и C++ функции st rch г и st
rst r ищут первое вхождение заданного символа или подстроки в строку, в Java у
класса String есть метод indexOf, а обобщенные функции поиска в C++ find
применимы к большинству типов данных. Если такая функция существует для
нужного
вам типа данных, то используйте ее.
Последовательный поиск достаточно прост, но время его работы прямо
пропорционально количеству данных, которые нужно просмотреть; удвоение
количества элементов приведет к удвоению времени на поиск, если искомого
элемента в массиве нет. Это линейное соотношение (время выполнения является
линейной функцией от размера данных), поэтому такой метод также
называется
линейным поиском.
Вот пример массива более реалистичного размера из программы, выполняющей
синтаксический разбор текста, написанного на HTML, где определены имена более
чем сотни отдельных символов:
typedef struct Nameval Nameval; struct Nameval {
char *name;
int value;
/* символы HTML, например AElig - лигатура1 А и Е.
*/ /* значения в кодировке
Unicode/18010646 */ Nameval htmlchars[] = {
"AElig", ОхООсб, /* лигатура А и Е
"Aacute", OxOOd, /* А с акцентом
"Acirc", OxOOc2, /* А с кружочком
/*...*/
"zeta", ОхОЗЬб, /* греческая дзета */
};
Для объемистого массива вроде этого более эффективно было бы использовать
двоичный поиск. Алгоритм двоичного поиска является систематизированной версией
поиска слова в словаре
. Проверяем средний элемент. Если это значение больше,
чем нужное, то ищем далее в первой части; в противном случае ищем во второй
части. Повторяем до тех пор, пока не найдем нужный элемент или не убедимся, что
его в массиве нет.
Для двоичного поиска таблица должна быть отсортирована, как в данном случае (
в
любом случае это полезно; люди тоже быстрее находят требуемое в
отсортированных таблицах), а также должно быть известно, сколько элементов в
таблице. Здесь может помочь макрофункция NELEMS из первой главы:
printf("Ta6лица HTML содержит %d слов\n", NELEMS(htmlchars));
Функция двоичного поиска для этой таблицы могла бы выглядеть так:
/* lookup: двоичный поиск имени name
в таблице tab;
возвращается индекс */
int lookup(char *name, Nameval tab[], int ntab) {
int low, high, mid, cmp;
low = 0;
high = ntab - 1;
while (low <= high) {
mid = (low + high) / 2;
cmp = strcmp(name, tab[mid].name);
if (cmp < 0)
high = mid - 1; else if (cmp > 0) low = mid + 1:
else /* совпадение
найдено */
return mid; } return -1;
/* совпадений нет */
Объединяя все это вместе, мы можем написать:
half = lookup("frac12", htmlchars, NElEMS(htmlchars));
для определения индекса, под которым символ 1/2 (одна вторая) стоит в массиве
htmlchars.
Двоичный поиск отбрасывает за каждый шаг половину данных, поэтому количество
шагов пропорционально тому, сколько раз мы можем поделить п на 2, пока у
нас не
останется один элемент. Без учета округления это число равно Iog2 п. Если у нас в
массиве 100"0 элементов, то линейный поиск займет до 1000 шагов, в то время как
двоичный — только около 10; при миллионе элементов линейный поиск займет
миллион шагов, а двоичный — 20. Очевидно, чем больше число элементов, тем
больше преимущество двоичного поиска. Начиная с некоторого зависящего от
реализации размера данных, двоичный поиск работает быстрее, чем линейный.
Сортировка
Двоичный поиск работает только в том случае, если элементы отсортированы. Если
по одному и тому же набору данных планируется неоднократный повторный поиск,
то выгоднее один раз отсортировать данные, а затем использовать двоичный поиск.
Если набор данных известен заранее, то он может быть отсортирован при написании
программы и проинициализирован во время компиляции
. Иначе придется
сортировать его во время выполнения программы.
Один из самых лучших алгоритмов сортировки — быстрая сортировка (quicksort),
которая была придумана в 1960 году Чарльзом Хоаром (С. A. R. Ноаге). Быстрая
сортировка — замечательный пример того, как можно избежать лишних вычислений.
Она работает при помощи разделения массива на большие и маленькие элементы:
выбрать один элемент массива ("
разделитель"):
разбить оставшиеся элементы на две группы:
"маленькие", то есть меньшие, чем разделитель,
"большие", то есть большие или равные разделителю,
рекурсивно отсортировать обе группы.
Когда этот процесс закончится, то массив будет отсортирован. Быстрая сортировка
работает быстро, потому что, как только мы узнаем, что элемент меньше, чем
разделитель, нам уже не
нужно его сравнивать с большими элементами;
аналогично, большие элементы не сравниваются с маленькими. Поэтому данный
алгоритм существенно быстрее, чем такие простые методы сортировки, как
сортировка вставкой или пузырьком, когда каждый элемент сравнивается напрямую
со всеми остальными.
Алгоритм быстрой сортировки практичен и эффективен; он хорошо изучен, и
существует множество его вариаций.
Версия, которую мы здесь представим,
является одной из самых простых реализаций, но, конечно, далеко не самой
быстрой.
Наша функция quicksort сортирует массив целых чисел:
/* quicksort: сортирует v[0]..v[n-1]
по возрастанию */ void quicksоrtClrrt
v[], int n)
> {
int i, last;
if (n <= 1) /* ничего не делать */
return;
swap(v, 0, rand() % n); /* поместить
разделитель в v[0] */ last = 0;
for (i = 1; i < n; i++) /* разделить */
if (v[i] < v[0])
swap(v, ++last, i);
swap(v, 0, last); /* сохранить разделитель */
quicksort(v, last); /* рекурсивно
отсортировать */ quicksort(v+last+1, n-last-1);
/* каждую часть */ }
Операция swap, которая меняет местами два элемента, встречается в quicksort
трижды, поэтому лучше всего вынести ее в отдельную функцию:
/* swap:
поменять местами v[i] и v[j] */
void swap(int v[], int i, int j)
{
int temp;
temp = v[i]; v[i] = v[j]; v[j] = temp;
При разделении прежде всего случайным образом выбирается элемент-
разделитель, который временно переставляется в начало массива, затем
просматриваются остальные. Элементы, меньшие разделителя ("
маленькие"
элементы), перемещаются ближе к началу массива (на позицию last), а "большие"
элементы — в сторону конца массива (на позицию i). В начале процесса, сразу после
перемещения разделителя в начало, last = 0 и элементы с i = 1 по n-1 еще не
исследованы:
В начале 1-й итерации элементы с первого по last строго меньше разделителя,
элементы с last+1 no i-1 больше или равны разделителю, а элементы с i по п-1 еще
не рассмотрены. Пока не выполнилось первый раз условие v[i] >='v[0], алгоритм
будет переставлять элемент v[i] сам с собой; это, конечно, занимает дополнительное
время, но не столь страшно.
Когда все элементы просмотрены, нулевой элемент переставляется на позицию last,
чтобы разделитель занял свою окончательную позицию; тогда порядок элементов
будет правильным. Теперь массив выглядит так:
Та же самая операция применяется к левой и правой частям массива; после
окончания этого процесса весь массив будет отсортирован.
Насколько быстро работает быстрая сортировка? В наилучшем случае
• первый проход делит массив из п элементов на две группы примерно по п/2
элементов;
• второй проход разделяет две группы по п/2 элементов на 4 группы, в каждой
из которых примерно по п/4 элементов;
• на следующем проходе четыре группы по п/4 делятся на восемь групп по
(примерно) п/8 элементов;
• и т. д.
Данный процесс продолжается примерно Iog2 n раз, поэтому общее время работы в
лучшем случае пропорционально п + 2 X и/2 + 4 х и/4 + + 8 X п/8 ... (Iog2 и
слагаемых), что равно п log? п. В среднем алгоритм работает совсем не намного
дольше. Обычно принято использовать именно двоичные логарифмы, поэтому мы
можем сказать, что быстрая сортировка работает пропорционально n long.
Эта
демонстрационная реализация быстрой сортировки наиболее прозрачна, но у
нее есть одна слабина. Если каждый выбор разделителя разбивает массив на две
примерно одинаковые группы, то наш анализ корректен, однако если разделение
слишком часто происходит неровно, то время работы будет расти скорее как п1. В
нашей реализации в качестве разделителя берется случайный
элемент, чтобы
уменьшить шанс того, что плохие входные данные приведут к слишком большому
количеству неровных разбиений массива. Но если все входные значения одинаковы,
то наша реализация за каждый проход будет отделять только один элемент, поэтому
время работы будет расти как п2.
Поведение некоторых алгоритмов сильно зависит от входных данных. Неправильный
или
неудачный ввод может заставить в среднем хороший алгоритм работать крайне
медленно или использовать огромное количество памяти. В случае быстрой
сортировки, хотя простые реализации вроде нашей иногда могут работать медленно,
более продуманные реализации способны уменьшить шанс патологического
поведения почти до нуля.
Библиотеки
В стандартные библиотеки языков С и C++ входят функции сортировки, которые
устойчивы к неблагоприятным входным данным и настроены на предельно быструю
работу.
Библиотечные функции написаны так, что они могут сортировать данные любого
типа, но мы в свою очередь должны адаптироваться к их интерфейсу, что может
быть несколько сложнее, чем в рассмотренном выше
примере. В языке С
библиотечная функция называется qso rt, и ей нужно предоставлять функцию
сравнения двух значений. Поскольку значения могут быть любых типов, то функции
сравнения передаются два нетипизированных указателя (void *) на сравниваемые
значения. Функция преобразует указатели к нужному типу, извлекает значения
данных, сравнивает их и возвращает результат (отрицательный, нуль или
положительный в
зависимости от того, меньше ли первый элемент, равен ли
второму или больше его).
Рассмотрим реализацию функции сравнения для сортировки массива строк, случая,
встречающегося довольно часто. Мы написали функцию scmp, которая -преобразует
параметры к другому типу и затем вызывает st rcmp для выполнения самого
сравнения:
/* scmp: сравнение строк *р1 и *р2 */
int scmp(const void *p1, const void *p2)
{
char *v1, *v2;
v1 = *(char **) p1; v2 = *(char **) p2;
return strcmp(v1, v2); }
Мы могли бы написать эту функцию в одну строку, но при использовании временных
переменных код становится более удобочитаемым.
Мы не можем напрямую использовать strcmp как функцию сравнения, поскольку
qsort передает адрес каждого элемента в массиве &s t г [ i ] (типаспаг **), ане str[i]
(типа char *), как показано на рисунке:
Для сортировки элементов массива строк с st r[0] по st r[N-1 ] функция qsort должна
получить массив, его длину, размер сортируемых элементов и функцию сравнения:
char *str[N];
qsort(str, N, sizeof(str[OJ), scmp);
А вот аналогичная функция icmp для сравнения целых:
{
int v1, v2;
v1 = *(int *) p1; v2 = *(int *.) p2;
if (v1 < v2)
return -1; else
if (v1 == v2)
return 0; else
return 1; >
}
Мы могли бы написать
? return v1-v2;
но если v2 — большое положительное число, a v1 — большое по абсолютному
значению отрицательное или наоборот, то получившееся
переполнение привело бы
к неправильному ответу. Прямое сравнение длиннее, но надежнее.