Урок: Алгоритмы

Полиморфные алгоритмы, описанные здесь, являются частями допускающей повторное использование функциональности, обеспеченной платформой Java. Все они происходят из Collections class, и все принимают форму статических методов, первым параметром которых является набор, на котором должна быть выполнена работа. Значительное большинство алгоритмов, обеспеченных платформой Java, работает на List экземпляры, но несколько из них работают на произвольном Collection экземпляры. Этот раздел кратко описывает следующие алгоритмы:

• Сортировка
• Перестановка
• Стандартное Манипулирование данными
• Поиск
• Состав
• Обнаружение Экстремумов

Сортировка

sort алгоритм переупорядочивает a List так, чтобы его элементы были в порядке возрастания согласно отношению упорядочивания. Обеспечиваются две формы работы. Простая форма берет a List и виды это согласно естественному упорядочиванию его элементов. Если Вы незнакомы с понятием естественного упорядочивания, считайте раздел Упорядочивания Объекта.

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

• Быстро: Это, как гарантируют, будет работать в n log(n) время и работает существенно быстрее в почти сортированных списках. Эмпирические тесты показали это, чтобы быть с такой скоростью, как чрезвычайно оптимизированный quicksort. quicksort, как обычно полагают, быстрее чем сортировка слиянием, но не устойчив и не гарантирует n log(n) производительность.
• Устойчивый: Это не переупорядочивает равные элементы. Это важно, если Вы неоднократно сортируете тот же самый список на различных атрибутах. Если пользователь почтовой программы сортирует ящик для приема сообщений, отправляя дату по почте и затем сортирует это отправителем, то пользователь естественно ожидает, что теперь непрерывный список сообщений от данного отправителя будет (все еще) сортирован, отправляя дату по почте. Это гарантируется, только если второй вид был устойчив.

Следующий trivial program распечатывает его параметры в лексикографическом (алфавитном) порядке.

import java.util.*;

public class Sort {
    public static void main(String[] args) {
        List<String> list = Arrays.asList(args);
        Collections.sort(list);
        System.out.println(list);
    }
}

Давайте выполнять программу.

% java Sort i walk the line

Следующий вывод производится.

[i, line, the, walk]

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

Вторая форма sort берет a Comparator в дополнение к a List и виды элементы с Comparator. Предположите, что Вы хотите распечатать группы анаграммы от нашего более раннего примера в обратном порядке размера — самая многочисленная группа анаграммы сначала. Пример, который следует за шоу Вы, как достигнуть этого со справкой второй формы sort метод.

Вспомните, что группы анаграммы сохранены как значения в a Map, в форме List экземпляры. Пересмотренный код печати выполняет итерации через Map's оценивает представление, помещая каждый List это проходит тест минимального размера в a List из Lists. Затем код сортирует это List, использование a Comparator это ожидает List экземпляры, и реализации инвертируют упорядочивание размера. Наконец, код выполняет итерации через сортированный List, печать его элементов (группы анаграммы). Следующий код заменяет код печати в конце main метод в Anagrams пример.

// Make a List of all anagram groups above size threshold.
List<List<String>> winners = new ArrayList<List<String>>();
for (List<String> l : m.values())
    if (l.size() >= minGroupSize)
        winners.add(l);

// Sort anagram groups according to size
Collections.sort(winners, new Comparator<List<String>>() {
    public int compare(List<String> o1, List<String> o2) {
        return o2.size() - o1.size();
    }});

// Print anagram groups.
for (List<String> l : winners)
    System.out.println(l.size() + ": " + l);

Выполнение the program на same dictionary как в разделе Интерфейса Карты, с тем же самым минимальным групповым размером анаграммы (восемь), производит следующий вывод.

12: [apers, apres, asper, pares, parse, pears, prase,
       presa, rapes, reaps, spare, spear]
11: [alerts, alters, artels, estral, laster, ratels,
       salter, slater, staler, stelar, talers]
10: [least, setal, slate, stale, steal, stela, taels,
       tales, teals, tesla]
9: [estrin, inerts, insert, inters, niters, nitres,
       sinter, triens, trines]
9: [capers, crapes, escarp, pacers, parsec, recaps,
       scrape, secpar, spacer]
9: [palest, palets, pastel, petals, plates, pleats,
       septal, staple, tepals]
9: [anestri, antsier, nastier, ratines, retains, retinas,
       retsina, stainer, stearin]
8: [lapse, leaps, pales, peals, pleas, salep, sepal, spale]
8: [aspers, parses, passer, prases, repass, spares,
       sparse, spears]
8: [enters, nester, renest, rentes, resent, tenser,
       ternes,��treens]
8: [arles, earls, lares, laser, lears, rales, reals, seral]
8: [earings, erasing, gainers, reagins, regains, reginas,
       searing, seringa]
8: [peris, piers, pries, prise, ripes, speir, spier, spire]
8: [ates, east, eats, etas, sate, seat, seta, teas]
8: [carets, cartes, caster, caters, crates, reacts,
       recast,��traces]

Перестановка

shuffle алгоритм делает противоположность какой sort делает, уничтожая любую трассировку порядка, который, возможно, присутствовал в a List. Таким образом, этот алгоритм переупорядочивает List основанный на вводе из источника случайности так, что все возможные перестановки происходят с равной вероятностью, принимая справедливый источник случайности. Этот алгоритм полезен в реализации азартных игр. Например, это могло использоваться, чтобы переставить a List из Card объекты, представляющие деку. Кроме того, это полезно для генерирования прецедентов.

У этой работы есть две формы: каждый берет a List и использует источник значения по умолчанию случайности, и другой требует, чтобы вызывающая сторона обеспечила Случайный объект использовать в качестве источника случайности. Код для этого алгоритма используется в качестве примера в List раздел.

Стандартное Манипулирование данными

Collections class обеспечивает пять алгоритмов для того, чтобы они сделали стандартное манипулирование данными на List объекты, все из которых являются довольно прямыми:

• reverse — инвертирует порядок элементов в a List.
• fill — перезаписывает каждый элемент в a List с указанным значением. Эта работа полезна для переинициализации a List.
• copy — берет два параметра, место назначения List и источник List, и копирует элементы источника в место назначения, перезаписывая его содержание. Место назначения List должен быть, по крайней мере, пока источник. Если это более длинно, остающиеся элементы в месте назначения List незатронуты.
• swap — подкачивает элементы в указанных позициях в a List.
• addAll — добавляют все указанные элементы к a Collection. Элементы, которые будут добавлены, могут быть определены индивидуально или как массив.

Поиск

binarySearch алгоритм ищет указанный элемент в сортированном List. У этого алгоритма есть две формы. Первые взятия a List и элемент, чтобы искать ("ключ поиска"). Эта форма предполагает что List сортируется в порядке возрастания согласно естественному упорядочиванию его элементов. Вторая форма берет a Comparator в дополнение к List и ключ поиска, и предполагает что List сортируется в порядок по возрастанию согласно указанному Comparator. sort алгоритм может привыкнуть к виду List до вызова binarySearch.

Возвращаемое значение является тем же самым для обеих форм. Если List содержит ключ поиска, индексировать возвращается. В противном случае возвращаемое значение (-(insertion point) - 1), где точка вставки является точкой, в которой значение было бы вставлено в List, или индексирование первого элемента, больше чем значение или list.size() если все элементы в List меньше чем указанное значение. Эта по общему признанию уродливая формула гарантирует, что возвращаемое значение будет >= 0 если и только если ключ поиска находится. Это - в основном взлом, чтобы объединить булево (found) и целое число (index) в сингл int возвращаемое значение.

Следующая идиома, применимая с обеими формами binarySearch работа, ищет указанный ключ поиска и вставляет его в соответствующей позиции, если он уже не присутствует.

int pos = Collections.binarySearch(list, key);
if (pos < 0)
   l.add(-pos-1);

Состав

Частота и непересекающиеся алгоритмы тестируют некоторый аспект состава один или больше Collections:

• frequency — считает число раз, указанный элемент происходит в указанном наборе
• disjoint — определяет ли два Collections являются непересекающимися; то есть, не содержат ли они элементов вместе

Обнаружение Экстремумов

min и max возврат алгоритмов, соответственно, минимальный и максимальный элемент содержится в указанном Collection. Обе из этих операций прибывают в две формы. Простая форма берет только a Collection и возвращает минимум (или максимум) элемент согласно естественному упорядочиванию элементов. Вторая форма берет a Comparator в дополнение к Collection и возвращает минимум (или максимум) элемент согласно указанному Comparator.