Java, перебор ArrayList

Нужен был функционал похожий на std::vector в java, использовал это ArrayList<MyClass> bact = new ArrayList<MyClass>();

Верно.

вопрос встал о том как его перебирать

Если нужен индекс, то

for (int i = 0; i < bact.size(); ++i) { MyClass b = bact.get(i); ... }

если не нужен индекс, то

for (MyClass b : bact) { ... }

если я правильно понял, то прямого доступа здесь нет, и доступ к N-ому элементу будет O(N)

Неправильно. В ArrayList доступ к N-ому элементу это O(1).

Неправильно. В ArrayList доступ к N-ому элементу это O(1).

Странно, где-то читал что в нем могут хранится элементы любого типа... Ну ладно. Индекс не нужен, по поводу сайта http://howtodoinjava.com/2013/03/26/performance-comparison-of-different-for-l...

Там сказано что это не самый быстрый способ...

Странно, где-то читал что в нем могут хранится элементы любого типа... Ну ладно. Индекс не нужен, по поводу сайта http://howtodoinjava.com/2013/03/26/performance-comparison-of-different-for-l...

А попробуй запустить пример из сравнения, только поменять местами алгоритмы. Что-то мне подсказывает, что первый способ занял больше всего времени из-за того, что в последующих java могла использовать кэш.

Если порядок перебора неважен, то лучше использовать HashSet.

Там и О(1) и любого типа.

60 раз в секунду — это 60 FPS. Игру пишешь, в главном цикле перебираешь.

В таком случае лучше всего

for(int i = 0; i < list.size(); i++) {list.get(i);}

Понятнее, чем обход в обратном направлении, скорость такая же. Может, на какие-то копейки и отличается, ну и фиг с ним.

А вот с итератором единственная проблема, что он каждый раз создает новый объект. Он, конечно, весит немного, но тут лучше совсем не мусорить.

Список уже давным-давно означает не «односвязанный список», в котором по индексу искать медленно, а «абстрактная коллекция», просто штуковина с парой методов. И ArrayList внутрях на самом деле не список, а массив, так что индексация мгновенная.

В Map-е от итератора точно не избавиться, здравстуй, мусор, Новый год. Ему же не конкретный элемент искать, а все перебирать надо, у каждого вызвать что-то вроде act() или там draw().

Ок, спасибо. Ещё один вопрос, что лучше

 
for(int i = 0; i < list.size(); i++) {
list.get(i).doSomething1();
list.get(i).doSomething2();
...
list.get(i).doSomething99();
}

 
for(int i = 0; i < list.size(); i++) {
Bact list.get(i);
Bact.doSomething1();
Bact.doSomething2();
...
Bact.doSomething99();
}

Ещё один вопрос, что лучше

А сам как думаешь?

Однофигственно. Не стоит такими мелочами заморачиваться.

Ясно дело, что один раз сохранить ссылку быстрее, чем каждый раз доставать из списка, но это и само по себе быстро, и оптимизатор может закешировать в свое удовольствие.

Единственное, я бы все эти doSomethingxx завернул в одну общую функцию, которая внтури все и вызывает. И понятнее, и вопрос «что быстрее» не возникает.

Bact bact = list.get(i);
bact.doEverything();
// ну или doEverything(bact), если это не метод того класса

А сам как думаешь?

Я же только начал учить джаву, с одной стороны, каким-бы быстрым доступ не был к элементу массива, он тут будет медленнее чем к объекту. С другой стороны на создание объекта нужна память, и наверное процессорное время. Так что ХЗ.

я бы все эти doSomethingxx завернул в одну общую функцию

Там немного труднее.

for(int i = 0; i < list.size(); i++) {
Bact.doSomething1();
if(ФазаЛуны){
Bact.doSomething2();
}
...
if(СвященныйБогРандома){
Bact.doSomething99();
}
}

private void act(){
    for(int i = 0; i < list.size(); i++) {
        processBact(list.get(i));
    }
}

private void processBact(Bact bact) {
    Bact.doSomething1();
    if(ФазаЛуны){
        Bact.doSomething2();
    }
//...
    if(СвященныйБогРандома){
        Bact.doSomething99();    
    }

}

И функция act() попроще (мало ли, что там еще добавить надо), и лишних отступов для цикла не надо. Выгода!

Хм... а где я должен писать функцию act ?

А вот тут какие-то непонятки.

arrayList.get(i); каждый раз отдает одну и ту же ссылку на объект. Он ничего и никогда не создает. И когда пишешь

Bact bact = list.get(i);,

то тоже ничего не создается. Заводится одна-единственная ссылка, никакой нагрузки это вообще не добавляет.

Так что никаких ХЗ тут нет, в одном случае эту ссылку сохранили, во втором — каждый раз просим вернуть ее же. Другое дело, что эта операция недорогая, так что разницу вряд ли увидишь. Но чисто эстетически я бы ссылку сохранил.

class Scene {
    private ArrayList<Bact> bacts = new ArrayList<Bact>();

    // всякие инициализации и заполнения

    public void init(List<Bact> bacts) this.bacts.addAll(bacts);}


    // а его дергаем 60 раз в секунду
    public void act() {
    // тут итерируем
    }

    private void processBact(Bact bact) {
    // тут обрабатываем отдельный элемент
    }

}

Ну и в самом начале программы создаем этот Scene, init() его нужными объектами, и каждый раз вместо написания цикла дергаем act().

Странно, где-то читал что в нем могут хранится элементы любого типа...

Да.

http://howtodoinjava.com/2013/03/26/performance-comparison-of-different-for-l...

Там написан бред, который не имеет смысла для 99% программ.

то тоже ничего не создается.

Как это? Даже если bact будет указателем, нам нужно создать этот указатель. Я понимаю что это гораздо быстрее чем Bact bact = new Bact(); но все-же время тратиться, и те 4 или больше байта на хранение дополнительного указателя тоже.

Это, опять же, никому не интересная мелочь. Ссылка создается на стеке. Затребовать там место, считай, мгновенно. Память освободится автоматом при выходе из функции. Все это не несет абсолютно никакой нагрузки. Не надо об этом думать.

Ну да, я понял что это не существенно. Отмечу тему решенной.

Делая Bact bact = list.get(i), ты не создаешь объект, а получаешь его по ссылке из списка.

Но тем самым создаю указатель. Операция очень быстрая. Получение по get как я понял тоже быстрое. В любом случае, это не существенно.

Ой, то есть ссылку.. я недавно на Java после С++

Но тем самым создаю указатель. Операция очень быстрая. Получение по get как я понял тоже быстрое. В любом случае, это не существенно.

еще имей в виду, что жабский рантайм достаточно мозговит для того, чтобы в конце концов все эти варианты свести к чему-то одному более-менее оптимальному.

А пример можно, что рантайм может здесь сделать?

Коллекция-то может оказаться мутабельной, и list.get(i) может возвращать разные ссылки. Да, потом уже выкинется ConcurrentModificationException, но это только потом, рантайм об этом знать не может.

Коллекция-то может оказаться мутабельной

а может и не оказаться. Ну и ConcurrentModificationException при обращении по индексу вываливаться далеко не обязано.

Так речь об оптимизаторе. Он же работает по принципу «не навреди», и вряд ли будет здесь что-то менять. Про exception — точно так, кидаться не будет, сработает только для итератора.

for (final Bact i : list) {
}

Чем меньше мутабельных переменных, тем лучше. Если в языке есть foreach, и при этом для перебора используется мутабельная переменная, то я, например, сразу начинаю искать места в теле цикла, где ее изменяют.

Получение по get как я понял тоже быстрое

Если геттер только возвращает значение из поля - быстрая. Но мало ли какой ерунды может заползти потом в геттер, я предпочитаю не рисковать.

В джабе SomeObject примерно тоже самое, что SomeObject* в крестах.

Не относится к необъектам (int, float ...)

Если геттер только возвращает значение из поля - быстрая. Но мало ли какой ерунды может заползти потом в геттер, я предпочитаю не рисковать.

Я же не про свой геттер говорю, а про извлечение элемента из массива.

Упс, почему то (видимо пора отдыхать) этот пост распарсил как

Bact bact = list.get(i);
bact.getSomething().doSomething1();
bact.getSomething().doSomething2();
...

Хотя совет всё равно не теряет актуальности, только аллах знает что будет в вашей имплементации списка, хотспот конечно штука умная, но он не всесилен.

имплементации , хотспот.

Я только начал учить java. Но я решил все таки делать Bact b = bact.get(i); Так размер кода получается меньше.

хотспот

Оптимизатор, но я лажанул

пишется под Android

в далвике нет хотспота.