Эффективный цикл через список Java

Ответ 1

Этот список немного устарел и сегодня не должен быть действительно полезным.

Это была хорошая рекомендация несколько лет назад, когда устройства Android были медленными и имели очень ограниченные ресурсы. Внедрение Dalvik VM также не имело большого количества оптимизаций, доступных сегодня.

На таких устройствах простая сборка мусора легко принимала 1 или 2 секунды (для сравнения это занимает около 20 мс на большинстве устройств сегодня). Во время GC устройство просто зависало, поэтому разработчикам приходилось очень осторожно относиться к потреблению памяти.

Вам не стоит слишком беспокоиться об этом сегодня, но если вы действительно заботитесь о производительности, вот некоторые подробности:

(1) for (int i = initializer; i >= 0; i--) //hard to loop backwards
(2) int limit = calculate_limit(); for (int i=0; i < limit; i++)
(3) Type[] array = get_array(); for (Type obj : array)

Эти легко понять. i >= 0 быстрее оценивать, чем i < limit, потому что он не считывает значение переменной перед выполнением сравнения. Он работает непосредственно с целым литералом, который выполняется быстрее.

Я не знаю, почему (3) должно быть медленнее, чем (2). Компилятор должен создать тот же цикл, что и (2), но, возможно, Dalvik VM в это время не оптимизировал его правильно.

(4) for (int i=0; i < array.length; i++) //gets array.length everytime
(5) for (int i=0; i < this.var; i++) //has to calculate what this.var is
(6) for (int i=0; i < obj.size(); i++) //even worse calls function  each time

Эти комментарии уже объясняются в комментариях.

(7) Iterable list = get_list(); for (Type obj : list)

Iterables медленны, потому что они выделяют память, выполняют некоторую обработку ошибок, вызывают несколько методов внутри,... Все это намного медленнее, чем (6), которое выполняет только один вызов функции на каждой итерации.

Ответ 2

Я чувствовал, что мой первый ответ был неудовлетворительным и действительно не помог объяснить вопрос; Я разместил ссылку на этот сайт и немного уточнил, в котором были рассмотрены некоторые основные варианты использования, но не проблема, связанная с проблемой. Итак, я пошел вперед и сделал небольшое практическое исследование.

Я выполнил два отдельных кода:

    // Code 1
    int i = 0;
    Integer[] array = { 1, 2, 3, 4, 5 };
    for (Integer obj : array) {
        i += obj;
    }
    System.out.println(i);

    // Code 2
    int i = 0;
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    for (Integer obj : list) {
        i += obj;
    }
    System.out.println(i);

Конечно, оба печатают 15, и оба используют массив Integer (no int s).

Затем я использовал javap, чтобы разобрать их и посмотреть на байт-код. (Я проигнорировал инициализацию, все до того, как цикл for закомментирован.) Поскольку они довольно длинные, я разместил их в PasteBin здесь.

Теперь, когда байт-код для кода 1 на самом деле длиннее, он менее интенсивен. Он использует invokevirtual только один раз (кроме println), и никакие другие вызовы не нужны. В коде 1, похоже, оптимизируется итерация на базовый цикл; проверяя длину массива и загружая в нашу переменную, затем добавляя к i. Это, по-видимому, оптимизировано так, чтобы вести себя как for (int i = 0; i < array.length; i++) { ... }.

Теперь, в коде 2, байт-код становится намного более интенсивным. Он должен сделать 2 invokeinterface вызовов (оба в Iterator) в дополнение ко всем другим вызовам, которые необходимы выше. Кроме того, код 2 должен вызывать checkcast, потому что это общий Iterator (который не оптимизирован, как я уже упоминал выше). Теперь, несмотря на то, что существует меньше вызовов операций load и store, эти вышеупомянутые вызовы требуют значительных дополнительных накладных расходов.

Как он говорит в видеоролике, если вам нужно много чего делать, вы можете столкнуться с проблемами. Например, запуск одного из них в начале Activity, вероятно, не слишком большой. Просто будьте осторожны с созданием многих из них, особенно, например, в onDraw.

Ответ 3

Я предполагаю, что компилятор оптимизирует (3) к этому (это та часть, где я предполагаю):

for (int i =0; i < array.length; ++i)
{
    Type obj = array[i];

}

И (7) невозможно оптимизировать, поскольку компилятор не знает, что это за Итерабель. Это означает, что на самом деле нужно создать new Iterator в куче. Выделение памяти дорого. И каждый раз, когда вы запрашиваете следующий объект, он проходит через некоторые вызовы.

Чтобы дать приблизительный эскиз того, что происходит, когда (7) скомпилируется (обязательно об этом):

Iterable<Type> iterable = get_iterable();
Iterator<Type> it = iterable.iterator(); // new object on the heap
while (it.hasNext()) // method call, some pushing and popping to the stack
{
    Type obj = it.next(); // method call, again pushing and popping


}

Ответ 4

Я предполагаю, что вы должны маршировать объекты в Iterator с "связанным списком", а затем поддерживать API, а не кусок памяти и указатель (массив)

Ответ 5

Третий вариант быстрее, чем 7, потому что массив - тип reified, а JVM должен просто назначить указатель на правильное значение. Но когда вы перебираете коллекцию, компилятор может выполнять дополнительные отбрасывания из-за стирания. На самом деле компилятор вставляет это приведение в общий код, чтобы как можно скорее определить некоторые грязные хаки, такие как использование устаревших типов raw.

P.S. Это просто предположение. На самом деле, я думаю, что компилятор и компилятор JIT могут выполнять любую оптимизацию (JIT даже во время выполнения), и результат может зависеть от конкретных деталей, таких как версия JVM и поставщик.

Ответ 6

В случае Android это видео от Google Developers в 2015 году.

Чтобы индексировать или начинать? (Android Performance Patterns Season 2 ep6) https://www.youtube.com/watch?v=MZOf3pOAM6A

Они выполнили тест во время выполнения DALVIK, 4.4.4 build, 10 раз, чтобы получить средние результаты. Результат показывает, что "For index" является лучшим.

int size = list.size();
for (int index = 0; index < size; index++) {
    Object object = list.get(index);
    ...
}