Керниган Б., Пайк Р. Практика программирования

Подождите немного. Документ загружается.

И здесь при вызове qsort нужно передать массив, его длину, размер сортируемых

элементов и функцию сравнения:

int arr[N];

qsort(arr, N, sizeof(arr[0]), icmp);

В стандарте ANSI С определена также функция двоичного поиска bsea rch. Как и qso

rt, этой функции нужен указатель на функцию сравнения (часто на ту же, что

используется для qsort); bsearch возвращает указатель на найденный элемент или

на NULL, если такого элемента

нет. Вот наша программа для поиска имен в HTML-

файле, переписанная с использованием bsearch:

/* lookup: использует bsearch для поиска name в таблице tab,

возвращает индекс */

int lookup(char *name, Nameval tab[],

int ntab) {

Nameval key, *np;

key.value = 0; /* не используется;

годится любое значение */

np = (Nameval *) bsearch(&key, tab, ntab,

sizeof(tab[0]), nvcmp); if (np == NULL)

return -1; else

return np-tab;

Как и в случае qsort, функция сравнения получает адреса сравниваемых значений,

поэтому ключевое (искомое) значение должно иметь этот же тип; в данном примере

нам

пришлось создать фиктивный элемент типа Nameval для передачи в функцию

сравнения. Сама функция сравнения nvcmp сравнивает два значения типа Nameval,

вызывая st rcmp для их строковых компонентов, полностью игнорируя численные

компоненты:

/* nvcmp: сравнивает два вначения типа

Nameval */

int nvcmp(const void *va, const void *vb)

{

const Nameval *a, *b;

a = (Nameval *) va;* b = (Nameval *) vb;

return strcmp(a->name, b->name); }

Это похоже на scmp, только с тем отличием, что строки хранятся как члены

структуры.

Неудобство передачи ключевого значения

показывает, что bsearch предоставляет

меньше возможностей, чем qso rt. Хорошая многоцелевая функция сортировки

занимает одну-две страницы кода, а двоичный поиск — ненамного больше, чем код

для интерфейса с bsearch. Тем не менее лучше использовать bsearch, чем писать

свою собственную версию. Как показывает опыт, программистам на удивление

трудно написать двоичный поиск без ошибок.

В стандартной библиотеке C++

имеется обобщенная функция sort, которая

обеспечивает время работы 0(п log n). Код для ее вызова проще, потому что нет

необходимости в преобразовании типов и размеров элементов. Кроме того, для

порядковых типов не требуется задавать функцию сравнения:

int arr[N]; sort(arr, arr+N);

Эта библиотека содержит также обобщенные функции двоичного поиска, с теми же

преимуществами в вызове.

Упражнение 2-1

Алгоритм быстрой сортировки проще всего выразить рекурсивно. Реализуйте его

итеративно и сравните две версии. (Хоар рассказывает, как было трудно

разработать итеративный вавариант быстрой сортировки и как легко все оказалось,

когда он сделал ее рекурсивной.)

Быстрая сортировка на языке Java

В Java ситуация другая. В ранних версиях не было стандартной функции сортировки,

поэтому приходилось писать собственную. В последних версиях появилась такая

функция, работающая с классами, реализующими интерфейс Comparable, поэтому

теперь мы можем просить библиотеку сортировать то, что нам потребуется. Но

поскольку используемые технологии полезны и в других ситуациях, в данном

разделе мы опишем

все детали реализации быстрой сортировки в Java.

Адаптировать быструю сортировку для каждого конкретного типа данных легко;

однако же более поучительно написать обобщенную функцию для сортировки

объектов любых типов, что больше похоже на интерфейс qsort.

Одно из крупных отличий от С и C++ заключается в том, что в Java мы не можем

передать функцию сравнения

в другую функцию — здесь не существует указателей

на функции. Вместо этого мы создаем интерфейс (interface), единственным

содержимым которого будет функция, сравнивающая два объекта типа Object. Далее

для каждого сортируемого типа данных мы создаем класс с функцией (методом),

которая реализует интерфейс для этого типа данных. Мы передаем экземпляр

класса в функцию сортировки, которая в

свою очередь использует функцию

сравнения из этого класса для сравнения элементов.

Сначала опишем интерфейс Стр, который определяет единственную функцию стр,

сравнивающую два значения типа Object:

interface Cmp {

int cmp(0bject x, Object y);

}

Теперь мы можем написать функции сравнения, которые реализуют этот интерфейс;

например, следующий класс определяет функцию, сравнивающую объекты типа

Integer:

// Icmp: сравнение целых class

Icmp implements Cmp {

public int cmp(0bject o1, Object o2)

{

int 11 = ((Integer) o1). intValueO;

int 12 =

((Integer) o2). intValueO; if (11 < 12)

return -1; else if (11 == 12)

return 0; else

return 1; } }

;

а эта функция сравнивает объекты типа St ring:

// Scmp: сравнение

строк class

Scmp implements Cmp {

public int cmp(0bject o1, Object o2)

{

String s1 = (String) o1; String s2 =

(String) o2; return s1.compareTo(s2);

} }

Данным способом можно сортировать только типы, наследуемые от класса Object;

подобный механизм нельзя применять для базовых типов, таких как int или double.

Поэтому мы сортируем элементы типа Integer,

а не int.

С этими компонентами мы теперь можем перенести функцию быстрой сортировки из

языка С в

Java и вызывать в ней функцию сравнения из объекта Стр, переданного

параметром. Наиболее существенное изменение — это использование индексов left

и right, поскольку в Java нет указателей на массивы.

// Quicksort.sort: сортировать v[left]..v[right]

// алгоритмом quicksort

static void sort(0bject[] v, int left,

int right, Cmp cmp)

{

int i, last;

if (left >= right) // ничего делать не надо

return;

swap(v, left, rand(left,right)); // поместить

разделитель last = left; // в v[left]

for (i = left+1; i <= right; i++) // разделить

массив if (cmp.cmp(v[i], v[left]) < 0)

swap(v, ++last, i);

swap(v, left, last); // вернуть разделитель

sort(v, left, last-1, cmp); // рекурсивно

отсортировать sort(v, last+1, right, cmp);

// обе части }

Quicksort.sort

использует cmp для сравнения двух объектов, как и раньше, вызывает

swap для их обмена.

// Quicksort.swap: обменять v[i]

и v[j] static void swap

(0bject[] v, int i, int j) {

Object temp;

temp = v[i]; v[i] = v[j]

; v[j] = temp; }

Генерация случайного номера происходит в функции rand, которая а возвращает

случайное число в диапазоне с left по right включительно:

static

Random rgen = new Random();

// Quicksort, rand: возвращает

случайное целое число // из [left, right]

static int rand(int left, int right)

{

return left + Math.abs

(rgen.nextlnt())%(right-left+1);

}

Мы вычисляем абсолютное значение (используя функцию Math.abs), поскольку в

Java генератор случайных чисел возвращает как положительные, так и

отрицательные значения.

Функции sort, swap и rand, а также объект-генератор случайных чисел rgen являются

членами класса Quicksort.

Наконец мы готовы написать вызов Quicksort, sort для сортировки массива типа

String:

String[] sarr = new String[n];

// заполнить n

элементов sarr...

Quicksort. sort

(sarr, 0, sarr. length-1, new ScmpO);

Так вызывается so rt с объектом сравнения строк, созданным для этой цели.

Упражнение 2-2

Наша реализация быстрой сортировки в Java делает несколько преобразований

типов, сначала переводя исходные данные из их первоначального типа (вроде

Integer) в Object, а затем обратно. Поэкспериментируйте с версией Quickso rt. so rt,

которая использует конкретный тип при сортировке, и попробуйте вычислить, какие

потери производительности

вызываются преобразованием типов.

"О большое"

Мы описывали трудоемкость алгоритма в зависимости от п, количества входных

элементов. Поиск в неотсортированных данных занимает время, пропорциональное

п; при использовании двоичного поиска по отсортированным данным время будет

пропорционально log п. Время сортировки пропорционально n

или n logn.

Нам нужно как-то уточнить эти высказывания, при этом абстрагируясь от таких

деталей, как скорость процессора и качество компилятора (и программиста).

Хотелось бы сравнивать время работы и затраты памяти алгоритмов вне

зависимости от языка программирования, компилятора, архитектуры компьютера,

скорости процессора, загруженности системы и других сложных факторов.

Для этой цели

существует стандартная форма записи, которая называется "О

большое". Основной параметр этой записи — п, размер входных данных, а

сложность или время работы алгоритма выражается как функция от п. "О" — от

английского order, то есть порядок. Например, фраза "Двоичный поиск имеет

сложность 0(log n)" означает, что для поиска в массиве из п элементов требуется

порядка log n действий

. Запись О(f(n)) предусматривает, что при достаточно

больших п время выполнения пропорционально f(n), не быстрее, например, О(n

)

или 0(n log n). Асимптотические оценки вроде этой полезны при теоретическом

анализе и грубом сравнении алгоритмов, однако на практике разница в деталях

может иметь большое значение. Например, алгоритм класса 0(n

) с малым

количеством дополнительных вычислений для малых п может работать быстрее,

чем сложный алгоритм класса О(n logn), однако при достаточно большом п алгоритм

с медленнее возрастающей функцией поведения неизбежно будет работать

быстрее.

Нам нужно различать также случаи наихудшего и ожидаемого поведения. Трудно

строго определить, что такое "ожидаемое" поведение, потому что определение

зависит от наших предположений о возможных входных данных. Обычно мы можем

точно указать самый плохой случай, хотя иногда и здесь можно ошибиться. Для

quicksort в самом плохом случае время работы растет как О(n

), а среднее

("ожидаемое") время — как О(n log n). Если каждый раз аккуратно выбирать элемент-

разделитель, то мы можем свести вероятность квадратичного (то есть 0(n

))

поведения практически к нулю; хорошо реализованная quicksort действительно

обычно ведет себя как О(n log n).

Вот основные случаи:

Запись Название времени Пример

0(1) Константное Индексирование массива

0(log n) Логарифмическое Двоичный поиск

0(n) Линейное Сравнение строк

0(n log n)

n logn Quicksort

0(n

) Квадратичное Простые методы сортировки

О(n

) Кубическое Перемножение матриц

0(2

) Экспоненциальное Перебор всех подмножеств

Доступ к элементу в массиве — операция, работающая за константное (О(1)) время.

Алгоритм, за каждый шаг отсеивающий половину входных данных, как двоичный

поиск, обычно займет время 0(log n). Сравнение двух строк длиной в n символов с

помощью strcmp займет О(n).

Традиционный алгоритм перемножения двух квадратных матриц порядка п занимает

О(и!), поскольку каждый элемент получается

в результате перемножения и пар

чисел и суммирования результатов, а всего элементов n

Экспоненциальное время работы алгоритма обычно является результатом перебора

всех вариантов: у множества из п элементов — 2"различных подмножеств, поэтому

алгоритм, которому надо пройтись по всем подмножествам, будет выполняться за

время 0(2"), то есть будет экспоненциальным. Экспоненциальные алгоритмы обычно

слишком долго работают, если только п не очень мало, поскольку добавление

одного элемента удваивает

время работы алгоритма. К сожалению, существует

много задач, таких как, например, знаменитая "задача коммивояжера", для которых

известны только экспоненциальные решения. Когда задача такова, часто вместо

точных решений берут алгоритмы, находящие некоторое приближение к ответу.

Упражнение 2-3

Каковы входные данные для алгоритма quicksort, которые заставляют его работать

медленнее всего, как в наихудшем случае? Попробуйте найти несколько наборов

данных, сильно замедляющих библиотечную версию алгоритма. Автоматизируйте

процесс, чтобы вы легко могли задавать параметры и проводить большое число

экспериментов.

Упражнение 2-4

Придумайте и реализуйте алгоритм, который будет сортировать массив из п целых

как

можно медленнее. Только напишите его честно: алгоритм должен постепенно

прогрессировать и в конце концов завершиться, и ваша реализация не должна

использовать всяческие трюки вроде лишних пустых циклов. Какова получилась

сложность вашего алгоритма как функция от n?

Динамически расширяемые массивы

Массивы, использованные в нескольких предыдущих разделах, были статическими,

их размер и содержимое задавались во время компиляции. Если потребовать, чтобы

некоторую таблицу слов или символов HTML можно было изменять во время

выполнения, то хэш-таблица была бы для этой цели более подходящей структурой.

Вставка в отсортированный массив п элементов по одному занимает О

), чего

стоит избегать при больших n.

Однако часто нам нужно работать с переменным, но небольшим числом значений, и

тогда массивы по-прежнему могут применяться. Для уменьшения потерь при

перераспределении памяти изменение размера должно происходить блоками, и для

простоты массив должен храниться вместе с информацией, необходимой для

управления им^ В C++ и Java это

делается с помощью классов из стандартных

библиотек, а в С мы можем добиться похожего результата с помощью структур.

Следующий код определяет расширяемый массив с элементами типа Nameval:

новые элементы добавляются в хвост массива, который удлиняется при

необходимости. Доступ к каждому элементу по его индексу происходит за

константное время. Эта конструкция аналогична

векторным классам из библиотек

C++ и Java.

typedef struct Nameval Nameval;

struct Nameval {

char *name;

int value; };

struct NVtab {

int nval; /* текущее количество

элементов */

int max; /* под сколько элементов

выделена память */

Nameval *nameval; /* массив пар */

} nvtab;

enum { NVINIT = 1, NVGROW = 2 };

/* addname: добавить новое имя

и значение в nvtab */

int addname(Nameval newname)

{

Nameval *nvp;

if (nvtab.nameval == NULL) { /* первый вызов

*/ nvtab.nameval =

(Nameval *) malloc(NVINIT * sizeof(Nameval));

if (nvtab.nameval == NULL)

return -1; nvtab.max = NVINIT; nvtab.nval = 0;

} else if (nvtab.nval >= nvtab.max) { /* расширить

*/ nvp = (Nameval *) realloc(nvtab.nameval,

(NVGROW*nvtab.max) * sizeof(Nameval));

if (nvp == NULL)

return -1;

nvtab.max *= NVGROW;

nvtab.nameval = nvp; }

nvtab.nameval[nvtab.nval]

= newname; return nvtab.

Функция addname возвращает индекс только что добавленного элемента или -1 в

случае возникновения ошибки.

Вызов reallос увеличивает массив до новых размеров, сохраняя существующие

элементы, и возвращает указатель на него или NULL при недостатке памяти.

Удвоение размера массива при каждом вызове realloc сохраняет средние

"ожидаемые" затраты на копирование

элемента постоянными; если бы массив

увеличивался каждый раз только на один элемент, то производительность была бы

порядка 0(п2). Поскольку при перераспределении памяти адрес массива может

измениться, то программа должна обращаться к элементам массива по индексам, а

не через указатели. Заметьте, что код не таков:

? nvtab.nameval = (Nameval *) realloc(nvtab.nameval,

? (NVGROW*nvtab.jnax) * sizeof (Nameval));

потому что при такой форме если

вызов realloc не сработает, то исходный массив

будет утерян.

Мы задаем очень маленький начальный размер массива (NVINIT = 1). Это

заставляет программу увеличивать массив почти сразу, что гарантирует проверку

данной части программы. Начальное значение может быть и увеличено, когда

программа начнет реально использоваться, однако затраты на стартовое

расширение массива ничтожны.

Значение, возвращаемое realloc, не обязательно

должно приводиться к его

настоящему типу, поскольку в С нетипизированные указатели (void *) приводятся к

любому типу указателя автоматически. Однако в C++ это не так; здесь

преобразование обязательно. Можно поспорить, что безопаснее: преобразовывать

типы (это честнее и понятнее) или не преобразовывать (поскольку в преобразовании

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

программа корректна как в С, так и в C++. Цена такого решения — уменьшение

количества проверок на ошибки компилятором С, но это неважно, когда мы

производим дополнительные проверки с помощью двух компиляторов.

Удаление элемента может быть более сложной операцией, поскольку нам нужно

решить, что же делать с образовавшейся "дыркой" в массиве. Если

порядок

элементов не имеет значения, то проще всего переставить последний элемент на

место удаленного. Однако, если порядок должен быть сохранен, нам нужно сдвинуть

элементы после "дырки" на одну позицию:

/* delname: удалить первое

совпавшее имя в массиве nvtab */

int delname(char *name)

{

int i;

for (i = 0; i < nvtab.nval; i++)

if (strcmp(nvtab.nameval[i].name,

name)

== 0) { meminove(nvtab. nameval+i, nvtab.

nameval'+i+1, (nvtab.nval-(i+1)

) * sizeof(Nameval));

nvtab.nval--; return 1;

}

return 0:

}

Вызов memmove сдвигает массив, перемещая элементы вниз на одну позицию;

memmove — стандартная библиотечная функция для копирования блоков памяти

любого размера.

В стандарте ANSI

определены две функции: memcpy, которая работает быстрее, но может затереть

память, если источник и приемник данных пересекаются, и memmove, которая

может

работать медленнее, но зато всегда корректна. Бремя выбора между скоростью и

корректностью не должно взваливаться на программиста; должна была бы быть

только одна функция. Считайте, что это так и есть, и всегда используйте memmove.

Мы могли бы заменить вызов memmove следующим циклом:

nt j;

for (j = i; j

< nvtab.nval-1; j++)

nvtab.namevalfj]

= nvtab.nameval[j+1];i

Однако мы предпочитаем использовать memmove, чтобы обезопасить себя от

легко

возникающей ошибки копирования элементов в неправильном порядке. Если бы мы

вставляли элемент, а не удаляли, то цикл должен был бы идти вверх, чтобы не

затереть элементы. Вызывая memmove, мы ограждаем себя от необходимости

постоянно задумываться об этом.

Альтернатива перемещению элементов — помечать удаленные элементы как

неиспользуемые. Тогда для добавления элемента нам

надо сначала найти

неиспользуемую ячейку и увеличивать массив, только если свободного места не

найдено. В данном примере элемент можно пометить как неиспользуемый,

установив значения поля name в NULL.

Массивы — простейший способ группировки данных; вовсе не случайно

большинство языков имеют эффективные и удобные индексируемые массивы и

даже представляют строки в виде массивов символов. Массивы

просты в

использовании, обладают константным доступом к любому элементу, хорошо

работают с двоичным поиском и быстрой сортировкой, а также почти совсем не

тратят лишних ресурсов. Для наборов данных фиксированного размера, которые

могут быть созданы даже во время компиляции, или же для гарантированно

небольших объемов данных массивы подходят идеально. Однако хранение

меняющегося набора значений в массиве может быть весьма ресурсоемким,

поэтому, если количество элементов непредсказуемо и потенциально

неограниченно, может оказаться удобнее использовать другую структуру данных.

Упражнение 2-5

В приведенном выше коде функция delname не вызывает realloc для возврата

системе памяти, освобожденной удалением элемента. Имеет ли смысл это делать?

Как решить, стоит это делать или нет?

Упражнение 2-6

Внесите необходимые изменения в функции delname и addname, чтобы удаленные

элементы помечались как неиспользуемые. Насколько остальная программа не

зависит от этого изменения?

Списки

По своей встречаемости в типичных программах списки занимают второе место

после массивов. Многие языки имеют встроенные типы списков, некоторые, такие

как Lisp, даже построены на них, но в языке С мы должны конструировать их

самостоятельно. В C++ и Java работа со списками поддерживается стандартными

библиотеками, но и в этом случае нужно знать их возможности

и типичные

применения. В данном параграфе мы собираемся обсудить использование списков в

С, но уроки из этогр обсуждения можно извлечь и для более широкого применения.

Простым цепным списком (single-linked list) называется последовательность

элементов, каждый из которых содержит данные и указатель на следующий элемент.

Головой списка является указатель на первый элемент, а конец

помечен нулевым

указателем. Ниже показан список из четырех элементов:

Есть несколько важных различий между массивами и списками. Во-первых, размер

массивов фиксирован, а список всегда имеет именно такой размер, который нужен

для хранения содержимого, плюс некоторое дополнительное место для указателей

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

указателей, что дешевле, чем копирование блоков, необходимое при использовании

массива. Наконец, при удалении или вставке элементов остальные элементы не

перемещаются; если мы будем хранить указатели на отдельные элементы в другой

структуре данных, то при изменениях в списке они останутся корректными.

Эти различия подсказывают, что если набор данных будет часто меняться, особенно

при непредсказуемом количестве элементов, то нужно использовать список;

напротив, массив больше подходит для относительно статичных данных.

Фундаментальных операций со списком совсем немного: добавить элемент в начало

или конец списка, найти указанный элемент, добавить новый элемент до или после

указанного элемента и, возможно, удалить элемент. Простота списков позволяет при

необходимости легко добавлять новые операции.

Вместо того чтобы определить специальный тип List, обычно в С начинают

определение списка с описания типа для элементов, вроде нашего Nameval, и

добавляют в него указатель на следующий элемент:

typedef struct Nameval Nameval;

struct Nameval {

char *name:

int value;

Nameval «next;

/* следующий в списке */ };

Инициализировать непустой список во

время компиляции трудно, поэтому списки, не

в пример массивам, создаются динамически. Для начала нам нужен способ создания

элемента. Наиболее простой подход — выделить под него память специальной

функцией, которую мы назвали newitem:

/* newitem: создать новый элемент

по полям name и value */ Nameval

*newitem(char *name, int value)

{

Nameval *newp;

newp = (Nameval *) emalloc(sizeof(Nameval));

newp->name = name; newp->value

= value; newp->next = NULL; return newp; }

Функцию emalloc мы будем использовать и далее во всей книге; она вызывает

mall

ос, а при ошибке выделения памяти выводит сообщение и завершает программу. Мы

представим код этой функции в главе 4, а пока считайте, что эта функция всегда

корректно и без сбоев выделяет память.

Простейший и самый быстрый способ собрать список — это добавлять новые

элементы в его начало:

/* addfront: добавить элемент newp

в начало списка

listp */ Nameval

*addfront

(Nameval *listp, Nameval *newp)

{

newp->next = listp;

return newp; }

При изменении списка у него может измениться первый элемент, что и происходит

при вызове addf ront. Функции, изменяющие список, должны возвращать указатель

на новый первый элемент, который хранится в переменной, указывающей на список.

Функция addfront и другие функции этой группы передают указатель на первый

элемент в качестве возвращаемого значения; вот типичное использование

таких

функций:

nvlist = addf ront(nvlist, newitem( "smiley", Ox263A));

Такая конструкция работает, даже если существующий список пуст (NULL), она

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

более естественно, чем альтернативный вариант — передавать указатель на

указатель на голову списка.