Предисловие
Благодаря этой статье вы можете понять пять методов пересечения списка, их соответствующих выступлений и реализации Foreach и итератора, а также углубить ваше понимание реализаций ArrayList и LinkedList. Давайте посмотрим вместе ниже.
1. Пять способов пройти список
1. Для каждой петли
Список <integer> list = new ArrayList <Integer> (); для (Integer J: List) {// Использование j}2. Итератор коллекции вызовов вызовов
Список <integer> list = new ArrayList <Integer> (); for (iterator <Integer> iterator = list.iterator (); iterator.hasnext ();) {iterator.next ();}или
Список <integer> list = new ArrayList <Integer> (); итератор <Integer> iterator = list.iterator (); while (iterator.hasnext ()) {iterator.next ();}3. Польшеменный цикл подростка, условие завершения состоит в том, чтобы сравнивать и судить каждый раз, когда вызывается функция Size ()
Список <integer> list = new ArrayList <Integer> (); for (int j = 0; j <list.size (); j ++) {list.get (j);}4. Покрементный цикл подростка, сравнения и суждения о временных переменных, условия прекращения которых равны размеру ()
Список <integer> list = new ArrayList <Integer> (); int size = list.size (); for (int j = 0; j <size; j ++) {list.get (j);}5. Цикл уменьшения индекса
Список <integer> list = new ArrayList <Integer> (); for (int j = list.size ()-1; j> = 0; j--) {list.get (j);}Проверка производительности и сравнение пяти методов обхода списка
Ниже приведен код тестирования производительности, который выводит время, затрачиваемое на различные методы обхода ArrayList и LinkedList по разным порядкам.
пакет cn.trinea.java.test; import java.text.decimalformat; импорт java.util.arraylist; import java.util.calendar; импорт java.util.iterator; импорт java.util.linkedlist; импорт java.util.list;/** * Javalooptest * @authorlist; 2013-10-28 */public class javalooptest {public static void main (string [] args) {System.out.print ("Сравните производительность цикла ArrayList"); LooplistCompare (getarraylists (10000, 100000, 100000, 9000000)); System.out.print ("/r/n/r/ncompare LooplistCompare (GetLinkedLists (100, 1000, 10000, 10000)); } public Static List <integer> [] getarraylists (int ... sizearray) {list <Integer> [] listarray = new Arraylist [sizearray.length]; for (int i = 0; i <listarray.length; i ++) {int size = sizearray [i]; Список <integer> list = new ArrayList <Integer> (); for (int j = 0; j <size; j ++) {list.add (j); } listArray [i] = list; } return ListArray; } public Static List <integer> [] getLinkedLists (int ... sizearray) {list <Integer> [] listarray = new LinkedList [sizearray.length]; for (int i = 0; i <listarray.length; i ++) {int size = sizearray [i]; Список <integer> list = new LinkedList <Integer> (); for (int j = 0; j <size; j ++) {list.add (j); } listArray [i] = list; } return ListArray; } public static void looplistcompare (list <Integer> ... listarray) {printheader (listarray); Long Starttime, EndTime; // Тип 1 для (int i = 0; i <listarray.length; i ++) {list <Integer> list = listarray [i]; startTime = calendar.getInstance (). getTimeInmillis (); for (integer j: list) {// Использовать j} endtime = calendar.getInstance (). getTimeInmillis (); printcosttime (i, listarray.length, "для каждого", EndTime - StartTime); } // Тип 2 для (int i = 0; i <listarray.length; i ++) {list <Integer> list = listarray [i]; startTime = calendar.getInstance (). getTimeInmillis (); // iterator <Integer> iterator = list.iterator (); // while (iterator.hasnext ()) {// iterator.next (); //} for (iterator <Integer> iterator = list.iterator (); iterator.hasnext ();) {iterator.next (); } endtime = calendar.getInstance (). getTimeInmillis (); printcosttime (i, listarray.length, «для итератора», EndTime - StartTime); } // Тип 3 для (int i = 0; i <listarray.length; i ++) {list <Integer> list = listarray [i]; startTime = calendar.getInstance (). getTimeInmillis (); for (int j = 0; j <list.size (); j ++) {list.get (j); } endtime = calendar.getInstance (). getTimeInmillis (); printcosttime (i, listarray.length "для list.size ()", endtime - starttime); } // Тип 4 для (int i = 0; i <listarray.length; i ++) {list <Integer> list = listarray [i]; startTime = calendar.getInstance (). getTimeInmillis (); int size = list.size (); for (int j = 0; j <size; j ++) {list.get (j); } endtime = calendar.getInstance (). getTimeInmillis (); printcosttime (i, listarray.length, "for size = list.size ()", endtime - starttime); } // Тип 5 для (int i = 0; i <listarray.length; i ++) {list <Integer> list = listarray [i]; startTime = calendar.getInstance (). getTimeInmillis (); for (int j = list.size ()-1; j> = 0; j--) {list.get (j); } endtime = calendar.getInstance (). getTimeInmillis (); printcosttime (i, listarray.length, "для j--", endtime-starttime); }} static int first_column_length = 23, other_column_length = 12, total_column_length = 71; static final decimalformat comma_format = new DecimalFormat ("#, ###"); public static void printheader (список <Integer> ... Listarray) {printrowdivider (); for (int i = 0; i <listarray.length; i ++) {if (i == 0) {stringBuilder sb = new StringBuilder (). Append ("size size"); while (sb.length () <first_column_length) {sb.append (");} system.out.print (sb);} stringbuilder sb = new Stringbuilder (). Append (" | ") .append (comma_format.format (listarray [i] .size ()); SB.Append (""); (sb.length () <total_column_length) {sb.append ("-"); <First_column_length) {sb.append (""); System.out.print (sb); }}} PS: если run сообщит о исключении in thread “main” java.lang.OutOfMemoryError: Java heap space , пожалуйста, уменьшите размер list size в main функции.
Функция getArrayLists вернет ArrayList с разными size , а функция getLinkedLists вернет LinkedList с разными size .
Функция loopListCompare будет использовать приведенный выше метод обхода 1-5, чтобы пройти список в каждом массиве списков (включая списки разных размеров).
Функция, начинающаяся с print является функцией вывода.
Тестовая среда -32 -битная система Windows 7 32 -битная система 3,2 г памяти 4G, Java 7, Eclipse -xms512m -xmx512m
Окончательные результаты теста следующие:
Сравните производительность цикла ArrayList --------------------------------------------------------------------------- Размер списка | 10000 | 100 000 | 1 000 000 | 10 000 000 ------------------------------------------------------------------- Для каждого | 1 мс | 3 мс | 14 мс | 152 мс ----------------------------------------------------------------------- Для итератора | 0 мс | 1 мс | 12 мс | 114 мс ------------------------------------------------------------------- для list.size () | 1 мс | 1 мс | 13 мс | 128 мс ------------------------------------------------------------------- для размера = list.size () | 0 мс | 0 мс | 6 мс | 62 мс ----------------------------------------------------------------------- Для j-- | 0 мс | 1 мс | 6 мс | 63 мс ----------------------------------------------------------------------- Сравнить 100 | 1000 | 10000 | 100 000 ------------------------------------------------------------------- Для каждого | 0 мс | 1 мс | 1 мс | 2 мс ------------------------------------------------------------------- Для итератора | 0 мс | 0 мс | 0 мс | 2 мс ----------------------------------------------------------------------- Для List.Size () | 0 мс | 1 мс | 73 мс | 7972 мс ----------------------------------------------------------------------- для размера = list.size () | 0 мс | 0 мс | 67 мс | 8216 мс ----------------------------------------------------------------------- Для J-- | 0 мс | 1 мс | 67 мс | 8277 ms ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Первая таблица является результатом сравнения ArrayList, а вторая таблица является результатом сравнения LinkedList.
Горизонтальное направление таблицы - это потребление времени прохождения различных размеров списков в одном и том же методе обхода, а вертикальное направление - это потребление времени прохождения различных методов обхода одного и того же списка.
PS: Поскольку первое обход списка займет немного больше времени, результаты for each немного отклоняются. Если вы поменяете несколько типов в тестовом коде, вы обнаружите, что for each времени близко к for iterator .
Анализ результатов тестирования производительности метода обхода
1. Фореш Введение
Foreach - это очень мощная структура петли, представленная Java SE5.0. for (Integer j : list) следует прочитать for each int in list .
for (Integer j : list) реализация почти эквивалентна
Итератор <Integer> iterator = list.iterator (); while (iterator.hasnext ()) {integer j = iterator.next ();}Код FOREACH прост в написании, и нет необходимости заботиться о начальном значении, о прекращении значения и трансграничного, поэтому нелегко делать ошибки.
2. Анализ результатов метода обхода ArrayList
а До того, как размер ArrayList составил 100 000 человек, потребление времени пяти методов обхода было почти таким же
беременный После 100 000 методов четвертого и пятого обхода быстрее, чем первые три, метод GET лучше, чем метод итератора, и
int size = list.size (); for (int j = 0; j <size; j ++) {list.get (j);} Замена list.size() с временным размером переменной - это лучшая производительность. Давайте посмотрим на реализацию Iterator и get методы в ArrayList
Частный класс ITR реализует итератор <e> {int cursor; // индекс следующего элемента для возврата int lastret = -1; // Индекс последнего элемента возвращался; -1, если нет такого такого int weardmodcount = modcount; public boolean hasnext () {return cursor! = size; } @Suppresswarnings ("unchecked") public e next () {checkforComodification (); int i = курсор; if (i> = size) бросить новый noshelementexception (); Object [] elementData = ArrayList.This.ElementData; if (i> = elementdata.length) бросить новый concurrentmodificationexception (); курсор = i + 1; вернуть (e) elementData [lastret = i]; }…} Public e Get (int index) {rangecheck (index); return elementdata (index);} Из этого мы видим, что next функции get и Iterator также получают элементы путем непосредственного позиционирования данных, но есть только несколько суждений.
в Из вышесказанного мы видим, что даже в межсчетах десятков миллионов разница между несколькими методами обхода составляет всего около 50 мс, а время почти равное около 100 000. Учитывая преимущества Foreach, мы можем использовать простой метод Foreach Foreach для прохождения.
3. Анализ результатов метода обхода LinkedList
а Когда размер LinkedList составляет около 10 000, метод get и метод Iterator уже примерно на два порядка разных. Когда 100 000 человек, производительность метода Iterator намного лучше, чем метод получить.
Давайте посмотрим на реализацию итераторов и get методы в LinkedList
Лист частного класса реализует ListIterator <e> {private node <e> lastreturned = null; Частный узел <e> Далее; частный int nextIndex; private int weddcount = modcount; SistiTR (int index) {// Assert ispositionIndex (index); Next = (index == размер)? null: узел (индекс); NextIndex = index; } public boolean hasNext () {return nextIndex <size; } public e next () {checkforComodification (); if (! hasnext ()) бросить новый noshelementexception (); Lastreturned = Далее; Next = Next.Next; NextIndex ++; return lastreturned.item; }…} Public e get (int index) {checkElementex (index); return node (index) .item;} /*** Возвращает (не нулевой) узел в указанном индексе элементов. */Node <e> node (int index) {// утверждать iselementIndex (index); if (index <(size >> 1)) {node <e> x = first; для (int i = 0; i <index; i ++) x = x.next; возврат x; } else {node <e> x = last; для (int i = size-1; i> index; i--) x = x.prev; возврат x; }} Из приведенного выше кода мы видим, что next функция итератора LinkedList просто быстро получает следующий элемент через следующий указатель и возвращает. Метод GET будет проходить с самого начала до индексного индекса и найти элемент со сложностью времени o (n), а временная сложность обхода достигнет O (N2).
Поэтому рекомендуется использовать Foreach для прохождения LinkedList, чтобы избежать использования get .
4. Сравнительный анализ результатов MarrayList и методов обхода LinkedList
Из вышеуказанного порядка, это также прохождение петли Foreach, а время ArrayList и LinkedList аналогична. Если вы слегка измените этот пример и увеличите list size вы обнаружите, что эти два в основном находятся на том же порядке.
Тем не менее, временная сложность функции ArrayList get составляет O (1), в то время как временная сложность функции LinkedList GET составляет O (n).
Если вы рассмотрите потребление пространства, рекомендуется сначала выбрать ArrayList. Для индивидуальной вставки и удаления вы можете использовать LinkedList.
Заключение резюме
Через приведенный выше анализ мы можем в основном суммировать:
Суммировать
Вышеуказанное - все содержание этой статьи. Я надеюсь, что содержание этой статьи будет полезно для всех при обучении или использовании Java. Если у вас есть какие -либо вопросы, вы можете оставить сообщение для общения.