LINUX.ORG.RU

Java, перебор ArrayList

 , ,


1

1

Нужен был функционал похожий на std::vector в java, использовал это ArrayList<MyClass> bact = new ArrayList<MyClass>(); вопрос встал о том как его перебирать, если я правильно понял, то прямого доступа здесь нет, и доступ к N-ому элементу будет O(N). Подумал что нужно использовать итераторы, погуглив нашел сравнение скоростей роботы. И вот это наиболее быстро

private static List<Integer> list = new ArrayList<>();
for(int j = list.size(); j > size ; j--)
{
    //do stuff
}

Я запутался... каким способом быстро перебрать все элементы? (порядка 20*300 элементов, 60 раз/секунда , вроде и сейчас все быстро работает, но зачем зря нагружать телефон(пишется под Android))

★★★

Нужен был функционал похожий на 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).

Legioner ★★★★★
()
Ответ на: комментарий от Legioner

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

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

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

abs ★★★
() автор топика
Ответ на: комментарий от abs

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

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

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

Deleted
()

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

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

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

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

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

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

anonymous
()
Ответ на: комментарий от Deleted

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

anonymous
()
Ответ на: комментарий от anonymous

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

 
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();
}

abs ★★★
() автор топика
Ответ на: комментарий от abs

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

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

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

Bact bact = list.get(i);
bact.doEverything();
// ну или doEverything(bact), если это не метод того класса
anonymous
()
Ответ на: комментарий от grouzen

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

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

abs ★★★
() автор топика
Ответ на: комментарий от anonymous

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

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

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

abs ★★★
() автор топика
Ответ на: комментарий от abs
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() попроще (мало ли, что там еще добавить надо), и лишних отступов для цикла не надо. Выгода!

anonymous
()
Ответ на: комментарий от abs

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

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

Bact bact = list.get(i);,

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

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

anonymous
()
Ответ на: комментарий от abs
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().

anonymous
()
Ответ на: комментарий от anonymous

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

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

abs ★★★
() автор топика
Ответ на: комментарий от abs

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

anonymous
()
Ответ на: комментарий от anonymous

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

abs ★★★
() автор топика
Ответ на: комментарий от grouzen

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

abs ★★★
() автор топика
Ответ на: комментарий от grouzen

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

abs ★★★
() автор топика
Ответ на: комментарий от abs

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

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

arkhnchul ★★
()
Ответ на: комментарий от arkhnchul

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

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

arkhnchul ★★
()
Ответ на: комментарий от arkhnchul

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

anonymous
()
Ответ на: комментарий от abs
for (final Bact i : list) {
}

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

Kuzy ★★★
()
Ответ на: комментарий от abs

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

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

ya-betmen ★★★★★
()
Ответ на: комментарий от abs

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

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

Kuzy ★★★
()
Ответ на: комментарий от ya-betmen

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

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

abs ★★★
() автор топика
Ответ на: комментарий от abs

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

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

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

ya-betmen ★★★★★
()
Ответ на: комментарий от ya-betmen

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

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

abs ★★★
() автор топика
Ответ на: комментарий от abs

хотспот

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

пишется под Android

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

ya-betmen ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.