1. введение
В этом уроке мы рассмотрим java.util.Массивы , служебный класс, который является частью Java с Java 1.2.
Используя Массивы, мы можем создавать, сравнивать, сортировать, искать, передавать и преобразовывать массивы.
2. Создание
Давайте рассмотрим некоторые способы создания массивов: copyOf , copyOfRange и fill.
2.1. copyOf и copyOfRange
Чтобы использовать copyOfRange , нам нужен наш исходный массив и начальный индекс (включительно) и конечный индекс (эксклюзивно), которые мы хотим скопировать:
String[] intro = new String[] { "once", "upon", "a", "time" };
String[] abridgement = Arrays.copyOfRange(storyIntro, 0, 3);
assertArrayEquals(new String[] { "once", "upon", "a" }, abridgement);
assertFalse(Arrays.equals(intro, abridgement));И чтобы использовать копию , мы возьмем intro и целевой размер массива, и мы получим новый массив этой длины:
String[] revised = Arrays.copyOf(intro, 3); String[] expanded = Arrays.copyOf(intro, 5); assertArrayEquals(Arrays.copyOfRange(intro, 0, 3), revised); assertNull(expanded[4]);
Обратите внимание, что копия передает массив с null s, если ваш целевой размер больше исходного размера.
2.2. заполнить
Другой способ, которым мы можем создать массив фиксированной длины,-это fill, , который полезен, когда нам нужен массив, в котором все элементы одинаковы:
String[] stutter = new String[3]; Arrays.fill(stutter, "once"); assertTrue(Stream.of(stutter) .allMatch(el -> "once".equals(el));
Проверять setAll чтобы создать массив, в котором элементы разные.
Обратите внимание, что нам нужно заранее создать экземпляр массива–в отличие от чего-то вроде String[].fill(“один раз” , 3) ; –поскольку эта функция была введена до того, как дженерики были доступны в языке.
3. Сравнение
Теперь перейдем к методам сравнения массивов.
3.1. равные и глубокие равенства
Мы можем использовать equals для простого сравнения массивов по размеру и содержимому. Если мы добавим null в качестве одного из элементов, проверка содержимого завершится неудачей:
assertTrue(
Arrays.equals(new String[] { "once", "upon", "a", "time" }, intro));
assertFalse(
Arrays.equals(new String[] { "once", "upon", "a", null }, intro));Когда у нас есть вложенные или многомерные массивы, мы можем использовать deepEquals не только для проверки элементов верхнего уровня, но и для рекурсивного выполнения проверки:
Object[] story = new Object[]
{ intro, new String[] { "chapter one", "chapter two" }, end };
Object[] copy = new Object[]
{ intro, new String[] { "chapter one", "chapter two" }, end };
assertTrue(Arrays.deepEquals(story, copy));
assertFalse(Arrays.equals(story, copy));Обратите внимание, как deep quals проходит, но равно терпит неудачу .
Это связано с тем , что deepEquals в конечном счете вызывает себя каждый раз, когда сталкивается с массивом , в то время как equals просто сравнивает ссылки на под массивы.
Кроме того, это делает опасным вызов массива с самоссылкой!
3.2. Хэш-код и deepHashCode
Реализация hashCode даст нам другую часть контракта equals /| hashCode , который рекомендуется для объектов Java. Мы используем Хэш-код для вычисления целого числа на основе содержимого массива:
Object[] looping = new Object[]{ intro, intro };
int hashBefore = Arrays.hashCode(looping);
int deepHashBefore = Arrays.deepHashCode(looping);Теперь мы устанавливаем для элемента исходного массива значение null и вычисляем хэш-значения:
intro[3] = null; int hashAfter = Arrays.hashCode(looping);
В качестве альтернативы deepHashCode проверяет вложенные массивы на совпадение количества элементов и содержимого. Если мы пересчитаем с помощью deepHashCode :
int deepHashAfter = Arrays.deepHashCode(looping);
Теперь мы видим разницу в этих двух методах:
assertEquals(hashAfter, hashBefore); assertNotEquals(deepHashAfter, deepHashBefore);
deepHashCode – это базовый расчет, используемый при работе со структурами данных, такими как HashMap и HashSet на массивах .
4. Сортировка и поиск
Далее давайте рассмотрим сортировку и поиск массивов.
4.1. сортировка
Если наши элементы являются примитивами или реализуют Comparable , мы можем использовать sort для выполнения встроенной сортировки:
String[] sorted = Arrays.copyOf(intro, 4);
Arrays.sort(sorted);
assertArrayEquals(
new String[]{ "a", "once", "time", "upon" },
sorted);Позаботьтесь о том , чтобы сортировка мутировала исходную ссылку , поэтому мы выполняем копию здесь.
сортировка будет использовать другой алгоритм для разных типов элементов массива. Примитивные типы используют быструю сортировку с двойным поворотом и Типы объектов используют Timsort . Оба имеют средний случай O(n log(n)) для случайно отсортированного массива.
Начиная с Java 8, parallelSort доступен для параллельной сортировки-слияния. Он предлагает параллельный метод сортировки с использованием нескольких задач Arrays.sort .
4.2. Бинарный поиск
Поиск в несортированном массиве является линейным, но если у нас есть отсортированный массив, то мы можем сделать это в O(log n) , что мы можем сделать с помощью BinarySearch:
int exact = Arrays.binarySearch(sorted, "time");
int caseInsensitive = Arrays.binarySearch(sorted, "TiMe", String::compareToIgnoreCase);
assertEquals("time", sorted[exact]);
assertEquals(2, exact);
assertEquals(exact, caseInsensitive);Если мы не предоставляем Компаратор в качестве третьего параметра, то двоичный поиск рассчитывает на то, что наш тип элемента имеет тип Сопоставимый .
И снова обратите внимание, что если ваш массив сначала не отсортирован, то двоичный поиск не будет работать так, как мы ожидаем!
5. Потоковая передача
Как мы видели ранее, Массивы были обновлены в Java 8, чтобы включить методы, использующие API потока, такие как параллельная сортировка (упомянутая выше), поток и setAll.
5.1. поток
stream предоставляет нам полный доступ к API потока для нашего массива:
Assert.assertEquals(Arrays.stream(intro).count(), 4); exception.expect(ArrayIndexOutOfBoundsException.class); Arrays.stream(intro, 2, 1).count();
Мы можем предоставить включающие и исключающие индексы для потока, однако мы должны ожидать исключения ArrayIndexOutOfBoundsException , если индексы не в порядке, отрицательны или находятся вне диапазона.
6. Трансформация
Наконец, toString, | as List, и set All дают нам несколько различных способов преобразования массивов.
6.1. toString и Deept-string
Отличный способ получить читаемую версию нашего исходного массива-это использовать toString:
assertEquals("[once, upon, a, time]", Arrays.toString(storyIntro));
Опять же мы должны использовать глубокую версию для печати содержимого вложенных массивов :
assertEquals( "[[once, upon, a, time], [chapter one, chapter two], [the, end]]", Arrays.deepToString(story));
6.2. asList
Наиболее удобным из всех методов Arrays для нас является asList. У нас есть простой способ превратить массив в список:
Listrets = Arrays.asList(storyIntro); assertTrue(rets.contains("upon")); assertTrue(rets.contains("time")); assertEquals(rets.size(), 4);
Однако возвращаемый Список будет иметь фиксированную длину, поэтому мы не сможем добавлять или удалять элементы .
Обратите также внимание, что, как ни странно, java.util.Массивы имеет свой собственный ArrayList подкласс, который asList возвращает . Это может быть очень обманчиво при отладке!
6.3. setAll
С помощью set All мы можем установить все элементы массива с функциональным интерфейсом. Реализация генератора принимает позиционный индекс в качестве параметра:
String[] longAgo = new String[4];
Arrays.setAll(longAgo, i -> this.getWord(i));
assertArrayEquals(longAgo, new String[]{"a","long","time","ago"});И, конечно, обработка исключений-одна из самых рискованных частей использования лямбд. Поэтому помните, что здесь если лямбда-код создает исключение, то Java не определяет конечное состояние массива.
7. Параллельный Префикс
Еще один новый метод в Массивы , введенные с Java 8, являются параллельным префиксом . С параллельным префиксом мы можем работать с каждым элементом входного массива кумулятивным образом.
7.1. parallelPrefix
Если оператор выполняет сложение, как в следующем примере, [1, 2, 3, 4] приведет к [1, 3, 6, 10]:
int[] arr = new int[] { 1, 2, 3, 4};
Arrays.parallelPrefix(arr, (left, right) -> left + right);
assertThat(arr, is(new int[] { 1, 3, 6, 10}));Кроме того, мы можем указать поддиапазон для операции:
int[] arri = new int[] { 1, 2, 3, 4, 5 };
Arrays.parallelPrefix(arri, 1, 4, (left, right) -> left + right);
assertThat(arri, is(new int[] { 1, 2, 5, 9, 5 }));Обратите внимание, что метод выполняется параллельно, поэтому кумулятивная операция должна быть без побочных эффектов и ассоциативной .
Для неассоциативной функции:
int nonassociativeFunc(int left, int right) {
return left + right*left;
}использование параллельного префикса приведет к противоречивым результатам:
@Test
public void whenPrefixNonAssociative_thenError() {
boolean consistent = true;
Random r = new Random();
for (int k = 0; k < 100_000; k++) {
int[] arrA = r.ints(100, 1, 5).toArray();
int[] arrB = Arrays.copyOf(arrA, arrA.length);
Arrays.parallelPrefix(arrA, this::nonassociativeFunc);
for (int i = 1; i < arrB.length; i++) {
arrB[i] = nonassociativeFunc(arrB[i - 1], arrB[i]);
}
consistent = Arrays.equals(arrA, arrB);
if(!consistent) break;
}
assertFalse(consistent);
}7.2. Производительность
Параллельное вычисление префиксов обычно более эффективно, чем последовательные циклы, особенно для больших массивов. При запуске микро-бенчмарка на машине Intel Xeon(6 ядер) с JMH мы видим значительное повышение производительности:
Benchmark Mode Cnt Score Error Units largeArrayLoopSum thrpt 5 9.428 ± 0.075 ops/s largeArrayParallelPrefixSum thrpt 5 15.235 ± 0.075 ops/s Benchmark Mode Cnt Score Error Units largeArrayLoopSum avgt 5 105.825 ± 0.846 ops/s largeArrayParallelPrefixSum avgt 5 65.676 ± 0.828 ops/s
Вот тестовый код:
@Benchmark
public void largeArrayLoopSum(BigArray bigArray, Blackhole blackhole) {
for (int i = 0; i < ARRAY_SIZE - 1; i++) {
bigArray.data[i + 1] += bigArray.data[i];
}
blackhole.consume(bigArray.data);
}
@Benchmark
public void largeArrayParallelPrefixSum(BigArray bigArray, Blackhole blackhole) {
Arrays.parallelPrefix(bigArray.data, (left, right) -> left + right);
blackhole.consume(bigArray.data);
}7. Заключение
В этой статье мы узнали, как некоторые методы создания, поиска, сортировки и преобразования массивов с помощью java.util.Массивы класс.
Этот класс был расширен в более поздних выпусках Java с включением методов создания и потребления потоков в Java 8 и методов несоответствия в Java 9 .
Источник этой статьи, как всегда, на Github .