Философия Java3 - Брюс Эккель

В следующем примере класс реализует Comparable, а для демонстрации совместимости используется метод стандартной библиотеки Java Arrays.sort():

//: arrays/CompType.java

// Реализация классом интерфейса Comparable.

import java.util.*;

import net.mindview.util.*;

import static net.mindview.util.Print.*;

public class CompType implements Comparable<CompType> { int i. int j;

private static int count = 1; public CompType(int nl, int n2) { i = nl; J = n2;

}

public String toStringO {

String result = "[i = " + i + J = " + j + "]"; if(count++ % 3 == 0)

result += "n"; return result;

}

public int compareTo(CompType rv) {

return (i < rv.i ? -1 : (i == rv.i ? 0 : 1));

}

private static Random r = new Random(47); public static Generator<CompType> generatorO { return new Generator<CompType>() { public CompType nextO {

return new CompType(r.nextInt(100),r.nextInt(100));

}

}:

}

public static void main(String[] args) { CompType[] a =

Generated, array (new CompType[12], generatorO); print("перед сортировкой;"); pri nt(Arrays.toStri ng(a)); Arrays.sort(a); print("после сортировки;");

print(Arrays.toString(a)); продолжение &

}

} /* Output: перед сортировкой:

[[1 = 58, j = 55], [i = 93. j = 61]. [i =61. j = 29] . [i = 68, j = 0], [i = 22, j = 7]. [i = 88, j = 28] , [i = 51, j = 89], [i = 9, j = 78], [i = 98. j = 61]

, [i = 20, j = 58]. [i = 16, j = 40], [i - 11. j - 22] ]

после сортировки:

CCi = 9. j = 78], [i - 11. j - 22], [i - 16. j - 40]

. [i = 20. j = 58]. [i = 22, j = 7]. [i = 51. j = 89]

. [i = 58. j = 55]. [i =61. j = 29]. [i = 68. j = 0]

. [i = 88. j = 28]. [i = 93. j = 61]. [i = 98. j = 61] ]

*///:-

Определяя метод сравнения, вы несете полную ответственность за принятие решения о его результатах. В приведенном примере в сравнении используются только значения i, а значения j игнорируются.

Метод generator() производит объект, реализующий интерфейс Generator, создавая анонимный внутренний класс. Объект строит объекты CompType, инициализируя их случайными значениями. В main() генератор заполняет массив CompType, который затем сортируется. Если интерфейс Comparable не реализован, то при попытке вызова sort() произойдет исключение ClassCastException. Это объясняется тем, что sort() преобразует свой аргумент к типу Comparable.

Теперь представьте, что вы получили класс, который не реализует интерфейс Comparable... а может быть, реализует, но вам не нравится, как он работает, и вы хотели бы задать для типа другой метод сравнения. Для решения проблемы создается отдельный класс, реализующий интерфейс Comparator. Он содержит два метода, compare() и equals(). Впрочем, вам практически никогда не придется реализовывать equals() — разве что при особых требованиях по быстродействию, потому что любой создаваемый класс неявно наследует от класса Object метод equals().

Класс Collections содержит метод reverseOrder(), который создает Comparator для порядка сортировки, обратного по отношению к естественному. Он может быть применен к CompType:

//: arrays/Reverse.java

// Метод Col lections.reverseOrderO

import java util *;

i mport net.mi ndvi ew.uti1.*,

import static net.mindview.util.Print.*;

public class Reverse {

public static void main(String[] args) { CompTypeC] a = Generated.array(

new CompType[12], CompType generatorO); print("перед сортировкой "); print(Arrays.toString(a)). Arrays.sort(a. Col lections. reverseOrderO). print("после сортировки:"); pri nt(Arrays.toStri ng(a));

} /* Output: перед сортировкой:

[[i = 58. j = 55]. [i = 93. j = 61]. [i =61. j = 29] . [i = 68. j = 0]. [i = 22. j = 7]. [i - 88. j - 28] . [i = 51. j = 89]. [i = 9. j = 78]. [i = 98. j = 61]

. [i = 20. j = 58]. [i =16. j = 40]. [i - 11. j - 22] ]

после сортировки:

[[i - 98. j - 61]. [i =93. j = 61]. [i =88. j = 28] . [i = 68. j = 0]. [i = 61. j = 29]. [i = 58. j = 55] . [i = 51. j = 89]. [i = 22. j = 7]. [i = 20. j = 58]

. [i = 16. j = 40]. [i = 11. j = 22]. [i = 9. j = 78] ]

*///:-

Наконец, вы можете написать собственную реализацию Comparator. В следующем примере объекты CompType сравниваются по значениям]' вместо i:

//: arrays/ComparatorTest.java

// Реализация Comparator

import java.util.*:

import net.mindview.util.*:

import static net.mindview.util.Print.*:

class CompTypeComparator implements Comparator<CompType> { public int compare(CompType ol. CompType o2) {

return (ol.j < o2.j ? -1 : (ol.j == o2.j ? 0 : 1)):

}

}

public class ComparatorTest {

public static void main(String[] args) { CompTypeC] a = Generated.array(

new CompType[12], CompType.generatorO); print("перед сортировкой:"): print(Arrays.toString(a)): Arrays.sort(a. new CompTypeComparatorO); print("после сортировки:"): print(Arrays.toString(a));

}

} /* Output: перед сортировкой:

[[i = 58. j = 55]. [i = 93. j = 61]. [i = 61. j = 29] . [i = 68. j = 0]. [i = 22. j = 7]. [i = 88. j = 28] . [i = 51. j = 89]. [i = 9. j = 78]. [i = 98. j = 61]

. [i = 20. j = 58]. [i = 16. j = 40]. [i = 11. j = 22] ]

после сортировки:

[[1 = 68. j = 0]. [i = 22. j = 7]. [i - 11. j - 22]

. [i = 88. j = 28]. [i = 61. j = 29]. [i = 16. j = 40]

. [i = 58. j = 55]. [i = 20. j = 58]. [i = 93. j = 61]

. [i = 98. j = 61]. [i = 9. j = 78]. [i = 51. j = 89] ]

Сортировка массива

Встроенные средства сортировки позволяют отсортировать любой массив примитивов, любой массив объектов, реализующих Comparable или ассоциированных с объектом Comparator1. Следующий пример генерирует случайные объекты String и сортирует их:

//: arrays/StringSorting.java // Sorting an array of Strings, import java.util *; import net.mindview.util.*, import static net.mindview.util.Print *; public class StringSorting {

public static void main(String[] args) {

String[] sa = Generated.array(new String[20],

new RandomGenerator String(5)), print("Before sort. " + Arrays toString(sa)); Arrays sort(sa);

print("After sort. " + Arrays toString(sa)), Arrays.sort(sa, Collections reverseOrder()); print("Reverse sort. " + Arrays toString(sa)); Arrays sort(sa, String CASE_INSENSITIVE_ORDER). print("Case-insensitive sort- " + Arrays toString(sa));

}

} /* Output-

Before sort [YNzbr. nyGcF, OWZnT, cQrGs, eGZMm, JMRoE, suEcU, OneOE, dLsmw, HLGEa,

hKcxr, EqUCB. bklna, Mesbt, WHkjU. rUkZP, gwsqP, zDyCy, RFJQA, HxxHv]

After sort- [EqUCB, HLGEa. HxxHv. JMRoE. Mesbt, OWZnT, OneOE, RFJQA, WHkjU, YNzbr,

bklna, cQrGs, dLsmw, eGZMm, gwsqP, hKcxr, nyGcF, rUkZP. suEcU. zDyCy]

Reverse sort: [zDyCy. suEcU, rUkZP, nyGcF. hKcxr, gwsqP, eGZMm, dLsmw. cQrGs, bklna.

YNzbr. WHkjU, RFJQA, OneOE, OWZnT, Mesbt. JMRoE. HxxHv, HLGEa, EqUCB]

Case-insensitive sort, [bklna. cQrGs. dLsmw, eGZMm, EqUCB, gwsqP, hKcxr, HLGEa, HxxHv,

JMRoE. Mesbt. nyGcF, OneOE. OWZnT. RFJQA. rUkZP. suEcU. WHkjU. YNzbr. zDyCy] *///.-

В выходных данных алгоритма сортировки String бросается в глаза то, что алгоритм является лексикографическим, то есть все слова, начинающиеся с прописных букв, предшествуют любым словам, начинающимся со строчных букв. Если вы хотите, чтобы слова группировались независимо от регистра символов, используйте режим String.CASE_INSENSITIVE_ORDER, как показано в последнем вызове sort() из приведенного примера.

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

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

После того, как массив будет отсортирован, вы сможете быстро найти нужный элемент методом Arrays.binarySearchQ. Попытка вызова binarySearchQ для несортированного массива приведет к непредсказуемым последствиям. В следующем примере генератор RandomGenerator.Integer заполняет массив, после чего тот же генератор используется для получения искомых значений:

//. arrays/ArraySearching java

// Using Arrays binarySearch()

import java util *;

import net.mindview util *;

import static net mindview.util Print *.

public class ArraySearching {

public static void main(String[] args) { Generator<Integer> gen =

new RandomGenerator.Integer(1000). int[] a = ConvertTo primitive(

Generated.array(new Integer[25], gen)). Arrays sort(a).

ргШСОтсортированный массив: " + Arrays toString(a)). while(true) {

int r = gen.nextO.

int location = Arrays binarySearch(a, r). if(location >= 0) {

pnnt("Значение " + r + " находится в позиции " +

location +

a[" + location + "] = " + a[location]); break. // Выход из цикла while

}

} /* Output

Отсортированный массив- [128. 140. 200. 207. 258. 258. 278. 288, 322. 429. 511. 520.

522. 551. 555. 589. 693. 704. 809. 861. 861. 868. 916. 961. 998]

Значение 322 находится в позиции 8. а[8] = 322

*/// ~

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

Если искомое значение найдено, метод Arrays.binarySearchQ возвращает неотрицательный результат. В противном случае возвращается отрицательное значение, представляющее позицию элемента при вставке (при сохранении сортировки массива). Если массив содержит повторяющиеся значения, алгоритм поиска не дает гарантий относительно того, какой именно из дубликатов будет обнаружен. Алгоритм проектировался не для поддержки дубликатов, а для того, чтобы переносить их присутствие. Если вам нужен отсортированный список без повторений элементов, используйте TreeSet (для сохранения порядка сортировки) или LinkedHashSet (для сохранения порядка вставки). Эти классы автоматически берут на себя все детали. Только в ситуациях, критичных по быстродействию, эти классы заменяются массивами с ручным выполнением операций.

При сортировке объектных массивов с использованием Comparator (примитивные массивы не позволяют выполнять сортировку с Comparator) необходимо включать тот же объект Comparator, что и при использовании binarySearch() (перегруженной версии). Например, программу StringSorting.java можно модифицировать для выполнения поиска:

//• arrays/AlphabeticSearch.java // Поиск с Comparator, import java.util.*; import net.mindview.util.*;

public class AlphabeticSearch {

public static void main(String[] args) {

String[] sa = Generated.array(new String[30],

new RandomGenerator String(5)); Arrays.sort(sa. String.CASE_INSENSITIVE_ORDER); System.out.pri ntln(Arrays.toStri ng(sa)); int index = Arrays.binarySearch(sa. sa[10],

Stri ng. CASE JNSENSITI VE_0RDER); System.out.printlпС'Индекс: "+ index + "n"+ sa[index]);

}

} /* Output

[bklna. cQrGs. cXZJo. dLsmw. eGZMm. EqUCB. gwsqP. hKcxr, HLGEa. HqXum, HxxHv, JMRoE. JmzMs. Mesbt, MNvqe, nyGcF, ogoYW, OneOE. OWZnT. RFJQA. rUkZP. sgqia, slJrL, suEcU. uTpnX, vpfFv, WHkjU. xxEAJ, YNzbr, zDyCy] Индекс 10 HxxHv *///.-

Объект Comparator передается перегруженному методу binarySearch() в третьем аргументе. В приведенном примере успех поиска гарантирован, так как искомое значение выбирается из самого массива.

Резюме

В этой главе вы убедились в том, что язык Java предоставляет неплохую поддержку низкоуровневых массивов фиксированного размера. Такие массивы отдают предпочтение производительности перед гибкостью. В исходной версии Java низкоуровневые массивы фиксированного размера были абсолютно необходимы — не только потому, что проектировщики Java решили включить в язык примитивные типы (также по соображениям быстродействия), но и потому, что поддержка контейнеров в этой версии была крайне ограниченной.