В этой статье мы представляем исчерпывающую статью, в которой объясняется проблема создания универсальных массивов. Язык программирования Java добавил дженерики в сентябре 2004 года в выпуске Java 5.0 «Tiger». Система обобщений или параметризации типов расширяет существующую систему типов Java, обеспечивая безопасность типов.
1. Введение
У Java есть Платформа Коллекций, предоставляющая библиотеку общих структур данных для использования в разработке программного обеспечения Java. В Collections Framework отсутствует одна структура данных — массив. Тем не менее, Java Collections Framework имеет типизированные структуры данных ArrayList.java и Vector.java. Обе структуры данных используют динамический массив одного измерения, который использует базовый массив java.lang.Object.
Java предоставляет встроенный массив, который является объектом, который включен в языковую спецификацию начиная с Java 1.0 с 1995 года. В качестве объекта встроенный массив объявляется и создается в Java-коде в виде частиц. Встроенный массив представляет собой контейнер объектов с фиксированным числом и длиной, возможно, многих измерений.
Тем не менее, безопасность типов во время компиляции с использованием дженериков не полностью реализована. Особенно со встроенным объектом массива.
2. Универсальные массивы
Проблема в том, что дженерики используются со встроенным объектом массива в Java. Рассмотрим следующий класс Java, TestArray1.java, который объявляет два универсальных массива вокруг одного параметра универсального типа E. Исходный код класса Java:
|
1
2
3
|
class TestArray1 { public E[] array = new E[10];}//end class TestArray1 |
Исходный код для TestArray1.java является только декларативным, массивы не используются. Написано два варианта использования универсального массива: один для универсального массива в качестве атрибута класса, а другой — с использованием универсального массива в статическом (т. Е. Неэкземплярном) методе класса.
2.1 Общая ошибка при компиляции
При компиляции компилятор сообщает о следующей ошибке:
|
1
2
3
4
|
Error: TestArray1.java. Line 3 At 22: generic array creation public E[] array = new E[10]; ^ |
Сообщается об одном виде ошибки: создание универсального массива. Эта ошибка напрямую связана с вариантом использования универсальных массивов.
ковариации
В Java массивы являются ковариантными или используют специализацию типа общего для определенных типов, таких как Коллекция в Набор. Однако параметры универсального типа не являются ковариантными. Гетц объясняет: «Классы Коллекций используют уродливую уловку, чтобы обойти эту проблему…» [Goet 2019]
Таким образом, чтобы использовать встроенный массив с универсальными типами Java или параметр универсального типа E, массив должен иметь тип java.lang.Object, который является отличным супертипом в Java. Все это java.lang.Object, это ужасный трюк.
Массив объектов
Тем не менее, недостаток использования массива Object является обязательным условием для обобщений — привязать структуру данных или переменную к определенному типу. Структура данных типа Object может смешивать и сопоставлять любой тип, и для преобразования в исходный тип требуется приведение типа. В этом дженерики в Java не полезны — и это основная проблема.
Решение или ответ на этот вопрос прост: универсальный класс массива Java. Такой класс отсутствует в структуре коллекций Java, поэтому создайте его.
3. Java Array Class
Класс Java Array похож на другие структуры данных в структуре коллекций Java, это структура данных. Первоначально написанная реализация предназначена для простоты и не реализует никаких конкретных интерфейсов или расширений каких-либо суперклассов. Цель состоит в том, чтобы получить функциональный и полезный массив в виде класса Array.java для построения. Скелет универсального параметра типа класса Array.java:
|
1
2
3
4
5
6
7
|
class Array { Array(final int... dim); void init(final E elem); void init(final E[] elem); E get(final int...idx); void add(final E elem, final int... idx); } |
По сути, у вас есть средство для создания массива любого ранга, а затем любого размера для измерений.
Массив затем имеет метод init () для инициализации массива начальным значением по умолчанию или начального значения. Наконец, массив имеет два основных метода: один для добавления () элемента и один для получения () элемента в определенном месте массива. Базовая функциональность создания экземпляра или создания, инициализации всего массива и доступа к элементу.
3.1 Атрибуты класса массива
Класс массива Java имеет несколько атрибутов, которые определяют экземпляр класса Array.java. Атрибуты параметра универсального типа Array.java:
|
1
2
3
4
5
6
7
|
class Array { int size; int dim[]; int rank; Object data[]; E elem; } |
Атрибуты класса Array.java представляют собой данные в виде встроенного массива Object, границы массива, такие как размер, ранг, размеры. Наконец, есть элемент, элемент инициализации.
3.2 ранг и размерность с Varargs
Язык программирования Java добавил переменную номер или параметры или аргументы, именованные переменные Java-аргументы, или, более просто, varargs в выпуске Java 5.0 «Tiger» в сентябре 2004 года. Эта особенность позволяет конструктору или методу принимать различное количество параметров, и, таким образом, обобщать параметры без дублирования конструктора или метода просто для количества параметров.
Обобщение класса Array использует эту особую функцию Java: varargs или переменные аргументы для создания и доступа к элементам в классе Array.java. Это допускает любой ранг (количество измерений), а также для каждого любого числового измерения для любого неотрицательного целого числа.
Varargs также позволяет рангу быть общим, поэтому нет (по крайней мере, теоретически…) верхней границы ранга класса Array.java. Таким образом, varargs допускают общее обобщение при определении и использовании универсального класса Array.java.
Конструктор с использованием Varargs
Исходный код для конструктора Array.java иллюстрирует использование varargs для измерений для создания универсального объекта массива с использованием класса Array.java. Ранг и измерения обобщены, поэтому любой ранг массива возможен с любыми размерными границами. Исходный код для конструктора Array.java:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
|
Array(final int... dims) { this.rank = dims.length; this.dim = new int[rank]; int size = 1; //compute size of 1-dim internal array for (int x = 0; x < dims.length; x++) { size = size * dims[x]; dim[x] = dims[x]; }//end for //create internal "flat" array this.data = new Object[size]; this.size = size; }//end constructor |
Varargs — это переменные параметры, передаваемые как примитив int как массив целых чисел в переменной dims. Исходя из значения dim, вычисляются и создаются размеры для границ массива и общий внутренний «плоский» массив. Без varargs потребуется конструктор для каждого ранга для разных измерений. С конечным числом конструкторов для ранга класс универсального массива Array.java будет ограничен и не будет таким общим для varargs.
Accessor с Varargs
Доступ к элементу в общем массиве осуществляется через методы get и set. Это методы доступа или методы доступа. В отличие от методов получения и установки свойств, для универсального класса массива индекс измерения определяет элемент.
Используя varargs, это обобщает методы доступа для любого ранга или измерения для доступа к элементу. Индекс измерений проверяется на соответствие границ и ранга универсального массива для доступа.
Читатель Accessor Получить
Метод getter является средством доступа к чтению, он читает или копирует значение из массива. Исходный код для Array.java метод доступа get:
|
1
2
3
|
E get(final int... idx) { return (E) this.data[this.getIndex(idx)]; }//end get |
Набор аксессуаров для записи
Метод setter является средством доступа к записи, он записывает или копирует значение в массив. Исходный код метода метода доступа Array.java:
|
1
2
3
|
void set(final E elem, final int... idx) { this.data[this.getIndex(idx)] = elem; }//end set |
Для простоты вспомогательный метод getIndex () выполняет «тяжелую работу» по вычислению индекса одного измерения и проверке границ индекса массива.
Вспомогательные методы, чтобы помочь
Три вспомогательных метода или вспомогательные методы выполняют фактическую обработку в универсальном классе Array.java. Один метод getIndex () вычисляет один индекс из нескольких измерений индекса, а два других метода isValidDim () и isValidIndex () проверяют, что рассчитанный или заданный индекс не выходит за границы массива. Исходный код интерфейса для вспомогательных методов:
|
1
2
3
4
5
|
class Array { int getIndex(final int... idx); boolean isValidDim(final int... idx); boolean isValidIndex(final int idx); }//end class Array |
Тяжелая атлетика Получение индекса элемента
Метод getIndex () является основной функцией класса Array.java. Метод getIndex () вычисляет индекс во внутренний одномерный линейный или «плоский» массив элемента. От теории компилятора (и это намекает на теорию, но более подробное объяснение выходит за рамки объяснения), массив индексируется либо по маске строки, либо по столбцу майора для индекса. [Ахо 2007]
Для класса Array.java это несущественно, если функция согласована для заданного индекса для границ измерения экземпляра массива. Исходный код для метода getIndex ():
|
01
02
03
04
05
06
07
08
09
10
11
12
|
int getIndex(final int... idx){ isValidDims(idx); int index = 0; for(int x = 0; x < idx.length; x++) { int i = idx[x]; for(int y = x + 1; y < idx.length; y++) { i = i * dim[y]; }//end for index = index + i; }//end for return index; }//end getIndex |
Исходный код метода getIndex () проверяет размеры индекса перед тем, как фактически рассчитать одномерный индекс во внутренний линейный массив.
Валидация индекса
Есть два метода для проверки индекса. Одним из них является проверка многомерного индекса, а другим — проверка одного индекса. Исходный код для проверки одномерного индекса:
|
1
2
3
|
void isValidIndex(final int idx){ if(idx = this.size) throw new RuntimeException("Index Overflow Error!"); }//end isValidIndex |
IsValidIndex () просто проверяет, что индекс математически находится в диапазоне от нуля до общего размера внутреннего массива. Если индекс не находится в пределах диапазона, генерируется непроверенное исключение во время выполнения. Исходный код для проверки многомерного индекса:
|
1
2
3
4
5
6
|
void isValidDims(final int... idx) { if(idx.length != this.dim.length) throw new RuntimeException("Rank Error"); for(int x = 0; x = dim[x]) throw new RuntimeException(“Index Overflow Error"); if(idx[x] < 0) throw new RuntimeException(“Index Underflow Error”); }//end for }//end isValidDims |
IsValidDims () просто обходит каждый параметр измерения и проверяет, что ранг индекса совпадает с рангом параметра массива. Если ранг массива и индекса не равны, генерируется непроверенное исключение RuntimeException.
3.3 Другие неарагские методы
Другие методы не являются varargs, которые либо не принимают параметры в качестве метода доступа геттера, либо принимают один параметр. Две категории методов:
- Запрос параметров массива
- Уникальная функциональность массива
Запросить массив
Запрос параметров массива обращается к параметрам массива, как метод доступа геттера или с параметром. Массив представляет собой запросы на ранг, общий размер, верхние измерения и измерение по определенному индексу в ранге. Интерфейс для запроса методов массива класса Array.java:
|
1
2
3
4
5
6
|
class Array { int getDim(final int dim); int[] getDims(); int getRank(); int size(); }//end class Array |
Уникальная функциональность класса Array
Уникальная функциональность класса массива — это конструктор и два метода, которые предоставляют уникальную функциональность. Эти два метода предназначены для доступа и преобразования в линейный массив экземпляра класса Array. Другая функциональность — это конструктор, который позволяет копировать или реплицировать экземпляр класса Array. Функциональность для класса Array.java:
|
1
2
3
4
5
|
class Array { Array(final Array array); E getAt(final int idx); Object[] toArray(); } |
Accessor as Linear Array
Метод getAt () позволяет получить доступ к элементу массива, как если бы экземпляр класса Array представлял собой «плоский» линейный массив одного измерения. Целочисленный индекс проверяется на достоверность, а элемент возвращается в правильном месте с внутренним одномерным массивом. Исходный код для доступа в виде линейного массива:
|
1
2
3
4
|
E getAt(final int index) { this.isValidIndex(index); return (E) this.data[index]; }//end getAt |
Преобразование в массив линейных объектов
Метод toArray () преобразует экземпляр класса Array или, скорее, обращается к внутреннему одномерному массиву и возвращает его в виде массива Object. Метод toArray () возвращает поверхностную копию внутреннего линейного массива, а не глубокую копию. Исходный код средства доступа геттера для доступа к массиву линейных объектов:
|
1
2
3
|
Object[] toArray() { return this.data; }//end toArray |
Копировать конструктор
Конструктор копирования позволяет дублировать экземпляр класса Array, но в качестве «глубокой» копии существующего экземпляра класса Array. Скопированный массив и копия имеют один и тот же тип параметра, размеры, ранг и, конечно, элементы. Исходный код конструктора копирования:
|
1
2
3
4
5
6
7
8
|
Array(final Array orig) { this.rank = orig.rank; this.dim = orig.dim; this.size = orig.size; this.elem = (E) orig.elem; this.data = new Object[this.size]; System.arraycopy(orig.data, 0, this.data, 0, this.size); }//end constructor copy |
System.arraycopy () копирует оригинал и создает новый массив Object для глубокой копии. Различные параметры экземпляра класса Array копируются в глубокую копию.
4. Использование универсального класса Array
Использование универсального массива Java Array.java иллюстрируется в исходном коде двумя примерами использования:
- Алгоритм пузырьковой сортировки
- Таблица умножения
Оба примера иллюстрируют демонстрацию использования универсальных методов класса массива для создания, инициализации, доступа, запроса и реализации функциональных возможностей массива, но без использования встроенного массива Java. Исходный код иллюстрирует, и вывод от фрагмента исходного кода дается.
4.1 Bubble Sort
Сортировка по пузырькам — это простой и простой алгоритм сортировки, но он идеально подходит для иллюстрации использования универсального класса массива Array.java. Пузырьковая сортировка реализована с использованием универсального массива Java:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
|
Array list = new Array(9).init(new Integer[]{3,5,7,4,8,0,2,1,6}); System.out.println(Arrays.toString(list.toArray())); boolean swapFlag = true; while(swapFlag) { swapFlag = false; for(int x=0;x 0) { Integer temp = list.get(x); list.set( list.get(x+1), x); list.set( temp, (x+1)); swapFlag = true; }//end if }//end for }//end while System.out.println(Arrays.toString(list.toArray())); |
При запуске вывод из пузырьковой сортировки с использованием универсального массива Java:
|
1
2
3
|
[3, 5, 7, 4, 8, 0, 2, 1, 6] [0, 1, 2, 3, 4, 5, 6, 7, 8] |
4.2 Таблица умножения
Основное иллюстративное применение универсального массива Java состоит в создании простой таблицы умножения целого числа от 1 до 10. Для этого требуется двумерный массив целых чисел. После создания таблицы умножения проверяются математические свойства тождества и коммутативности. Исходный код для этого использования универсального массива Java:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
|
Array multiplyTable = new Array(10,10).init(0); for(int x=0;x<multiplyTable.getDim(0);x++){ for(int y=0;y<multiplyTable.getDim(1);y++){ multiplyTable.set(x*y, x,y); }//end for }//end for //check 1*n = n for(int x=0;x<multiplyTable.getDim(0);x++){ if(multiplyTable.get(1,x) != x) throw new RuntimeException("Identity property doesn't hold!”); if(multiplyTable.get(x,1) != x) throw new RuntimeException("Identity property doesn't hold!”); }//end for //check m*n = n*m for(int x=0;x<multiplyTable.getDim(0);x++){ for(int y=0;y<multiplyTable.getDim(1);y++){ if(multiplyTable.get(x,y) != multiplyTable.get(y,x) ) throw new RuntimeException("Commutative property doesn't hold!"); }//end for }//end for |
Нет выходных данных, потому что тождество и коммутативные математические свойства для умножения верны и, следовательно, действительны. Но это иллюстрирует использование двумерного универсального массива. Для других более высоких измерений возможны другие применения.
5. Заключение
Первоначальная проблема продемонстрировала проблему с параметризованным типом или универсальным массивом с использованием встроенного объекта массива. Используя тот же фрагмент кода, но заменяя общий массив Array.java, исходный код:
|
1
2
3
|
class TestArray2 { public Array array = new Array(10); }//end class TestArray2 |
При компиляции нет сообщений об ошибках. Структура данных Array.java позволяет решить исходную проблему.
Параметризация типов или обобщений в Java допускает безопасные с точки зрения типов классы, но при разработке системы параметризации обобщенных типов существуют компромиссы. Таким образом, дженерики в Java имеют некоторые недостатки, связанные со встроенной сущностью массива Java. К сожалению, Java Collections Framework не устраняет проблему, предоставляя структуру данных массива.
Решение находится в языке Java и параметризации универсального типа. Просто спроектируйте универсальный класс Array как первоклассный объект, написанный на Java. На первый взгляд, это избыточное дублирование существующего объекта Java — массива.
Это не репликация; Проектирование класса Java Array создает общую, безопасную для типов структуру данных, которая является полезной заменой встроенной сущности массива Java. Компромисс заключается в том, что без перегрузки операторов синтаксис менее явный в отношении доступа к массиву и операций, но он согласуется с вызовом методов для экземпляра объекта.
6. Ссылки
- [Ахо 2007] Ахо, Альфред В., Лам, Моника С., Сетхи, Рави и Уллман, Джеффри Д. Компиляторы: принципы, методы и инструменты, 2-е издание. Pearson Education, Inc., Нью-Йорк, Нью-Йорк, 2007, с. 381 — 382.
- [Goet 2019] Гетц, Брайан. «Теория и практика Java: общие черты», 25 января 2005 г.
7. Загрузите исходный код
Вы можете скачать полный исходный код этой статьи здесь: Проблема с созданием универсальных массивов