Глава 15 Thinking in Java 4th edition |
МАССИВЫ
В конце главы 5 было показано, как определить и инициализировать массив. Программист создает и инициализирует массивы, извлекает из них элементы по целочисленным индексам, а размер массива остается неизменным. Как правило, при работе с массивами этого вполне достаточно, но иногда приходится выполнять более сложные операции, а также оценивать эффективность массива по сравнению с другими контейнерами. В этой главе массивы рассматриваются на более глубоком уровне.Чего не видят фанатики обоих лагерей? Смотрите с минуты 25:40
МАССИВЫ
В конце главы 5 было показано, как определить и инициализировать массив. Программист создает и инициализирует массивы, извлекает из них элементы по целочисленным индексам, а размер массива остается неизменным. Как правило, при работе с массивами этого вполне достаточно, но иногда приходится выполнять более сложные операции, а также оценивать эффективность массива по сравнению с другими контейнерами. В этой главе массивы рассматриваются на более глубоком уровне.
Особенности массивов
В Java существует немало разных способов хранения объектов, почему же массивы занимают особое место?
Массивы отличаются от других контейнеров по трем показателям: эффективность, типизация и возможность хранения примитивов. Массивы Java являются самым эффективным средством хранения и произвольного доступа к последовательности ссылок на объекты. Массив представляет собой простую линейную последовательность, благодаря чему обращения к элементам осуществляются чрезвычайно быстро. За скорость приходится расплачиваться тем, что размер объекта массива фиксируется и не может изменяться на протяжении его жизненного цикла. Как говорилось в главе 11, контейнер ArrayList способен автоматически выделять, дополнительное пространство, выделяя новый блок памяти и перемещая в него все ссылки из старого. Хотя обычно ArrayList отдается предпочтение перед массивами, за гибкость приходится расплачиваться, и ArrayList значительно уступает по эффективности обычному массиву.
И массивы, и контейнеры защищены от возможных злоупотреблений. При выходе за границу массива или контейнера происходит исключение RuntimeException, свидетельствующее об ошибке программиста.
До появления параметризации другим контейнерным классам приходилось работать с объектами так, как если бы они не имели определенного типа. Иначе говоря, объекты рассматривались как принадлежащие к типу Object, корневому для всей иерархии классов в Java. Массивы удобнее «старых» контейнеров тем, что массив создается для хранения конкретного типа. Проверка типов на стадии компиляции не позволит использовать неверный тип или неверно интерпретировать извлекаемый тип. Конечно, Java так или иначе запретит отправить неподходящее сообщение объекту на стадии компиляции или выполнения, так что ни один из способов не является более рискованным по сравнению с другим. Просто будет удобнее, если компилятор укажет на существующую проблему, и снижается вероятность того, что пользователь программы получит неожиданное исключение.
Массив может содержать примитивные типы, а «старые» контейнеры — нет. С другой стороны, параметризованные контейнеры могут проверять тип хранимых объектов, а благодаря автоматической упаковке они работают так, как если бы поддерживали хранение примитивов, поскольку преобразование выполняется автоматически. В следующем примере массивы сравниваются с параметризованными контейнерами:
//: arrays/ContainerComparison.java
import java.util.*;
import static net.mindview.util.Print.*;
class BerylliumSphere {
private static long counter;
private final long id = counter++;
public String toString() { return "Sphere " + id; }
}
public class ContainerComparison {
public static void main(String[] args) {
BerylliumSphere[] spheres = new BerylliumSphere[10];
for(int i = 0; i < 5; i++)
spheres[i] = new BerylliumSphere();
print(Arrays.toString(spheres));
print(spheres[4]);
List<BerylliumSphere> sphereList =
new ArrayList<BerylliumSphere>();
for(int i = 0; i < 5; i++)
sphereList.add(new BerylliumSphere());
print(sphereList);
print(sphereList.get(4));
int[] integers = { 0, 1, 2, 3, 4, 5 };
print(Arrays.toString(integers));
print(integers[4]);
List<Integer> intList = new ArrayList<Integer>(
Arrays.asList(0, 1, 2, 3, 4, 5));
intList.add(97);
print(intList);
print(intList.get(4));
}
}
<spoiler text="Output:">
[Sphere 0, Sphere 1, Sphere 2, Sphere 3, Sphere 4, null, null, null, null, null]
Sphere 4
[Sphere 5, Sphere 6, Sphere 7, Sphere 8, Sphere 9]
Sphere 9
[0, 1, 2, 3, 4, 5]
4
[0, 1, 2, 3, 4, 5, 97]
</spoiler>
Оба способа хранения объектов обеспечивают проверку типов, а единственное очевидное различие заключается в том, что массивы используют для обращения к элементам конструкцию [ ], a List — методы вроде add() или get(). Разработчики языка намеренно сделали массивы и ArrayList настолько похожими, чтобы программисту было концептуально проще переключаться между ними. Но, как было показано в главе 11, контейнеры обладают более широкими возможностями, чем массивы.
С появлением механизма автоматической упаковки контейнеры по удобству работы с примитивами почти не уступают массивам. Единственным реальным преимуществом массивов остается их эффективность. Впрочем, при решении более общих проблем может оказаться, что возможности массивов слишком ограничены, и тогда приходится пользоваться контейнерными классами.
Массив как объект
С каким бы типом массива вы ни работали, идентификатор массива в действительности представляет собой ссылку на объект, созданный в динамической памяти. Этот объект содержит ссылки на другие объекты и создается либо неявно (в синтаксисе инициализации массива), либо явно конструкцией new. Одной из частей объекта массива (а по сути, единственным доступным полем) является доступная только для чтения переменная length, которая указывает, сколько элементов может храниться в объекте массива. Весь доступ к объекту массива ограничивается синтаксисом [ ].
Следующий пример демонстрирует различные способы инициализации массивов и присваивания ссылок на массивы. Он также наглядно показывает, что массивы объектов и массивы примитивных типов практически идентичны. Единственное различие заключается в том, что массивы объектов содержат ссылки, а массивы примитивов содержат сами примитивные значения.
//: arrays/ArrayOptions.java
// Инициализация и повторное присваивание массивов
import java.util.*;
import static net.mindview.util.Print.*;
public class ArrayOptions {
public static void main(String[] args) {
// Массивы объектов:
BerylliumSphere[] a; // Локальная неинициализированная переменная
BerylliumSphere[] b = new BerylliumSphere[5];
// Ссылки в массиве автоматически инициализируются null:
print("b: " + Arrays.toString(b));
BerylliumSphere[] c = new BerylliumSphere[4];
for(int i = 0; i < c.length; i++)
if(c[i] == null) // Проверка ссылки на действительность
c[i] = new BerylliumSphere();
// Агрегатная инициализация:
BerylliumSphere[] d = { new BerylliumSphere(),
new BerylliumSphere(), new BerylliumSphere()
};
// Динамическая агрегатная инициализация:
a = new BerylliumSphere[]{
new BerylliumSphere(), new BerylliumSphere(),
};
// (Завершающая запятая не обязательна в обоих случаях)
print("a.length = " + a.length);
print("b.length = " + b.length);
print("c.length = " + c.length);
print("d.length = " + d.length);
a = d;
print("a.length = " + a.length);
// Массивы примитивов:
int[] e; // Ссылка null
int[] f = new int[5];
// Примитивы в массиве автоматически инициализируются нулями:
print("f: " + Arrays.toString(f));
int[] g = new int[4];
for(int i = 0; i < g.length; i++)
g[i] = i*i;
int[] h = { 11, 47, 93 };
// Ошибка компиляции переменная e не инициализирована:
//!print("e.length = " + e.length);
print("f.length = " + f.length);
print("g.length = " + g.length);
print("h.length = " + h.length);
e = h;
print("e.length = " + e.length);
e = new int[]{ 1, 2 };
print("e.length = " + e.length);
}
}
<spoiler text="Output:">
b: [null, null, null, null, null]
a.length = 2
b.length = 5
c.length = 4
d.length = 3
a.length = 3
f: [0, 0, 0, 0, 0]
f.length = 5
g.length = 4
h.length = 3
e.length = 3
e.length = 2
</spoiler>
Массив а — неинициализированная локальная переменная, и компилятор не позволяет что-либо делать с этой ссылкой до тех пор, пока она не будет соответствующим образом инициализирована. Массив b инициализируется массивом ссылок на объекты BerylliumSpere, хотя ни один такой объект в массив не заносится. Несмотря на это, мы можем запросить размер массива, потому что b указывает на действительный объект. В этом проявляется некоторый недостаток массивов: поле length сообщает, сколько элементов может быть помещено в массив, то есть размер объекта массива, а не количество хранящихся в нем элементов. Тем не менее при создании объекта массива все ссылки автоматически инициализируются значением null, и, чтобы узнать, связан ли некоторый элемент массива с объектом, достаточно проверить ссылку на равенство null. Аналогично, массивы примитивных типов автоматически инициализируются нулями для числовых типов: (char)0 для char и false для boolean.
Массив с демонстрирует создание массива с последующим присваиванием объектов BerylliumSphere всем элементам массива. Массив d демонстрирует синтаксис «агрегатной инициализации», при котором объект массива создается (с ключевым словом new, как массив с) и инициализируется объектами BerylliumSphere, причем все это происходит в одной команде.
Следующую конструкцию инициализации массива можно назвать «динамической агрегатной инициализацией». Агрегатная инициализация, используемая d, должна использоваться в точке определения d, но при втором синтаксисе объект массива может создаваться и использоваться в любой точке. Предположим, методу hide() передается массив объектов BerylliumSphere. Его вызов может выглядеть так:
hide(d);
однако массив, передаваемый в аргументе, также можно создать динамически:
hide(new BerylliumSphere[]{ new BeryllіumSphere(), new BerylliumSphere() });
Во многих ситуациях такой синтаксис оказывается более удобным.
Выражение
a=d;
показывает, как взять ссылку, связанную с одним объектом массива, и присвоить ее другому объекту массива, как это делается с любым другим типом ссылки на объект. В результате a и d указывают на один объект массива в куче. Вторая часть ArrayOptions.java показывает, что примитивные массивы работают точно так же, как массивы объектов, за исключением того, что примитивные значения сохраняются в них напрямую.
Возврат массива
Предположим, вы пишете метод, который должен возвращать не отдельное значение, а целый набор значений. В таких языках, как C и C++, это сделать нелегко, потому что возвращается из метода не массив, а только указатель на массив.
При этом возникают проблемы, поскольку сложности с управлением жизненным циклом массива могут привести к утечке памяти.
В Java вы просто возвращаете массив. Вам не нужно беспокоиться о нем — массив будет существовать до тех пор, пока он вам нужен, а когда надобность в нем отпадет, массив будет уничтожен уборщиком мусора. В качестве примера рассмотрим возвращение массива String:
//: arrays/IceCream.java
// Возвращение массивов из методов
import java.util.*;
public class IceCream {
private static Random rand = new Random(47);
static final String[] FLAVORS = {
"Chocolate", "Strawberry", "Vanilla Fudge Swirl",
"Mint Chip", "Mocha Almond Fudge", "Rum Raisin",
"Praline Cream", "Mud Pie"
};
public static String[] flavorSet(int n) {
if(n > FLAVORS.length)
throw new IllegalArgumentException("Set too big");
String[] results = new String[n];
boolean[] picked = new boolean[FLAVORS.length];
for(int i = 0; i < n; i++) {
int t;
do
t = rand.nextInt(FLAVORS.length);
while(picked[t]);
results[i] = FLAVORS[t];
picked[t] = true;
}
return results;
}
public static void main(String[] args) {
for(int i = 0; i < 7; i++)
System.out.println(Arrays.toString(flavorSet(3)));
}
}
<spoiler text="Output:">
[Rum Raisin, Mint Chip, Mocha Almond Fudge]
[Chocolate, Strawberry, Mocha Almond Fudge]
[Strawberry, Mint Chip, Mocha Almond Fudge]
[Rum Raisin, Vanilla Fudge Swirl, Mud Pie]
[Vanilla Fudge Swirl, Chocolate, Mocha Almond Fudge]
[Praline Cream, Strawberry, Mocha Almond Fudge]
[Mocha Almond Fudge, Strawberry, Mint Chip]
</spoiler>
Метод flavorSet() создает массив results с элементами String. Размер массива равен n; он определяется аргументом, передаваемым при вызове метода. Далее метод случайным образом выбирает элементы из массива FLAVORS и помещает их в массив results, возвращаемый методом. Массив возвращается точно так же, как любой другой объект, — по ссылке. При этом не важно, был ли массив создан методом flavorSet(), или он был создан в другом месте. Массив останется с вами все время, пока он будет нужен, а потом уборщик мусора позаботится о его уничтожении.
Из выходных данных видно, что метод flavorSet() действительно выбирает случайное подмножество элементов при каждом вызове.
Многомерные массивы
Создание многомерных массивов в Java не вызывает особых сложностей. Для многомерных массивов примитивных типов каждый вектор заключается в фигурные скобки:
//: arrays/MultidimensionalPrimitiveArray.java
// Creating multidimensional arrays.
import java.util.*;
public class MultidimensionalPrimitiveArray {
public static void main(String[] args) {
int[][] a = {
{ 1, 2, 3, },
{ 4, 5, 6, },
};
System.out.println(Arrays.deepToString(a));
}
}
<spoiler text="Output:">
[[1, 2, 3], [4, 5, 6]]
</spoiler>
Каждая вложенная пара фигурных скобок описывает новую размерность массива.
В этом примере используется метод Java SE5 Arrays.deepToString(). Как видно из выходных данных, он преобразует многомерные массивы в String.
Массив также может создаваться ключевым словом new. Пример создания трехмерного массива выражением new:
//: arrays/ThreeDWithNew.java
import java.util.*;
public class ThreeDWithNew {
public static void main(String[] args) {
// 3-D array with fixed length:
int[][][] a = new int[2][2][4];
System.out.println(Arrays.deepToString(a));
}
}
<spoiler text="Output:">
[[[0, 0, 0, 0], [0, 0, 0, 0]], [[0, 0, 0, 0], [0, 0, 0, 0]]]
</spoiler>
Как видите, если массиву примитивных типов не заданы явные значения, он автоматически инициализируется значениями по умолчанию. Массивы объектов инициализируются ссылками null.
Векторы массивов, образующих матрицу, могут иметь разную длину (это называется ступенчатым массивом):
//: arrays/RaggedArray.java
import java.util.*;
public class RaggedArray {
public static void main(String[] args) {
Random rand = new Random(47);
// Трехмерный массив с векторами переменной длины:
int[][][] a = new int[rand.nextInt(7)][][];
for(int i = 0; i < a.length; i++) {
a[i] = new int[rand.nextInt(5)][];
for(int j = 0; j < a[i].length; j++)
a[i][j] = new int[rand.nextInt(5)];
}
System.out.println(Arrays.deepToString(a));
}
}
<spoiler text="Output:">
[[], [[0], [0], [0, 0, 0, 0]], [[], [0, 0], [0, 0]],
[[0, 0, 0], [0], [0, 0, 0, 0]],
[[0, 0, 0], [0, 0, 0], [0], []], [[0], [], [0]]]
</spoiler>
Первая конструкция new создает массив, у которого первый элемент имеет случайную длину, а остальные остаются неопределенными. Вторая конструкция new в цикле for заполняет элементы, но оставляет третий индекс неопределенным вплоть до выполнения третьего new.
Массивы с не-примитивными элементами заполняются аналогичным образом. Пример объединения нескольких выражений new в фигурных скобках:
//: arrays/MultidimensionalObjectArrays.java
import java.util.*;
public class MultidimensionalObjectArrays {
public static void main(String[] args) {
BerylliumSphere[][] spheres = {
{ new BerylliumSphere(), new BerylliumSphere() },
{ new BerylliumSphere(), new BerylliumSphere(),
new BerylliumSphere(), new BerylliumSphere() },
{ new BerylliumSphere(), new BerylliumSphere(),
new BerylliumSphere(), new BerylliumSphere(),
new BerylliumSphere(), new BerylliumSphere(),
new BerylliumSphere(), new BerylliumSphere() },
};
System.out.println(Arrays.deepToString(spheres));
}
}
<spoiler text="Output:">
[[Sphere 0, Sphere 1],
[Sphere 2, Sphere 3, Sphere 4, Sphere 5],
[Sphere 6, Sphere 7, Sphere 8, Sphere 9, Sphere 10, Sphere 11, Sphere 12, Sphere 13]]
</spoiler>
Массив spheres также является ступенчатым, то есть длины вложенных списков объектов различаются.
Механизм автоматической упаковки работает с инициализаторами массивов:
//: arrays/AutoboxingArrays.java
import java.util.*;
public class AutoboxingArrays {
public static void main(String[] args) {
Integer[][] a = { // Автоматическая упаковка:
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 },
{ 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 },
{ 51, 52, 53, 54, 55, 56, 57, 58, 59, 60 },
{ 71, 72, 73, 74, 75, 76, 77, 78, 79, 80 },
};
System.out.println(Arrays.deepToString(a));
}
}
<spoiler text="Output:">
[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
[51, 52, 53, 54, 55, 56, 57, 58, 59, 60], [71, 72, 73, 74, 75, 76, 77, 78, 79, 80]]
</spoiler>
А вот как происходит поэлементное построение массива не-примитивных объектов:
//: arrays/AssemblingMultidimensionalArrays.java
// Создание многомерных массивов
import java.util.*;
public class AssemblingMultidimensionalArrays {
public static void main(String[] args) {
Integer[][] a;
a = new Integer[3][];
for(int i = 0; i < a.length; i++) {
a[i] = new Integer[3];
for(int j = 0; j < a[i].length; j++)
a[i][j] = i * j; // Автоматическая упаковка
}
System.out.println(Arrays.deepToString(a));
}
}
<spoiler text="Output:">
[[0, 0, 0], [0, 1, 2], [0, 2, 4]]
</spoiler>
Выражение i*j присутствует только для того, чтобы поместить менее тривиальное значение в Integer.
Метод Arrays.deepToString() работает как с массивами примитивных типов, так и с массивами объектов:
//: arrays/MultiDimWrapperArray.java
// Multidimensional arrays of "wrapper" objects.
import java.util.*;
public class MultiDimWrapperArray {
public static void main(String[] args) {
Integer[][] a1 = { // Автоматическая упаковка
{ 1, 2, 3, },
{ 4, 5, 6, },
};
Double[][][] a2 = { // Автоматическая упаковка
{ { 1.1, 2.2 }, { 3.3, 4.4 } },
{ { 5.5, 6.6 }, { 7.7, 8.8 } },
{ { 9.9, 1.2 }, { 2.3, 3.4 } },
};
String[][] a3 = {
{ "The", "Quick", "Sly", "Fox" },
{ "Jumped", "Over" },
{ "The", "Lazy", "Brown", "Dog", "and", "friend" },
};
System.out.println("a1: " + Arrays.deepToString(a1));
System.out.println("a2: " + Arrays.deepToString(a2));
System.out.println("a3: " + Arrays.deepToString(a3));
}
}
<spoiler text="Output:">
a1: [[1, 2, 3], [4, 5, 6]]
a2: [[[1.1, 2.2], [3.3, 4.4]], [[5.5, 6.6], [7.7, 8.8]], [[9.9, 1.2], [2.3, 3.4]]]
a3: [[The, Quick, Sly, Fox], [Jumped, Over], [The, Lazy, Brown, Dog, and, friend]]
</spoiler>
И снова в массивах Integer и Double механизм автоматической упаковки Java SE5 создает необходимые объекты-«обертки».
Массивы и параметризация
В общем случае массивы и параметризация плохо сочетаются друг с другом. Например, массивы не могут инициализироваться параметризованными типами:
Peel<Banana>[] peels = new Peel<Banana>[10]: // He разрешено
Стирание удаляет информацию о параметре типа, а массив должен знать точный тип хранящихся в нем объектов для обеспечения безопасности типов. Впрочем, параметризовать можно сам тип массива:
//: arrays/ParameterizedArrayType.java
class ClassParameter<T> {
public T[] f(T[] arg) { return arg; }
}
class MethodParameter {
public static <T> T[] f(T[] arg) { return arg; }
}
public class ParameterizedArrayType {
public static void main(String[] args) {
Integer[] ints = { 1, 2, 3, 4, 5 };
Double[] doubles = { 1.1, 2.2, 3.3, 4.4, 5.5 };
Integer[] ints2 =
new ClassParameter<Integer>().f(ints);
Double[] doubles2 =
new ClassParameter<Double>().f(doubles);
ints2 = MethodParameter.f(ints);
doubles2 = MethodParameter.f(doubles);
}
}
Обратите внимание, как удобно использовать параметризованный метод вместо параметризованного класса: вам не придется создавать очередную «версию» класса с параметром для каждого типа, к которому он применяется, и его можно сделать static. Конечно, параметризованный класс не всегда можно заменить параметризованным методом, но такое решение может оказаться предпочтительным.
Как выясняется, не совсем правильно говорить, что вы не можете создавать массивы параметризованных типов. Действительно, компилятор не позволит создать экземпляр массива параметризованного типа, но вы можете создать ссылку на такой массив. Пример:
List<String>[] Is;
Такая конструкция проходит проверку без малейших возражений со стороны компилятора. И хотя вы не можете создать объект массива с параметризацией, можно создать объект непараметризованного типа и преобразовать его:
//: arrays/ArrayOfGenerics.java
// Возможность создания массивов параметризованных типов.
import java.util.*;
public class ArrayOfGenerics {
@SuppressWarnings("unchecked")
public static void main(String[] args) {
List<String>[] ls;
List[] la = new List[10];
ls = (List<String>[])la; //Предупреждение о
// непроверенном преобразовании
ls[0] = new ArrayList<String>();
// Приводит к ошибке на стадии компиляции :
//! ls[1] = new ArrayList<Integer>();
// Проблема: List<String> является подтипом Object
Object[] objects = ls; // Поэтому присваивание возможно
// Компилируется и выполняется без ошибок и предупреждений :
objects[1] = new ArrayList<Integer>();
// Но если ваши потребности достаточно элементарны.
// создать массив параметризованных типов можно, хотя
// и с предупреждением о "непроверенном" преобразовании
List<BerylliumSphere>[] spheres =
(List<BerylliumSphere>[])new List[10];
for(int i = 0; i < spheres.length; i++)
spheres[i] = new ArrayList<BerylliumSphere>();
}
}
Мы видим, что при при получении ссылки на List<String>[] выполняется некоторая проверка на стадии компиляции. Проблема в том, что массивы ковариантны, поэтому List<String>[] также является Object[], поэтому вашему массиву можно присвоить ArrayList<Integer> без выдачи ошибок на стадии компиляции или выполнения.
Если вы уверены в том, что восходящее преобразование выполняться не будет, а ваши потребности относительно просты, можно создать массив параметризованных типов, обеспечивающий простейшую проверку типов на стадии компиляции. Тем не менее параметризованный контейнер практически всегда оказывается более удачным решением, чем массив параметризованных типов.
Создание тестовых данных
При экспериментах с массивами (и программами вообще) полезно иметь возможность простого заполнения массивов тестовыми данными. Инструментарий, описанный в этом разделе, заполняет массив объектными значениями.
Arrays.fill();
Класс Arrays из стандартной библиотеки Java содержит весьма тривиальный метод fill(): он всего лишь дублирует одно значение в каждом элементе массива, а в случае объектов копирует одну ссылку в каждый элемент. Пример:
//: arrays/FillingArrays.java
// Использование Arrays.fill()
import java.util.*;
import static net.mindview.util.Print.*;
public class FillingArrays {
public static void main(String[] args) {
int size = 6;
boolean[] a1 = new boolean[size];
byte[] a2 = new byte[size];
char[] a3 = new char[size];
short[] a4 = new short[size];
int[] a5 = new int[size];
long[] a6 = new long[size];
float[] a7 = new float[size];
double[] a8 = new double[size];
String[] a9 = new String[size];
Arrays.fill(a1, true);
print("a1 = " + Arrays.toString(a1));
Arrays.fill(a2, (byte)11);
print("a2 = " + Arrays.toString(a2));
Arrays.fill(a3, 'x');
print("a3 = " + Arrays.toString(a3));
Arrays.fill(a4, (short)17);
print("a4 = " + Arrays.toString(a4));
Arrays.fill(a5, 19);
print("a5 = " + Arrays.toString(a5));
Arrays.fill(a6, 23);
print("a6 = " + Arrays.toString(a6));
Arrays.fill(a7, 29);
print("a7 = " + Arrays.toString(a7));
Arrays.fill(a8, 47);
print("a8 = " + Arrays.toString(a8));
Arrays.fill(a9, "Hello");
print("a9 = " + Arrays.toString(a9));
// Интервальные операции:
Arrays.fill(a9, 3, 5, "World");
print("a9 = " + Arrays.toString(a9));
}
}
<spoiler text="Output:">
a1 = [true, true, true, true, true, true]
a2 = [11, 11, 11, 11, 11, 11]
a3 = [x, x, x, x, x, x]
a4 = [17, 17, 17, 17, 17, 17]
a5 = [19, 19, 19, 19, 19, 19]
a6 = [23, 23, 23, 23, 23, 23]
a7 = [29.0, 29.0, 29.0, 29.0, 29.0, 29.0]
a8 = [47.0, 47.0, 47.0, 47.0, 47.0, 47.0]
a9 = [Hello, Hello, Hello, Hello, Hello, Hello]
a9 = [Hello, Hello, Hello, World, World, Hello]
</spoiler>
Метод заполняет либо весь массив, либо, как показывают две последние команды, диапазон его элементов. Но, поскольку вызывать Arrays.fill() можно только для одного значения данных, полученные результаты не слишком полезны.
Генераторы данных
Чтобы создавать менее тривиальные массивы данных с более гибкими возможностями, мы воспользуемся концепцией генераторов, представленной в главе 14. Генератор способен выдавать любые данные по вашему выбору (напомню, что он является примером паттерна «стратегия» — разные генераторы представляют разные стратегии). В этом разделе будут представлены некоторые готовые генераторы, но вы также сможете легко определить собственный генератор для своих потребностей. Для начала рассмотрим простейший набор счетных генераторов для всех примитивных типов и String. Классы генераторов вложены в класс CountingGenerator, чтобы они могли обозначаться именами генерируемых объектов. Например, генератор, создающий объекты Integer, будет создаваться выражением new CountingGenerator.Integer():
//: net/mindview/util/CountingGenerator.java
// Simple generator implementations.
package net.mindview.util;
public class CountingGenerator {
public static class
Boolean implements Generator<java.lang.Boolean> {
private boolean value = false;
public java.lang.Boolean next() {
value = !value; // Поочередное переключение
return value;
}
}
public static class
Byte implements Generator<java.lang.Byte> {
private byte value = 0;
public java.lang.Byte next() { return value++; }
}
static char[] chars = ("abcdefghijklmnopqrstuvwxyz" +
"ABCDEFGHIJKLMNOPQRSTUVWXYZ").toCharArray();
public static class
Character implements Generator<java.lang.Character> {
int index = -1;
public java.lang.Character next() {
index = (index + 1) % chars.length;
return chars[index];
}
}
public static class
String implements Generator<java.lang.String> {
private int length = 7;
Generator<java.lang.Character> cg = new Character();
public String() {}
public String(int length) { this.length = length; }
public java.lang.String next() {
char[] buf = new char[length];
for(int i = 0; i < length; i++)
buf[i] = cg.next();
return new java.lang.String(buf);
}
}
public static class
Short implements Generator<java.lang.Short> {
private short value = 0;
public java.lang.Short next() { return value++; }
}
public static class
Integer implements Generator<java.lang.Integer> {
private int value = 0;
public java.lang.Integer next() { return value++; }
}
public static class
Long implements Generator<java.lang.Long> {
private long value = 0;
public java.lang.Long next() { return value++; }
}
public static class
Float implements Generator<java.lang.Float> {
private float value = 0;
public java.lang.Float next() {
float result = value;
value += 1.0;
return result;
}
}
public static class
Double implements Generator<java.lang.Double> {
private double value = 0.0;
public java.lang.Double next() {
double result = value;
value += 1.0;
return result;
}
}
}
Каждый класс реализует некоторое понятие «счетности». В случае CountingGenerator.Character это повторение символов верхнего и нижнего регистра. Класс CountingGenerator.String использует CountingGenerator.Character для заполнения массива символов, который затем преобразуется в String. Размер массива определяется аргументом конструктора. Обратите внимание на то, что CountingGenerator.String использует базовую конструкцию Generator<java.lang.Character> вместо конкретной ссылки на CountingGenerator.Character.
Следующая тестовая программа использует рефлексию с идиомой вложенных генераторов, что позволяет применять ее для любого набора генераторов, построенного по указанному образцу:
//: arrays/GeneratorsTest.java
import net.mindview.util.*;
public class GeneratorsTest {
public static int size = 10;
public static void test(Class<?> surroundingClass) {
for(Class<?> type : surroundingClass.getClasses()) {
System.out.print(type.getSimpleName() + ": ");
try {
Generator<?> g = (Generator<lt;?>)type.newInstance();
for(int i = 0; i < size; i++)
System.out.printf(g.next() + " ");
System.out.println();
} catch(Exception e) {
throw new RuntimeException(e);
}
}
}
public static void main(String[] args) {
test(CountingGenerator.class);
}
}
<spoiler text="Output:">
Double: 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0
Float: 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0
Long: 0 1 2 3 4 5 6 7 8 9
Integer: 0 1 2 3 4 5 6 7 8 9
Short: 0 1 2 3 4 5 6 7 8 9
String: abcdefg hijklmn opqrstu vwxyzAB CDEFGHI JKLMNOP QRSTUVW XYZabcd efghijk lmnopqr
Character: a b c d e f g h i j
Byte: 0 1 2 3 4 5 6 7 8 9
Boolean: true false true false true false true false true false
</spoiler>
Предполагается, что тестируемый класс содержит серию вложенных объектов Generator, каждый из которых имеет конструктор по умолчанию (то есть без аргументов). Рефлексионный метод getClasses() выдает информацию обо всех вложенных классах. Далее метод test() создает экземпляр каждого генератора и выводит результаты, полученные при десятикратном вызове next(). Следующий набор генераторов основан на случайных числах. Так как конструктор Random инициализируется константой, результаты будут повторяться при каждом запуске программы:
//: net/mindview/util/RandomGenerator.java
// Генераторы, выдающие случайные значения.
package net.mindview.util;
import java.util.*;
public class RandomGenerator {
private static Random r = new Random(47);
public static class
Boolean implements Generator<java.lang.Boolean> {
public java.lang.Boolean next() {
return r.nextBoolean();
}
}
public static class
Byte implements Generator<java.lang.Byte> {
public java.lang.Byte next() {
return (byte)r.nextInt();
}
}
public static class
Character implements Generator<java.lang.Character> {
public java.lang.Character next() {
return CountingGenerator.chars[
r.nextInt(CountingGenerator.chars.length)];
}
}
public static class
String extends CountingGenerator.String {
/ Подключение случайного генератора:
{ cg = new Character(); } // Инициализатор
public String() {}
public String(int length) { super(length); }
}
public static class
Short implements Generator<java.lang.Short> {
public java.lang.Short next() {
return (short)r.nextInt();
}
}
public static class
Integer implements Generator<java.lang.Integer> {
private int mod = 10000;
public Integer() {}
public Integer(int modulo) { mod = modulo; }
public java.lang.Integer next() {
return r.nextInt(mod);
}
}
public static class
Long implements Generator<java.lang.Long> {
private int mod = 10000;
public Long() {}
public Long(int modulo) { mod = modulo; }
public java.lang.Long next() {
return new java.lang.Long(r.nextInt(mod));
}
}
public static class
Float implements Generator<java.lang.Float> {
public java.lang.Float next() {
// Отсечение до двух разрядов в дробной части:
int trimmed = Math.round(r.nextFloat() * 100);
return ((float)trimmed) / 100;
}
}
public static class
Double implements Generator<java.lang.Double> {
public java.lang.Double next() {
long trimmed = Math.round(r.nextDouble() * 100);
return ((double)trimmed) / 100;
}
}
}
Как видите, RandomGenerator.String наследует от CountingGenerator.String, просто подключая новый генератор Character.
Чтобы генерируемые числа были не слишком велики, RandomGenerator.Integer по умолчанию берет остаток от деления на 10 000, но перегруженный конструктор позволяет выбрать меньшее значение. Аналогичный подход используется и для RandomGenerator.Long. Для генераторов Float и Double цифры в дробной части усекаются.
Для тестирования RandomGenerator можно воспользоваться уже готовым классом GeneratorsTest:
//: arrays/RandomGeneratorsTest.java
import net.mindview.util.*;
public class RandomGeneratorsTest {
public static void main(String[] args) {
GeneratorsTest.test(RandomGenerator.class);
}
}
<spoiler text="Output:">
Double: 0.73 0.53 0.16 0.19 0.52 0.27 0.26 0.05 0.8 0.76
Float: 0.53 0.16 0.53 0.4 0.49 0.25 0.8 0.11 0.02 0.8
Long: 7674 8804 8950 7826 4322 896 8033 2984 2344 5810
Integer: 8303 3141 7138 6012 9966 8689 7185 6992 5746 3976
Short: 3358 20592 284 26791 12834 -8092 13656 29324 -1423 5327
String: bkInaMe sbtWHkj UrUkZPg wsqPzDy CyRFJQA HxxHvHq XumcXZJ oogoYWM NvqeuTp nXsgqia
Character: x x E A J J m z M s
Byte: -60 -17 55 -14 -5 115 39 -37 79 115
Boolean: false true false false true true true true true true
</spoiler>
Чтобы изменить количество генерируемых значений, воспользуйтесь public-полем GeneratorsTest.size.
Создание массивов с использованием генераторов
Для создания массивов на основе Generator нам потребуются два вспомогательных класса. Первый использует произвольный Generator для получения массива типов, производных от Object. Для решения проблемы с примитивами второй класс получает произвольный массив с объектами-«обертками» и строит для него соответствующий массив примитивов.
public static class Double implements Generator<java.lang.Double> {
public java.lang.Double next() {
long trimmed = Math.round(r.nextDouble() * 100);
return ((double)trimmed) / 100;
}
}
Первый вспомогательный класс может работать в двух режимах, представленных перегруженным статическим методом аrrау(). Первая версия метода получает существующий массив и заполняет его с использованием Generator; вторая версия получает объект Class.Generator и количество элементов и создает новый массив, который также заполняется с использованием Generator. Помните, что при этом создаются только массивы субтипов Object, но не массивы примитивных типов:
//: net/mindview/util/Generated.java
package net.mindview.util;
import java.util.*;
public class Generated {
// Заполнение существующего массиваy:
public static <T> T[] array(T[] a, Generator<T> gen) {
return new CollectionData<T>(gen, a.length).toArray(a);
}
// Создание нового массива:
@SuppressWarnings("unchecked")
public static <T> T[] array(Class<T> type,
Generator<T> gen, int size) {
T[] a =
(T[])java.lang.reflect.Array.newInstance(type, size);
return new CollectionData<T>(gen, size).toArray(a);
}
}
Класс CollectionData создает объект Collection, заполненный элементами, которые были созданы генератором gen. Количество элементов определяется вторым аргументом конструктора. Все субтипы Collection содержат метод toArray(), заполняющий массив-аргумент элементами из Collection. Второй метод использует рефлексию для динамического создания нового массива соответствующего типа и размера. Затем созданный массив заполняется таким же способом, как в первом методе. Чтобы протестировать Generated, мы воспользуемся одним из классов CountingGenerator, описанных в предыдущем разделе:
//: arrays/TestGenerated.java
import java.util.*;
import net.mindview.util.*;
public class TestGenerated {
public static void main(String[] args) {
Integer[] a = { 9, 8, 7, 6 };
System.out.println(Arrays.toString(a));
a = Generated.array(a,new CountingGenerator.Integer());
System.out.println(Arrays.toString(a));
Integer[] b = Generated.array(Integer.class,
new CountingGenerator.Integer(), 15);
System.out.println(Arrays.toString(b));
}
}
<spoiler text="Output:">
[9, 8, 7, 6]
[0, 1, 2, 3]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
</spoiler>
Хотя массив а инициализируется, эти данные перезаписываются при вызове Generated.array(). Инициализация b показывает, как создать заполненный массив «с нуля».
Параметризация не работает с примитивами, поэтому для заполнения примитивных массивов будут использоваться генераторы. Для решения этой проблемы мы создадим преобразователь, который получает произвольный массив объектных «оберток» и преобразует его в массив соответствующих примитивных типов. Без него нам пришлось бы создавать специализированные генераторы для всех примитивов.
//: net/mindview/util/ConvertTo.java
package net.mindview.util;
public class ConvertTo {
public static boolean[] primitive(Boolean[] in) {
boolean[] result = new boolean[in.length];
for(int i = 0; i < in.length; i++)
result[i] = in[i]; // Autounboxing
return result;
}
public static char[] primitive(Character[] in) {
char[] result = new char[in.length];
for(int i = 0; i < in.length; i++)
result[i] = in[i];
return result;
}
public static byte[] primitive(Byte[] in) {
byte[] result = new byte[in.length];
for(int i = 0; i < in.length; i++)
result[i] = in[i];
return result;
}
public static short[] primitive(Short[] in) {
short[] result = new short[in.length];
for(int i = 0; i < in.length; i++)
result[i] = in[i];
return result;
}
public static int[] primitive(Integer[] in) {
int[] result = new int[in.length];
for(int i = 0; i < in.length; i++)
result[i] = in[i];
return result;
}
public static long[] primitive(Long[] in) {
long[] result = new long[in.length];
for(int i = 0; i < in.length; i++)
result[i] = in[i];
return result;
}
public static float[] primitive(Float[] in) {
float[] result = new float[in.length];
for(int i = 0; i < in.length; i++)
result[i] = in[i];
return result;
}
public static double[] primitive(Double[] in) {
double[] result = new double[in.length];
for(int i = 0; i < in.length; i++)
result[i] = in[i];
return result;
}
}
Каждая версия primitive() создает примитивный массив правильной длины, а затем копирует элементы из массива in. Обратите внимание на выполнение автоматической распаковки в выражении
result[i] = in[i];
Пример использования ConvertTo с обеими версиями Generated.array():
//: arrays/PrimitiveConversionDemonstration.java
import java.util.*;
import net.mindview.util.*;
public class PrimitiveConversionDemonstration {
public static void main(String[] args) {
Integer[] a = Generated.array(Integer.class,
new CountingGenerator.Integer(), 15);
int[] b = ConvertTo.primitive(a);
System.out.println(Arrays.toString(b));
boolean[] c = ConvertTo.primitive(
Generated.array(Boolean.class,
new CountingGenerator.Boolean(), 7));
System.out.println(Arrays.toString(c));
}
}
<spoiler text="Output:">
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
[true, false, true, false, true, false, true]
</spoiler>
Наконец, следующая программа тестирует инструментарий создания массивов с классами RandomGenerator:
//: arrays/TestArrayGeneration.java
// Test the tools that use generators to fill arrays.
import java.util.*;
import net.mindview.util.*;
import static net.mindview.util.Print.*;
public class TestArrayGeneration {
public static void main(String[] args) {
int size = 6;
boolean[] a1 = ConvertTo.primitive(Generated.array(
Boolean.class, new RandomGenerator.Boolean(), size));
print("a1 = " + Arrays.toString(a1));
byte[] a2 = ConvertTo.primitive(Generated.array(
Byte.class, new RandomGenerator.Byte(), size));
print("a2 = " + Arrays.toString(a2));
char[] a3 = ConvertTo.primitive(Generated.array(
Character.class,
new RandomGenerator.Character(), size));
print("a3 = " + Arrays.toString(a3));
short[] a4 = ConvertTo.primitive(Generated.array(
Short.class, new RandomGenerator.Short(), size));
print("a4 = " + Arrays.toString(a4));
int[] a5 = ConvertTo.primitive(Generated.array(
Integer.class, new RandomGenerator.Integer(), size));
print("a5 = " + Arrays.toString(a5));
long[] a6 = ConvertTo.primitive(Generated.array(
Long.class, new RandomGenerator.Long(), size));
print("a6 = " + Arrays.toString(a6));
float[] a7 = ConvertTo.primitive(Generated.array(
Float.class, new RandomGenerator.Float(), size));
print("a7 = " + Arrays.toString(a7));
double[] a8 = ConvertTo.primitive(Generated.array(
Double.class, new RandomGenerator.Double(), size));
print("a8 = " + Arrays.toString(a8));
}
}
<spoiler text="Output:">
a1 = [true, false, true, false, false, true]
a2 = [104, -79, -76, 126, 33, -64]
a3 = [Z, n, T, c, Q, r]
a4 = [-13408, 22612, 15401, 15161, -28466, -12603]
a5 = [7704, 7383, 7706, 575, 8410, 6342]
a6 = [7674, 8804, 8950, 7826, 4322, 896]
a7 = [0.01, 0.2, 0.4, 0.79, 0.27, 0.45]
a8 = [0.16, 0.87, 0.7, 0.66, 0.87, 0.59]
</spoiler>
Как видите, все версии ConvertTo.primitive() работают правильно.
Вспомогательный инструментарий Arrays
В библиотеку java.util включен класс Arrays, содержащий набор вспомогательных статических методов для работы с массивами. Основных методов шесть: equals() сравнивает два массива (также существует версия deepEquals() для многомерных массивов); fill() был описан ранее в этой главе; sort() сортирует массив; binarySearch( ищет элемент в отсортированном массиве; toString() создает представление массива в формате String, a hashCode() генерирует хеш-код массива. Все эти методы перегружены для всех примитивных типов и Object. Кроме того, метод Arrays.asList() преобразует любую последовательность или массив в контейнер List (см. главу 11).
Прежде чем обсуждать методы Arrays, следует рассмотреть еще один полезный метод, не входящий в Arrays.
Копирование массива
Стандартная библиотека Java содержит статический метод System.arraycopy(), который копирует массивы значительно быстрее, чем при ручном копировании в цикле for. Метод System.arraycopy() перегружен для работы со всеми типами. Пример для массивов int:
//: arrays/CopyingArrays.java
// Using System.arraycopy()
import java.util.*;
import static net.mindview.util.Print.*;
public class CopyingArrays {
public static void main(String[] args) {
int[] i = new int[7];
int[] j = new int[10];
Arrays.fill(i, 47);
Arrays.fill(j, 99);
print("i = " + Arrays.toString(i));
print("j = " + Arrays.toString(j));
System.arraycopy(i, 0, j, 0, i.length);
print("j = " + Arrays.toString(j));
int[] k = new int[5];
Arrays.fill(k, 103);
System.arraycopy(i, 0, k, 0, k.length);
print("k = " + Arrays.toString(k));
Arrays.fill(k, 103);
System.arraycopy(k, 0, i, 0, k.length);
print("i = " + Arrays.toString(i));
// Objects:
Integer[] u = new Integer[10];
Integer[] v = new Integer[5];
Arrays.fill(u, new Integer(47));
Arrays.fill(v, new Integer(99));
print("u = " + Arrays.toString(u));
print("v = " + Arrays.toString(v));
System.arraycopy(v, 0, u, u.length/2, v.length);
print("u = " + Arrays.toString(u));
}
}
<spoiler text="Output:">
i = [47, 47, 47, 47, 47, 47, 47]
j = [99, 99, 99, 99, 99, 99, 99, 99, 99, 99]
j = [47, 47, 47, 47, 47, 47, 47, 99, 99, 99]
k = [47, 47, 47, 47, 47]
i = [103, 103, 103, 103, 103, 47, 47]
u = [47, 47, 47, 47, 47, 47, 47, 47, 47, 47]
v = [99, 99, 99, 99, 99]
u = [47, 47, 47, 47, 47, 99, 99, 99, 99, 99]
</spoiler>
В аргументах arraycopy() передается исходный массив, начальная позиция копирования в исходном массиве, приемный массив, начальная позиция копирования в приемном массиве и количество копируемых элементов. Естественно, любое нарушение границ массива приведет к исключению.
Приведенный пример показывает, что копироваться могут как примитивные, так и объектные массивы. Однако при копировании объектных массивов копируются только ссылки, но не сами объекты. Такая процедура называется поверхностным копированием.System.arraycopy() не выполняет ни автоматической упаковки, ни автоматической распаковки — типы двух массивов должны полностью совпадать.
Сравнение массивов
Класс Arrays содержит метод equals() для проверки на равенство целых массивов. Метод перегружен для примитивов и Object. Чтобы два массива считались равными, они должны содержать одинаковое количество элементов, и каждый элемент должен быть эквивалентен соответствующему элементу другого массива (проверка осуществляется вызовом equals() для каждой пары; для примитивов используется метод equals() объектной «обертки» — например, Integer.equals() для int). Пример:
//: arrays/ComparingArrays.java
// Using Arrays.equals()
import java.util.*;
import static net.mindview.util.Print.*;
public class ComparingArrays {
public static void main(String[] args) {
int[] a1 = new int[10];
int[] a2 = new int[10];
Arrays.fill(a1, 47);
Arrays.fill(a2, 47);
print(Arrays.equals(a1, a2));
a2[3] = 11;
print(Arrays.equals(a1, a2));
String[] s1 = new String[4];
Arrays.fill(s1, "Hi");
String[] s2 = { new String("Hi"), new String("Hi"),
new String("Hi"), new String("Hi") };
print(Arrays.equals(s1, s2));
}
}
<spoiler text="Output:">
true
false
true
</spoiler>
Сначала массивы a1 и a2 полностью совпадают, поэтому результат сравнения равен true, но после изменения одного из элементов будет получен результат false. В последнем случае все элементы s1 указывают на один объект, тогда как s2 содержит пять разных объектов. Однако проверка равенства определяется содержимым (с вызовом Object.equals()), поэтому результат равен true.
Сравнение элементов массивов
Сравнения, выполняемые в ходе сортировки, зависят от фактического типа объектов. Конечно, можно написать разные методы сортировки для всех возможных типов, но такой код придется модифицировать при появлении новых типов.
Главной целью проектирования является «отделение того, что может измениться, от того, что остается неизменным». В данном случае неизменным остается общий алгоритм сортировки, а изменяется способ сравнения объектов. Вместо того, чтобы размещать код сравнения в разных функциях сортировки, мы воспользуемся паттерном проектирования «стратегия». В этом паттерне переменная часть кода инкапсулируется в отдельном классе. Объект стратегии передается коду, который остается неизменным, и последний использует стратегию для реализации своего алгоритма. При этом разные объекты выражают разные способы сравнения, но передаются универсальному коду сортировки.
В Java функциональность сравнения может выражаться двумя способами. Первый основан на «естественном» методе сравнения, который включается в класс при реализации java.lang.Comparable — очень простого интерфейса с единственным методом compareTo(). В аргументе метод получает другой объект того же типа. Он выдает отрицательное значение, если текущий объект меньше аргумента, нуль при равенстве и положительное значение, если текущий объект больше аргумента.
В следующем примере класс реализует 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 n1, int n2) {
i = n1;
j = n2;
}
public String toString() {
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> generator() {
return new Generator<CompType>() {
public CompType next() {
return new CompType(r.nextInt(100),r.nextInt(100));
}
};
}
public static void main(String[] args) {
CompType[] a =
Generated.array(new CompType[12], generator());
print("before sorting:");
print(Arrays.toString(a));
Arrays.sort(a);
print("after sorting:");
print(Arrays.toString(a));
}
}
<spoiler text="Output:">
before sorting:
[[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]
]
after sorting:
[[i = 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]
]
</spoiler>
Определяя метод сравнения, вы несете полную ответственность за принятие решения о его результатах. В приведенном примере в сравнении используются только значения і, а значения 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
// The Collections.reverseOrder() Comparator
import java.util.*;
import net.mindview.util.*;
import static net.mindview.util.Print.*;
public class Reverse {
public static void main(String[] args) {
CompType[] a = Generated.array(
new CompType[12], CompType.generator());
print("before sorting:");
print(Arrays.toString(a));
Arrays.sort(a, Collections.reverseOrder());
print("after sorting:");
print(Arrays.toString(a));
}
}
<spoiler text="Output:">
before sorting:
[[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]
]
after sorting:
[[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]
]
</spoiler>
Наконец, вы можете написать собственную реализацию Comparator. В следующем примере объекты CompType сравниваются по значениям j вместо і:
//: 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 o1, CompType o2) {
return (o1.j < o2.j ? -1 : (o1.j == o2.j ? 0 : 1));
}
}
public class ComparatorTest {
public static void main(String[] args) {
CompType[] a = Generated.array(
new CompType[12], CompType.generator());
print("before sorting:");
print(Arrays.toString(a));
Arrays.sort(a, new CompTypeComparator());
print("after sorting:");
print(Arrays.toString(a));
}
}
<spoiler text="Output:">
before sorting:
[[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]
]
after sorting:
[[i = 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]
]
</spoiler>
Сортировка массива
Встроенные средства сортировки позволяют отсортировать любой массив примитивов, любой массив объектов, реализующих Comparable или ассоциированных с объектом Comparator. Следующий пример генерирует случайные объекты 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));
}
}
<spoiler text="Output:">
Before sort: [YNzbr, nyGcF, OWZnT, cQrGs, eGZMm, JMRoE, suEcU, OneOE, dLsmw, HLGEa,
hKcxr, EqUCB, bkIna, Mesbt, WHkjU, rUkZP, gwsqP, zDyCy, RFJQA, HxxHv]
After sort: [EqUCB, HLGEa, HxxHv, JMRoE, Mesbt, OWZnT, OneOE, RFJQA, WHkjU, YNzbr,
bkIna, cQrGs, dLsmw, eGZMm, gwsqP, hKcxr, nyGcF, rUkZP, suEcU, zDyCy]
Reverse sort: [zDyCy, suEcU, rUkZP, nyGcF, hKcxr, gwsqP, eGZMm, dLsmw, cQrGs, bkIna,
YNzbr, WHkjU, RFJQA, OneOE, OWZnT, Mesbt, JMRoE, HxxHv, HLGEa, EqUCB]
Case-insensitive sort: [bkIna, cQrGs, dLsmw, eGZMm, EqUCB, gwsqP, hKcxr, HLGEa, HxxHv,
JMRoE, Mesbt, nyGcF, OneOE, OWZnT, RFJQA, rUkZP, suEcU, WHkjU, YNzbr, zDyCy]
</spoiler>
В выходных данных алгоритма сортировки String бросается в глаза то, что алгоритм является лексикографическим, то есть все слова, начинающиеся с прописных букв, предшествуют любым словам, начинающимся со строчных букв. Если вы хотите, чтобы слова группировались независимо от регистра символов, используйте режим String.CASE_INSENSITIVE_ORDER, как показано в последнем вызове sort() из приведенного примера.
Алгоритм сортировки, используемый стандартной библиотекой Java, спроектирован в расчете на оптимальность для сортируемого типа — быстрая сортировка для примитивов, надежная сортировка слиянием для объектов. Обычно вам не приходится беспокоиться о быстродействии, если только профайлер не укажет, что процесс сортировки тормозит работу программы.
Поиск в отсортированном массиве
После того, как массив будет отсортирован, вы сможете быстро найти нужный элемент методом Arrays.binarySearch(). Попытка вызова binarySearch() для несортированного массива приведет к непредсказуемым последствиям. В следующем примере генератор 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);
print("Sorted array: " + Arrays.toString(a));
while(true) {
int r = gen.next();
int location = Arrays.binarySearch(a, r);
if(location >= 0) {
print("Location of " + r + " is " + location +
", a[" + location + "] = " + a[location]);
break; // Out of while loop
}
}
}
}
<spoiler text="Output:">
Sorted array: [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]
Location of 322 is 8, a[8] = 322
</spoiler>
Цикл while генерирует случайные значения как искомые до тех пор, пока одно из них не будет найдено в массиве.
Если искомое значение найдено, метод Arrays.binarySearch() возвращает неотрицательный результат. В противном случае возвращается отрицательное значение, представляющее позицию элемента при вставке (при сохранении сортировки массива). Если массив содержит повторяющиеся значения, алгоритм поиска не дает гарантий относительно того, какой именно из дубликатов будет обнаружен. Алгоритм проектировался не для поддержки дубликатов, а для того, чтобы переносить их присутствие. Если вам нужен отсортированный список без повторений элементов, используйте 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.println(Arrays.toString(sa));
int index = Arrays.binarySearch(sa, sa[10],
String.CASE_INSENSITIVE_ORDER);
System.out.println("Index: "+ index + "\n"+ sa[index]);
}
}
<spoiler text="Output:">
[bkIna, 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]
Index: 10
HxxHv
</spoiler>
Объект Comparator передается перегруженному методу binarySearch() в третьем аргументе. В приведенном примере успех поиска гарантирован, так как искомое значение выбирается из самого массива.
Резюме
В этой главе вы убедились в том, что язык Java предоставляет неплохую поддержку низкоуровневых массивов фиксированного размера. Такие массивы отдают предпочтение производительности перед гибкостью. В исходной версии Java низкоуровневые массивы фиксированного размера были абсолютно необходимы — не только потому, что проектировщики Java решили включить в язык примитивные типы (также по соображениям быстродействия), но и потому, что поддержка контейнеров в этой версии была крайне ограниченной.
В последующих версиях Java поддержка контейнеров была значительно улучшена. Сейчас контейнеры превосходят массивы во всех отношениях, кроме быстродействия, хотя производительность контейнеров была значительно улучшена. С добавлением автоматической упаковки и параметризации хранение примитивов в контейнерах требует меньших усилий и способствует дальнейшему переходу с низкоуровневых массивов на контейнеры. Так как параметризация открыла доступ к типизованным контейнерам, в этом отношении массивы тоже утратили исходные преимущества.
Как было показано в этой главе, параметризация плохо сочетается с контейнерами. Даже если вам удастся тем или иным способом заставить их работать вместе, во время компиляции вы будете получать предупреждения.
Все эти факторы показывают, что при программировании для последних версий Java следует отдавать предпочтение контейнерам перед массивами. На массивы следует переходить только при критичных требованиях по быстродействию — и только в том случае, если переход принесет ощутимую пользу.
------------------------
ТРИО теплый пол отзыв
Vkjust отзыв
Заработок на сокращении ссылок
Earnings on reducing links
Код PHP на HTML сайты
Я уже пять лет не занимаюсь сайтом, так как работаю по 12 часов. Образование у меня среднее, и по этому нет нормальной работы. Если бы сайт приносил по 100$ в месяц, я бы добавлял по 50 статей каждый месяц. Если отправите пожертвования, я оставлю Ваши имена и фамилии в списке благодетелей !
Bitcoin: 1AP3JCZVFpHzZwcAyNztbrbFFiLdnKbY1j
Litecoin LfHXHz4k6LnDNNvCodd5pj9aW4Qk67KoUD
Dogecoin D9HHvKNFZxRhjtoh6uZYjMjgcZewwiUME9
Есть также другие кошельки.
Чего не видят фанатики обоих лагерей? Смотрите с минуты 25:40
Категория: Книги по Java
Комментарии |