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 п. Время сортировки пропорционально n2 или n logn.
Нам нужно как-то уточнить эти высказывания, при этом абстрагируясь от таких деталей, как скорость процессора и качество компилятора (и программиста). Хотелось бы сравнивать время работы и затраты памяти алгоритмов вне зависимости от языка программирования, компилятора, архитектуры компьютера, скорости процессора, загруженности системы и других сложных факторов.
Для этой цели существует стандартная форма записи, которая называется "О большое". Основной параметр этой записи — п, размер входных данных, а сложность или время работы алгоритма выражается как функция от п. "О" — от английского order, то есть порядок. Например, фраза "Двоичный поиск имеет сложность 0(log n)" означает, что для поиска в массиве из п элементов требуется порядка log n действий. Запись О(f(n)) предусматривает, что при достаточно больших п время выполнения пропорционально f(n), не быстрее, например, О(n2) или 0(n log n). Асимптотические оценки вроде этой полезны при теоретическом
анализе и грубом сравнении алгоритмов, однако на практике разница в деталях может иметь большое значение. Например, алгоритм класса 0(n2) с малым количеством дополнительных вычислений для малых п может работать быстрее, чем сложный алгоритм класса О(n logn), однако при достаточно большом п алгоритм с медленнее возрастающей функцией поведения неизбежно будет работать быстрее.
Нам нужно различать также случаи наихудшего и ожидаемого поведения. Трудно строго определить, что такое "ожидаемое" поведение, потому что определение зависит от наших предположений о возможных входных данных. Обычно мы можем точно указать самый плохой случай, хотя иногда и здесь можно ошибиться. Для quicksort в самом плохом случае время работы растет как О(n2), а среднее ("ожидаемое") время — как О(n log n). Если каждый раз аккуратно выбирать элементразделитель, то мы можем свести вероятность квадратичного (то есть 0(n2)) поведения практически к нулю; хорошо реализованная quicksort действительно обычно ведет себя как О(n log n).
Вот основные случаи:
|
|
|
|
|
|
Запись |
|
Название времени |
|
Пример |
|
|
|
|
|
Индексирование массива |
|
0(1) |
|
Константное |
|
|
|
|
|
|
|
Двоичный поиск |
|
0(log n) |
|
Логарифмическое |
|
|
|
|
|
|
|
Сравнение строк |
|
0(n) |
|
Линейное |
|
|
|
|
|
|
|
|
|
0(n log n) |
|
n logn |
|
Quicksort |
|
|
|
|
|
|
|
|
|
|
|
Простые методы сортировки |
|
0(n2) |
|
Квадратичное |
|
|
|
|
|
|
|
Перемножение матриц |
|
О(n3) |
|
Кубическое |
|
|
|
|
|
|
|
Перебор всех подмножеств |
|
0(2n) |
|
Экспоненциальное |
|
|
|
|
|
|
|
|
|
Доступ к элементу в массиве — операция, работающая за константное (О(1)) время. Алгоритм, за каждый шаг отсеивающий половину входных данных, как двоичный поиск, обычно займет время 0(log n). Сравнение двух строк длиной в n символов с помощью strcmp займет О(n).
Традиционный алгоритм перемножения двух квадратных матриц порядка п занимает О(и!), поскольку каждый элемент получается в результате перемножения и пар чисел и суммирования результатов, а всего элементов n2.
Экспоненциальное время работы алгоритма обычно является результатом перебора всех вариантов: у множества из п элементов — 2"различных подмножеств, поэтому алгоритм, которому надо пройтись по всем подмножествам, будет выполняться за время 0(2"), то есть будет экспоненциальным. Экспоненциальные алгоритмы обычно слишком долго работают, если только п не очень мало, поскольку добавление одного элемента удваивает время работы алгоритма. К сожалению, существует много задач, таких как, например, знаменитая "задача коммивояжера", для которых известны только экспоненциальные решения. Когда задача такова, часто вместо точных решений берут алгоритмы, находящие некоторое приближение к ответу.
Упражнение 2-3
Каковы входные данные для алгоритма quicksort, которые заставляют его работать медленнее всего, как в наихудшем случае? Попробуйте найти несколько наборов данных, сильно замедляющих библиотечную версию алгоритма. Автоматизируйте процесс, чтобы вы легко могли задавать параметры и проводить большое число экспериментов.
Упражнение 2-4
Придумайте и реализуйте алгоритм, который будет сортировать массив из п целых как можно медленнее. Только напишите его честно: алгоритм должен постепенно прогрессировать и в конце концов завершиться, и ваша реализация не должна использовать всяческие трюки вроде лишних пустых циклов. Какова получилась сложность вашего алгоритма как функция от n?
Динамически расширяемые массивы
Массивы, использованные в нескольких предыдущих разделах, были статическими, их размер и содержимое задавались во время компиляции. Если потребовать, чтобы некоторую таблицу слов или символов HTML можно было изменять во время выполнения, то хэш-таблица была бы для этой цели более подходящей структурой. Вставка в отсортированный массив п элементов по одному занимает О(n2), чего стоит избегать при больших 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.
Массивы — простейший способ группировки данных; вовсе не случайно большинство языков имеют эффективные и удобные индексируемые массивы и даже представляют строки в виде массивов символов. Массивы просты в использовании, обладают константным доступом к любому элементу, хорошо работают с двоичным поиском и быстрой сортировкой, а также почти совсем не тратят лишних ресурсов. Для наборов данных фиксированного размера, которые могут быть созданы даже во время компиляции, или же для гарантированно небольших объемов данных массивы подходят идеально. Однако хранение меняющегося набора значений в массиве может быть весьма ресурсоемким,