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 .