Слияние кода завершено, страница обновится автоматически
Сортировка
Перевод выполнен с английского языка на русский.
В области разработки и тестирования программного обеспечения сортировка алгоритмов является предметом чрезмерного увлечения. Если судить по тому времени, которое студенты, изучающие компьютерные науки, тратят на эту тему, можно подумать, что выбор алгоритма сортировки является краеугольным камнем современного программного обеспечения. Конечно, реальность такова, что разработчикам программного обеспечения в течение многих лет или даже всей своей карьеры не нужно задумываться о том, как работает сортировка. Для почти всех приложений они используют общие алгоритмы, предоставляемые используемым языком программирования или библиотекой. Обычно этого достаточно.
Поэтому, если вы пропустите эту главу и не будете знать об алгоритмах сортировки, вы всё равно останетесь отличным разработчиком. Однако есть несколько причин, по которым вам может быть полезно это сделать:
Таким образом, в этой главе мы рассмотрим сортировку вставками, вы реализуете сортировку слиянием, я объясню вам сортировку по основанию, и вы напишете простую версию ограниченной сортировки кучей.
17.1 Сортировка вставками
Мы начнём с сортировки вставками, главным образом потому, что её описание и реализация просты. Она не очень эффективна, но у неё есть некоторые компенсирующие свойства, которые мы увидим.
Здесь мы не будем объяснять алгоритм, а рекомендуем вам прочитать страницу Википедии о сортировке вставками (https://ru.wikipedia.org/wiki/Сортировка_вставками), которая включает псевдокод и примеры анимации. Вернитесь сюда после того, как поймёте идею.
Это реализация сортировки вставками на Java:
public class ListSorter<T> {
public void insertionSort(List<T> list, Comparator<T> comparator) {
for (int i=1; i < list.size(); i++) {
T elt_i = list.get(i);
int j = i;
while (j > 0) {
T elt_j = list.get(j-1);
if (comparator.compare(elt_i, elt_j) >= 0) {
break;
}
list.set(j, elt_j);
j--;
}
list.set(j, elt_i);
}
}
}
Я определил класс ListSorter как контейнер для алгоритмов сортировки. Используя параметр типа T, мы можем написать метод, который будет работать со списком, содержащим объекты любого типа.
insertionSort требует двух параметров: любой тип списка и компаратор, который знает, как сравнивать объекты типа T. Он сортирует список «на месте», что означает, что он изменяет существующий список, не выделяя никакого нового пространства.
Следующий пример показывает, как использовать объект List типа Integer и вызвать этот метод:
List<Integer> list = new ArrayList<Integer>(
Arrays.asList(3, 5, 1, 4, 2));
Comparator<Integer> comparator = new Comparator<Integer>() {
@Override
public int compare(Integer elt1, Integer elt2) {
return elt1.compareTo(elt2);
}
};
ListSorter<Integer> sorter = new ListSorter<Integer>();
sorter.insertionSort(list, comparator);
System.out.println(list);
У insertionSort есть два вложенных цикла, поэтому вы можете догадаться, что его время выполнения квадратично. В этом случае это обычно верно, но вы должны проверить, сколько раз каждый цикл выполняется с размером массива n, прежде чем делать такой вывод.
Внешний цикл повторяется от 1 до list.size(), поэтому для размера списка n он линейен. Внутренний цикл повторяется от i до 0, поэтому он также линеен в n. Таким образом, общее количество итераций двух циклов квадратично.
Если вы не уверены, вот доказательство:
На первой итерации внешнего цикла i = 1, внутренний цикл выполняется не более одного раза.
Во второй раз i = 2, внутренний цикл выполняет не более двух итераций.
В последний раз i = n - 1, внутренний цикл выполняет максимум n итераций.
Следовательно, внутренний цикл выполняется в общей сложности 1 + 2 + ... + n - 1 раз, то есть n(n - 1)/2. Главный член этого выражения (с наивысшим показателем степени) равен n^2.
В худшем случае сортировка вставками квадратична. Тем не менее:
k элементах от своего упорядоченного положения, внутренний цикл не будет выполняться более k раз, и общее время выполнения будет O(kn).an^2, коэффициент a главного члена может быть небольшим.Итак, если мы знаем, что массив почти упорядочен или не слишком велик, сортировка вставками может быть неплохим выбором. Но для больших массивов мы можем добиться большего. На самом деле, намного большего.
17.2 Упражнение 14
Сортировка слиянием — это алгоритм с временем выполнения лучше, чем квадратичное. Опять же, здесь мы не будем объяснять алгоритм. Я рекомендую вам ознакомиться со страницей Википедии о сортировке слиянием (https://ru.wikipedia.org/wiki/Сортировка_слиянием). Как только у вас появится идея, вернитесь сюда, чтобы проверить своё понимание, написав реализацию.
В репозитории этой книги вы найдёте исходный файл для этого упражнения:
Запустите ant build, чтобы скомпилировать исходные файлы, затем запустите ant ListSorterTest. Как обычно, он должен завершиться неудачно, потому что у вас есть работа.
В ListSorter.java я предоставил схемы двух методов, mergeSortInPlace и mergeSort:
public void mergeSortInPlace(List<T> list, Comparator<T> comparator) {
List<T> sorted = mergeSortHelper(list, comparator);
list.clear();
list.addAll(sorted);
}
private List<T> mergeSort(List<T> list, Comparator<T> comparator) {
// TODO: fill this in!
return null;
}
Эти два метода делают одно и то же, но предоставляют разные интерфейсы. mergeSort принимает список и возвращает новый список с теми же элементами, отсортированными в порядке возрастания. mergeSortInPlace — это метод void, который изменяет существующий список.
Ваша задача — заполнить mergeSort. Прежде чем приступить к полностью рекурсивной версии слияния, сначала сделайте следующее:
Collections.sort или insertionSort, чтобы отсортировать эти две части.Это даст вам возможность отладить код, используемый для объединения, без необходимости иметь дело со сложностью рекурсивного метода.
Затем добавьте граничное условие (см. https://thinkdast.com/basecase). Если вы предоставляете только список, содержащий один элемент, вы можете немедленно вернуться, потому что он уже упорядочен. Или, если длина списка меньше некоторого порога, вы можете использовать Collections.sort или insertionSort. Сначала проверьте граничные условия.
Наконец, измените своё решение, чтобы оно выполняло два рекурсивных вызова для сортировки двух частей массива. Когда вы заставите его работать должным образом, testMergeSort и testMergeSortInPlace должны пройти.
17.3 Анализ сортировки слиянием
Чтобы разделить время выполнения сортировки слиянием на уровни рекурсии и количество работы, выполняемой на каждом уровне, полезно подумать о количестве уровней рекурсии и количестве работы, выполняемой на каждом уровне. Предположим, мы начинаем со списка, содержащего n элементов. Шаги алгоритма следующие:
Рисунок 17.1 иллюстрирует эти шаги. 17.1: Демонстрация рекурсивной сортировки слиянием, показывающая один уровень рекурсии
Первый шаг — копирование каждого элемента один раз, поэтому он линейный. Третий шаг также копирует каждый элемент один раз, так что он тоже линейный. Теперь нам нужно разобраться со сложностью шага 2, чтобы сделать это, просмотр различных изображений вычислений может помочь, они показывают количество уровней рекурсии, как показано на рисунке 17.2.
Рисунок 17.2: демонстрация рекурсивного слияния, показывающая все уровни рекурсии.
На верхнем уровне у нас есть 1 список, содержащий n элементов. Для простоты предположим, что n является степенью двойки. На следующем уровне есть два списка, содержащих n/2 элемента. Затем 4 списка с n/4 элементами и так далее, пока мы не получим n списков с 1 элементом.
На каждом уровне у нас всего n элементов. В процессе спуска мы должны разделить массив пополам, что требует времени, пропорционального n на каждом уровне. При возвращении мы должны объединить n элементов, что также линейно.
Если количество уровней равно h, то общая работа алгоритма равна O(nh). Сколько уровней? Есть два способа подумать об этом:
Другая форма второго вопроса — «сколько степеней двойки равно n»?
$2^h = n$
Возьмите логарифм по основанию 2 с обеих сторон:
$h = log_2(n)$
Таким образом, общее время работы составляет O(nlogn). Я не зацикливаюсь на основании логарифма, потому что разница между разными основаниями логарифмов — это просто константа, поэтому все логарифмы имеют одинаковую степень роста.
O(nlogn) иногда называют алгоритмом «линейного логарифмического» типа, но большинство людей просто говорят n log n.
Фактически, O(nlogn) является теоретическим нижним пределом для алгоритмов сортировки сравнением. Это означает, что нет никакого другого алгоритма роста, который был бы лучше, чем n log n для сортировки на основе сравнения. См. http://thinkdast.com/compsort.
Но мы увидим в следующем разделе, что существует алгоритм линейного времени без сравнения!
Сортировка по куче полезна, когда вам нужны первые k элементов из очень большого набора данных, где k намного меньше n. Например, предположим, вы отслеживаете транзакции в веб-сервисе, который обрабатывает 10 миллиардов транзакций в день. В конце каждого дня вы хотите сообщить о самых больших k транзакциях (или самых медленных, или любых других самых xx). Один из вариантов — сохранить все транзакции и отсортировать их в конце дня, а затем выбрать самые большие k. Время, необходимое для этого, пропорционально nlogn, что очень медленно, поскольку мы, возможно, не сможем хранить 10 миллиардов записей транзакций в памяти одной программы. Мы должны использовать «внешний» алгоритм сортировки. Вы можете узнать больше о внешней сортировке на http://thinkdast.com/extsort.
Используя ограниченную кучу, мы можем добиться большего! Вот как мы это реализуем:
Чтобы понять сортировку по куче, вам необходимо понять кучи, которые представляют собой структуру данных, подобную двоичному дереву поиска (BST). Есть несколько отличий:
Примечание переводчика: здесь сначала обсуждается минимальная куча. Если все узлы поддерева больше x, то это максимальная куча.
В минимальной куче наименьший элемент всегда находится в корне, поэтому мы можем найти его за постоянное время. Добавление и удаление элементов в куче занимает время, пропорциональное высоте h дерева. И поскольку куча всегда сбалансирована, h пропорционально log n. Вы можете прочитать больше о кучах на http://thinkdast.com/heap.
Java PriorityQueue использует кучи. PriorityQueue предоставляет методы, указанные в интерфейсе Queue, включая offer и poll:
Учитывая PriorityQueue, вы можете легко отсортировать набор из n элементов следующим образом:
Поскольку опрос возвращает следующий наименьший элемент в очереди, элементы добавляются в список в порядке возрастания. Этот тип сортировки называется сортировкой по куче (см. http://thinkdast.com/heapsort).
Добавление n элементов в очередь занимает nlogn времени. Удаление n элементов также занимает столько же времени. Поэтому сортировка по куче выполняется за время O(n logn).
Вы можете найти план метода heapSort в репозитории этой книги в ListSorter.java. Заполните его, а затем запустите ant ListSorterTest, чтобы убедиться, что он работает. Разработчики программного обеспечения зачастую уделяют больше внимания времени выполнения, что вполне оправдано для многих приложений. Однако в случае больших наборов данных пространство может быть не менее важным или даже более значимым.
Например:
Если набор данных не помещается в память программы, время выполнения обычно значительно увеличивается или программа вообще не может работать. Если выбрать алгоритм, который требует меньше места и позволяет выполнить вычисления в памяти, то программа может выполняться быстрее. Аналогично, программы, которые занимают меньше пространства, могут лучше использовать кэш центрального процессора и работать быстрее (см. http://thinkdast.com/cache).
На сервере, где одновременно выполняется несколько программ, уменьшение необходимого пространства для каждой программы позволит запустить больше программ на одном сервере, что снизит затраты на оборудование и электроэнергию.
Поэтому есть несколько причин, по которым стоит хотя бы немного разбираться в требованиях к пространству у различных алгоритмов.
Вы можете оставить комментарий после Вход в систему
Неприемлемый контент может быть отображен здесь и не будет показан на странице. Вы можете проверить и изменить его с помощью соответствующей функции редактирования.
Если вы подтверждаете, что содержание не содержит непристойной лексики/перенаправления на рекламу/насилия/вульгарной порнографии/нарушений/пиратства/ложного/незначительного или незаконного контента, связанного с национальными законами и предписаниями, вы можете нажать «Отправить» для подачи апелляции, и мы обработаем ее как можно скорее.
Опубликовать ( 0 )