Обзор
На языке Java предоставляется структура сбора данных, которая определяет некоторые абстрактные типы данных, такие как список и набор. Каждый абстрактный тип данных имеет свою конкретную реализацию, а базовый уровень принимает различные методы реализации, такие как ArrayList и LinkedList.
Кроме того, Java также предоставляет несколько различных способов прохождения наборов данных. Разработчики должны четко понимать характеристики, применимые случаи и производительность в различных базовых реализациях. Давайте подробно проанализируем этот контент ниже.
Как элементы данных хранятся в памяти?
Есть два основных метода хранения для элементов данных в памяти:
1. Последовательное хранилище, случайный доступ (прямой доступ):
Таким образом, смежные элементы данных хранятся в соседних адресах памяти, а весь адрес памяти непрерывный. Адрес памяти может быть непосредственно рассчитан на основе местоположения элемента и считать его напрямую. Средняя временная сложность чтения элемента в определенном месте составляет O (1). Обычно, только устанавливает реализацию на основе массивов, имеет эту функцию. ArrayList представлен на Java.
2. цепочка хранения, последовательный доступ:
Таким образом, каждый элемент данных не должен находиться в соседней позиции в памяти, и каждый элемент данных содержит адрес памяти его следующего элемента. Адрес памяти не может быть рассчитан непосредственно на основе местоположения элемента, и элементы могут быть прочитаны только по порядку. Средняя временная сложность чтения элемента в определенном месте составляет O (n). Это в основном представлено связанными списками.
LinkedList представлен на Java.
Какие методы обхода предоставляются на Java?
1. Традиционный для прохождения петли, основанный на счетчике:
Сам обход сохраняет счетчик вне коллекции, а затем читает элементы в каждой позиции в последовательности и останавливается, когда читается последний элемент. Главное - читать элемент в соответствии с его позицией. Это также самый примитивный метод обезвреживания.
Метод написания:
for (int i = 0; i <list.size (); i ++) {list.get (i);}2. Итераторный обход, итератор:
Итератор был первоначально шаблоном проектирования OO, с его основной целью было блокировать характеристики различных наборов данных и равномерно пройти интерфейсы коллекции. Как язык OO, Java естественно поддерживает режим итератора в коллекциях.
Метод написания:
Iterator iterator = list.iterator (); while (iterator.hasnext ()) {iterator.next ();}3. Foreach Loop Traversal:
Итератор и счетчики, которые явно объявлены, заблокированы.
Преимущества: код кратко и не подвержен ошибкам.
Недостатки: могут быть сделаны только простые обходы, а коллекции данных не могут быть эксплуатированы (удалить, заменить) в течение процесса обхода.
Метод написания:
for (elementtype element: list) {}Каков принцип реализации каждого метода обхода?
1. Традиционный для прохождения петли, основанный на счетчике:
Сам обход сохраняет счетчик вне коллекции, а затем читает элементы в каждой позиции в последовательности и останавливается, когда читается последний элемент. Главное - читать элемент в соответствии с его позицией.
2. Итераторный обход, итератор:
Каждый конкретный набор данных реализации обычно должен предоставить соответствующий итератор. По сравнению с традиционными для петель, итератор запрещает явные счетчики обхода. Следовательно, итератор на основе последовательного хранения коллекций может напрямую получить доступ к данным по местоположению. Итератор на основе цепных наборов хранилища, нормальные реализации требуют сохранения текущего места прохождения. Затем переместите указатель вперед или назад в соответствии с текущей позицией.
3. Foreach Loop Traversal:
Согласно декомпилированному байткоду, можно обнаружить, что Foreach также использует метод итератора для его реализации, но компилятор Java помог нам генерировать эти коды.
Как каждый метод обхода работает для разных методов хранения?
1. Традиционный для прохождения петли, основанный на счетчике:
Потому что он основан на положении элемента, читается по позиции. Таким образом, мы можем знать, что для последовательного хранения, поскольку средняя сложность временных элементов считывания в определенном месте составляет O (1), средняя временная сложность прохождения всего набора - O (n). Для цепного хранения, поскольку средняя временная сложность элементов считывания в определенном месте составляет O (n), средняя временная сложность прохождения всего набора составляет O (N2) (квадрат n).
Код ArrayList Читает по позиции: ПРОЧИТАТЬ ПРЕДОЧЕТ по позиции элемента.
Transient Object [] elementData; public e get (int index) {rangecheck (index); return elementdata (index);} e elementdata (int index) {return (e) elementdata [index];}Код LinkedList Читая по позиции: каждый раз, когда вам нужно читать назад из 0 -го элемента. Фактически, это также сделало небольшие оптимизации внутри.
Transient int size = 0; переходной узел <e> First; Transient Node <e> последний; public e get (int index) {checkElementex (index); return node (index) .Item;} узел <e> node (int index) {if (index <(size >>) {// Query Position находится в первой половине ссылки, и смотрит на node node) {// Query -Position; i = 0; i <index;2. Итераторный обход, итератор:
Затем, для коллекций типа случайного, нет большого значения. Вместо этого некоторые дополнительные операции добавят дополнительное время выполнения. Тем не менее, он имеет большое значение для сбора последовательного доступа, поскольку итератор сохраняет текущую позицию обхода, поэтому каждый раз, когда вы проходите, вам не нужно начинать искать из первого элемента коллекции. Просто переместите указатель один за другим. Таким образом, временная сложность прохождения всего набора уменьшается до O (n);
(Это используется только в качестве примера LinkedList) Итератор LinkedList реализован внутри, который должен поддерживать текущую позицию обхода, а затем управлять указателем для перемещения:
Код:
public e Next () {checkforComodification (); if (! hasNext ())) бросить новый noshelementexception (); lastreturned = next; next = next.next; nextIndex ++; return lastreturned.item;} public e предыдущий () {checkformodification (); if (! hasprevious ()). == NULL)? Последнее: next.prev; nextIndex-; return lastreturned.item;}3. Foreach Loop Traversal:
Анализируя Java Bytecode, мы видим, что внутренний принцип реализации Foreach также реализуется через итератор, но этот итератор генерируется компилятором Java для нас, поэтому нам не нужно писать его вручную. Однако, поскольку проверки конверсии типа требуются каждый раз, она занимает немного больше времени, чем итератор. Сложность времени такая же, как и у итератора.
Bytecode с использованием итератора:
Код: новый # // класс java/util/arraylistdupinvokespecial # // method java/util/arraylist. "<init>" :() vastore_aload_invokeinterface #, // interfacemethod java/util/list.iterator :() ljava/util/iterator; Interfacemethod java/util/iterator.next :() ljava/lang/object; popaload_invokeinterface #, // interfacemethod java/util/iterator.hasnext :() Zifne return
Используйте байт -код Foreach:
Код: новый # // класс java/util/arraylistdupinvokespecial # // method java/util/arraylist. "<init>" :() vastore_aload_invokeinterface #, // interfacemethod java/util/list.iterator :() ljava/util/iterator; Interfacemethod java/util/iterator.next :() ljava/lang/object; castcast # // class loop/modelastore_aload_invokeinterface #, // interfacemethod java/util/iterator.hasnext :() Zifne return
В каких случаях применяется каждый метод обхода?
1. Традиционный для прохождения петли, основанный на счетчике:
Последовательное хранилище: высокая производительность чтения. Подходит для сборов последовательных последовательных хранений.
Хранение цепи: Сложность времени слишком высока и не подходит для прохождения коллекций цепного хранения.
2. Итераторный обход, итератор:
Последовательное хранилище: если вы не заботитесь о времени, рекомендуется выбрать этот метод. В конце концов, код более краткий, а также предотвращает проблему вне одного.
Хранение цепи: это имеет большое значение. Средняя временная сложность снижается до O (n), что является довольно привлекательным, поэтому рекомендуется этот метод обхода.
3. Foreach Loop Traversal:
Foreach делает только код более кратким, но у него есть некоторые недостатки, то есть он не может управлять коллекциями данных (делеция и т. Д.) В течение процесса обхода, поэтому он не используется в некоторых случаях. Более того, он реализован на основе итератора, но из -за проблемы преобразования типа он будет немного медленнее, чем напрямую использование итератора. К счастью, временная сложность такая же. Итак, как выбрать, обратитесь к двум вышеуказанным методам, чтобы сделать компромиссный выбор.
Каковы лучшие практики для Java?
В структуре сбора данных Java предоставляется интерфейс случайного интерфейса, который не имеет методов, просто тег. Обычно он используется в реализации интерфейса списка, чтобы отметить, поддерживает ли реализация списка случайный доступ.
Набор данных реализует этот интерфейс, что означает, что он поддерживает случайный доступ, а средняя сложности считывания элементов по местоположению - O (1). Например, ArrayList.
Если этот интерфейс не реализован, это означает, что случайный доступ не поддерживается. Например, LinkedList.
Таким образом, кажется, что разработчики JDK также заметили эту проблему. Рекомендуемый способ состоит в том, чтобы сначала определить, поддерживается ли случайный доступ, то есть список экземпляров случайного анализа.
например:
if (Список экземпляра RandomAccess) {// Использовать традиционную для обхода цикла. } else {// Использовать итератор или FOREACH. }Выше приведено анализ метода сбора Java Traversal (принцип реализации, производительность алгоритма и применимые случаи), введенный редактором. Я надеюсь, что это будет полезно для всех!