Java-Gaming.org Hi !
Featured games (91)
games approved by the League of Dukes
Games in Showcase (808)
Games in Android Showcase (239)
games submitted by our members
Games in WIP (872)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1] 2
  ignore  |  Print  
  Best way to iterate through ArrayList?  (Read 23380 times)
0 Members and 1 Guest are viewing this topic.
Offline matanui159

JGO Coder


Medals: 11
Projects: 1
Exp: 10-12 months


Aww... So cute...


« Posted 2014-10-15 00:03:51 »

I know four ways to do this... But which way is the best?

1. Using an iterator
2. Using a for loop with array.size() as the max value
3. Using array.toArray(new <some object>
  • );
4. Just using for (<some object> val : array) {} (this actually works!)

Just as a note, I will be iterating through it a lot so what is actually the best way which is easiest and the best?

Is it sad that I still get a fright when the computer beeps at me...
Offline BurntPizza

« JGO Bitwise Duke »


Medals: 486
Exp: 7 years



« Reply #1 - Posted 2014-10-15 00:09:55 »

"Which way is best?"

 Stare

Raw performance: c-style for loop, only really matters if it's an inner loop as it saves creating an iterator each time
List.toArray() makes a copy each time, horrible
Enhanced for: syntax sugar for creating an iterator, use in most cases. The sugar exists for a reason.
Manual Iterator: If you need to remove values while iterating, or need a ListIterator or some other specific iterator.
There's also while loops, which are sometimes more readable. And the rare do-while loop.
Also rare: recursive method that traverses the list

EDIT: and streams!
Offline ra4king

JGO Kernel


Medals: 508
Projects: 3
Exp: 5 years


I'm the King!


« Reply #2 - Posted 2014-10-15 06:46:16 »

Streams are probably my new favorite way of going through some Collection to perform operations on it. They're like LINQ for Java! Smiley

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline matanui159

JGO Coder


Medals: 11
Projects: 1
Exp: 10-12 months


Aww... So cute...


« Reply #3 - Posted 2014-10-15 07:12:15 »

So use array.size()?
What about if I want to return an array from an ArrayList? Do I use array.toArray(new <some object>
  • )?

Is it sad that I still get a fright when the computer beeps at me...
Offline Rayvolution

« JGO Spiffy Duke »


Medals: 379
Projects: 2
Exp: 2 years


Resident Crazyman


« Reply #4 - Posted 2014-10-15 07:15:50 »

Personally I use No.2, it's just easy to code IMO.

But I'd love to hear of a faster way, as I use quite a lot of ArrayLists in Retro-Pixel Castles.

- Raymond "Rayvolution" Doerr.
Retro-Pixel Castles - Now on Steam!
LIVE-STREAMING DEVELOPMENT: http://www.hitbox.tv/rayvolution
Offline philfrei
« Reply #5 - Posted 2014-10-15 08:20:53 »

Here's another.   Wink

1  
2  
3  
4  
try {
    array[idx++];
}
catch(ArrayIndexOutOfBoundsException e){}

music and music apps: http://adonax.com
Offline Gibbo3771

JGO Kernel


Medals: 128
Projects: 5
Exp: 1 year


Currently inactive on forums :(


« Reply #6 - Posted 2014-10-15 08:29:05 »

Here's another.   Wink

1  
2  
3  
4  
try {
    array[idx++];
}
catch(ArrayIndexOutOfBoundsException e){}


Surely that is considered hacky? lol

@OP, I tend to use the enhanced for each loop. Easy to ready, fast to code and seems to do the job.

1  
2  
3  
for(Foo foo : listOfFoos){
    foo.something();
}

"This code works flawlessly first time and exactly how I wanted it"
Said no programmer ever
Offline richierich
« Reply #7 - Posted 2014-10-15 08:41:43 »

Using an iterator or the enhanced for loop means a tiny extra loop-set-up cost (just a handful of variables in the iterator object) which is irrelevant if the loop's going round more than a handful of times. Then each time round, it'll be doing a couple of extra tests, which may be somewhat significant if the looped block's got very little in it, like searching for an element then breaking out or something trivial like that.

In general I'd say use the one which reads best in the context of what the code's doing at the time, usually the Java enhanced for loop if possible because it's neatest, otherwise what BurntPizza said. Tune later if need be.

In particular I don't like using a for (int x.....) loop when x isn't used for anything else except obtaining the next item. Apart from being less elegant it runs the risk of creating a problem later if the list is changed to a different type with inefficient random access.
Offline princec

« JGO Spiffy Duke »


Medals: 1146
Projects: 3
Exp: 20 years


Eh? Who? What? ... Me?


« Reply #8 - Posted 2014-10-15 08:50:00 »

(No-one ever uses any other kind of list than an ArrayList, mind Smiley)

Cas Smiley

Offline nsigma
« Reply #9 - Posted 2014-10-15 09:47:50 »

Just as a note, I will be iterating through it a lot so what is actually the best way which is easiest and the best?

What about modifying it a lot?  Do you need to modify the list while iterating it?

Both those questions may impact on the right solution.  In Praxis LIVE I have various 'collections' which are iterated often, modified rarely and occasionally modified while iterating.  I'm actually using arrays and this simple class which handles adding or removing an item and returning a copy of the array.  It's basically externalising some of the functionality of CopyOnWriteArrayList.  It has the added benefit of allowing to use the enhanced-for loop without creating an iterator.

Praxis LIVE - hybrid visual IDE for (live) creative coding
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Cero
« Reply #10 - Posted 2014-10-15 16:02:26 »

The "best" way I think is this:

1  
2  
3  
4  
5  
6  
7  
8  
9  
for (int i = projectiles.size() - 1; i >= 0; i--)
{
   projectiles.get(i); // do something
     
   if (removeCriteria)
   {
      projectiles.remove(i);
   }
}


I call it the reverse loop, and it allows you to iterate AND remove elements in the same loop.

Offline GoToLoop

Junior Devvie


Medals: 2
Exp: 1 year



« Reply #11 - Posted 2014-10-15 16:56:55 »

Nah! Best quickest algorithm is this:   Tongue  

1  
2  
3  
4  
5  
for (int len = projectiles.size(), i = len; i-- != 0; )
  if (projectiles.get(i).removeCriteria()) {
    projectiles.set(i, projectiles.get(--len));
    projectiles.remove(len);
  }
Offline philfrei
« Reply #12 - Posted 2014-10-15 18:44:31 »

Here's another.   Wink

1  
2  
3  
4  
try {
    array[idx++];
}
catch(ArrayIndexOutOfBoundsException e){}


Surely that is considered hacky? lol

Yep.

I just found a discussion of the technique:
Quote
try-catch blocks generally use no extra time if no exception is thrown...Throwing an exception and executing the catch block has a significant overhead. This overhead seems to be due mainly to the cost of getting a snapshot of the stack when the exception is created...Generally, the performance cost of throwing an exception is equivalent to several hundred lines of simple code executions...You can reduce the cost by reusing an exception object rather than creating a new one...is two orders of magnitude faster...the sole disadvantage of reusing an exception instance is that the instance does not have the correct stack trace...
From Java Performance Tuning by Jack Shirazi, 2003. (pages 172-176)

It definitely seems like asking for trouble. In chapter 7, Shirazi profiles examples of a few cases where it might eek out a slight performance benefit. The best case that can be made for its use is if the end test is a significant percentage of the looping code (i.e., only a couple statements in the loop) and the number of iterations is really large. Then, perhaps the gain in dropping the iteration-is-done test outweighs the cost (assuming you throw an existing exception rather than generating a new one). But you still have to deal with the inevitable WTF that occurs when looking at the code fresh a few months later.

music and music apps: http://adonax.com
Offline richierich
« Reply #13 - Posted 2014-10-15 19:27:39 »

This overhead seems to be due mainly to the cost of getting a snapshot of the stack when the exception is created ... exception object...

It would be cool if you could install a custom exception type to be thrown instead of ArrayIndexOutOfBoundsException, and the custom type didn't collect a stack trace.

(By cool I mean evil Cheesy)
Offline BurntPizza

« JGO Bitwise Duke »


Medals: 486
Exp: 7 years



« Reply #14 - Posted 2014-10-15 19:44:51 »

More info on that: http://java-performance.info/throwing-an-exception-in-java-is-very-slow/

About the loops: GoToLoop's (heh) is better than Cero's for ArrayList simply because it avoids large copies. I forgot to mention that technique in my initial post.
Offline nsigma
« Reply #15 - Posted 2014-10-16 10:15:13 »

About the loops: GoToLoop's (heh) is better than Cero's for ArrayList simply because it avoids large copies.

If order isn't important to you! In fact, @Cero's answer would also be problematic if order was important.  I remember someone (think @princec) posting a technique in an old thread on this using two ArrayLists, and ping-ponging valid values between them, which avoids most large array copies and retains the ordering.

As I said in my answer above, there is not really a way to answer the OP's question without context, and for that matter the question may be incorrect assuming ArrayList answers that problem in the first place.  One rarely iterates ArrayLists just for the hell of it!  Wink

Praxis LIVE - hybrid visual IDE for (live) creative coding
Offline princec

« JGO Spiffy Duke »


Medals: 1146
Projects: 3
Exp: 20 years


Eh? Who? What? ... Me?


« Reply #16 - Posted 2014-10-16 10:28:14 »

That thread ended up with an even simpler implementation using no extra space and very cache-friendly, and also has the ability to allow new things to be added to the list while it's iterating:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
for (int i = 0, pos = 0; i < list.size(); i ++) {
   Thing thing = list.get(i);
   thing.doStuff();
   if (thing.isActive()) {
      list.set(pos ++, thing);
   }
}
// This next bit could be implemented more efficiently probably if the list had some sort of truncation method
for (int i = list.size(); --i >= pos;) {
   list.remove(i);
}


Cas Smiley

Offline basil_

« JGO Bitwise Duke »


Medals: 418
Exp: 13 years



« Reply #17 - Posted 2014-10-16 11:00:35 »

the bag by kappa : http://www.java-gaming.org/topics/the-bag-fast-object-collection/24203/view.html
RW collection by riven : http://www.java-gaming.org/topics/readwritecollection-for-entities/28660/view.html

use these, do not use ArrayList (if you ask for the "best" way), at least use http://fastutil.di.unimi.it/

make your own array-list class.

o/
Offline nsigma
« Reply #18 - Posted 2014-10-16 16:38:01 »

That thread ended up with an even simpler implementation using no extra space and very cache-friendly, and also has the ability to allow new things to be added to the list while it's iterating:

Ah, nice, I'd forgotten or not read that bit!  Smiley

Quote
1  
// This next bit could be implemented more efficiently probably if the list had some sort of truncation method

Subclassing ArrayList and using removeRange(..) might be slightly more efficient?

Praxis LIVE - hybrid visual IDE for (live) creative coding
Offline matanui159

JGO Coder


Medals: 11
Projects: 1
Exp: 10-12 months


Aww... So cute...


« Reply #19 - Posted 2014-10-16 22:33:37 »

Thx for the responses... But if I had an ArrayList called enemies (for example)...
And I had a method called getEnemies which returns a normal array... What is the best way to convert it? At the moment I am using enemies.toArray(new Enemy[0]);
(Actually im not because I don't have an array called enemies)

Is it sad that I still get a fright when the computer beeps at me...
Offline richierich
« Reply #20 - Posted 2014-10-17 12:30:33 »

(No-one ever uses any other kind of list than an ArrayList, mind Smiley)

I've kind of wondered about that ever since I started doing Java a couple of years ago and looked through people's code. I'd noticed LinkedLists weren't really used but never really thought about why. This post made me look into it and now I know it's because array processing is more cache friendly! Well I'll be.... Roll Eyes Guess I'm a bit behind the cutting edge here. The C++ code I've seen and worked on over the years uses plenty of linked lists, but I guess was mostly written before cache architectures became common.

Anyway I took a look at the only place I've used a LinkedList in my Java code so far (as the A* open list) and swapped it out for an ArrayList just for kicks. Who knew, the ArrayList is straight away quicker a lot of the time, even though the code was specifically written to work with a LinkedList!!! Haha, what a waste of time those data structure courses were Cheesy

Having said that, the linked list comes back into its own with a less aggressive heuristic function, and if I put more obstacles in the way, because it gets costly to insert all the new nodes into the array. So now I have to decide if I can be bothered to rewrite or not - if I do I'll probably home bake something in between using some of the suggestions people have made in this thread.

Either way it's been a good learning day Smiley

Offline GoToLoop

Junior Devvie


Medals: 2
Exp: 1 year



« Reply #21 - Posted 2014-10-17 13:00:15 »

For me it's either regular Array[], ArrayList or ArrayDeque:  persecutioncomplex
http://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeque.html  
Offline GoToLoop

Junior Devvie


Medals: 2
Exp: 1 year



« Reply #22 - Posted 2014-10-17 13:09:31 »

What about:      for (Enemy e : getEnemies())  enemies.add(e);   Tongue
or even 133t:   enemies.addAll( java.util.Arrays.asList(getEnemies()) );
Offline matanui159

JGO Coder


Medals: 11
Projects: 1
Exp: 10-12 months


Aww... So cute...


« Reply #23 - Posted 2014-10-17 13:13:17 »

That is what I'm currently using... But what is the best way to make 'getEnemies'?

Is it sad that I still get a fright when the computer beeps at me...
Offline BurntPizza

« JGO Bitwise Duke »


Medals: 486
Exp: 7 years



« Reply #24 - Posted 2014-10-17 13:15:48 »

It's not what you're currently using, because it throws a ConcurrentModificationException.

What do you mean how to make getEnemies()? Why are you using an array in the first place?
Offline Jacob Pickens
« Reply #25 - Posted 2014-10-17 18:10:05 »

I find that the simple technique like this:

1  
2  
3  
for(int i = 0; i < array.size(); i++) {
     System.out.println(i);
}


Works best. I have tried to iterate through array lists using an advanced for loop and I mean it works, but it seems to not like Slick2D and other libraries i use so I have gotten errors many a time.

If you wanted to get as close as you can to an advance for loop and iterate though objects in the for loop you could do this:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
ArrayList<Player> list = new ArrayList<Player>();

Player tempPlayer;

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

     //This line is just to show a use. Not necessary.
     System.out.println("X: " + tempPlayer.x, "Y: " + tempPlayer.y);
}


Good luck with your games, man!

Offline SilverTiger

JGO Coder


Medals: 41
Exp: 3 years


がんばってください!


« Reply #26 - Posted 2014-10-17 21:33:41 »

Streams are probably my new favorite way of going through some Collection to perform operations on it. They're like LINQ for Java! Smiley

I like Streams too, so if you use Java 8 you can use them!

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
// One Operation
array.stream().forEach(val -> val.doSomething());

// Multiple Operations:
array.stream().forEach(val -> {
    val.doSomething();
    val.doSomeOtherThings();
});

// You could even make crazy things like this:
array.stream().filter(val -> val.isAThing())
              .forEach(thing -> thing.doSomething());

Just wanted to show some examples for this Wink
For some more methods you can look into the Java Doc.

Offline BurntPizza

« JGO Bitwise Duke »


Medals: 486
Exp: 7 years



« Reply #27 - Posted 2014-10-17 21:37:15 »

1  
2  
3  
// You could even make crazy things like this:
array.stream().filter(val -> val.isAThing())
              .forEach(thing -> thing.doSomething());


If you think that's crazy...
Offline SilverTiger

JGO Coder


Medals: 41
Exp: 3 years


がんばってください!


« Reply #28 - Posted 2014-10-17 21:40:27 »

If you think that's crazy...
Didn't want to make it too complicated Cheesy

Offline HeroesGraveDev

JGO Kernel


Medals: 383
Projects: 11
Exp: 4 years


┬─┬ノ(ಠ_ಠノ)(╯°□°)╯︵ ┻━┻


« Reply #29 - Posted 2014-10-17 21:46:08 »

@Jacob_Pickens: That method will cause silent problems if you remove entities during iteration.

Pages: [1] 2
  ignore  |  Print  
 
 

 
Riven (847 views)
2019-09-04 15:33:17

hadezbladez (5795 views)
2018-11-16 13:46:03

hadezbladez (2603 views)
2018-11-16 13:41:33

hadezbladez (6211 views)
2018-11-16 13:35:35

hadezbladez (1499 views)
2018-11-16 13:32:03

EgonOlsen (4734 views)
2018-06-10 19:43:48

EgonOlsen (5793 views)
2018-06-10 19:43:44

EgonOlsen (3276 views)
2018-06-10 19:43:20

DesertCoockie (4175 views)
2018-05-13 18:23:11

nelsongames (5501 views)
2018-04-24 18:15:36
A NON-ideal modular configuration for Eclipse with JavaFX
by philfrei
2019-12-19 19:35:12

Java Gaming Resources
by philfrei
2019-05-14 16:15:13

Deployment and Packaging
by philfrei
2019-05-08 15:15:36

Deployment and Packaging
by philfrei
2019-05-08 15:13:34

Deployment and Packaging
by philfrei
2019-02-17 20:25:53

Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!