Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (107)
games submitted by our members
Games in WIP (534)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Question - Iterating through an ArrayList  (Read 2232 times)
0 Members and 1 Guest are viewing this topic.
Offline Gudradain
« Posted 2009-04-20 20:54:18 »

Hello

I was looking for the bottlenect in my game and I find it at a strange place and I wonder why.

So the game is basically a lag test in which I have n circle. The bottleneck was iterating through a small  (between 1 and 5 elements) ArrayList n*n time. I was using this code to iterate :
1  
2  
3  
for(int i : list){
              //Do something
       }


I fix it by using this code :
1  
2  
3  
for(int i=0; i<list.size(); i++){
              //Do something
       }


So my question is why does it fix it. Is it because with for(int i : list) it creates an Iterator object and that's what take more time?

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 743
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #1 - Posted 2009-04-20 21:37:54 »

enhanced for loop over int[]
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
// YOUR code

int[] array = ...;
for(int item: array)
   // stuff



// REAL code

int[] array = ...;
for(int i=0; i<array.length; i++)
   int item = array[i]; // stuff





enhanced for loop over List<Integer>
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
// YOUR code

List<Integer> list = ...;
for(int item: list)
   // stuff



// REAL code

List<Integer> list= ...;
Iterator it = list.iterator();
while(it.hasNext());
   int item = ((Integer)it.next()).intValue(); // stuff

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Json

Junior Member


Exp: 7 years



« Reply #2 - Posted 2009-04-20 21:43:40 »

I would have thought the first method to be the fastest actually.

http://stackoverflow.com/questions/256859/is-there-a-performance-difference-between-a-for-loop-and-a-for-each-loop

Switching the i++ to read ++i might speed things up somewhat as well believe it or not Cheesy

// Json
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 743
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #3 - Posted 2009-04-20 21:46:54 »

Don't forget that iterator.hasNext() and iterator.next() must both perform exactly the same bounds checks.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Json

Junior Member


Exp: 7 years



« Reply #4 - Posted 2009-04-20 21:49:25 »

Of course you can optimise it some more as well.

1  
2  
3  
4  
5  
final int size = list.size();

for(int i = 0; ++i < size;) {
    //Do something
}



No need to call the size() method every time Cheesy

// Json
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 743
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #5 - Posted 2009-04-20 21:52:27 »

My point is that these are very different beasts:

for(int item: array)
   // stuff

for(int item: list)
   // stuff

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Gudradain
« Reply #6 - Posted 2009-04-20 21:53:30 »

I would have thought the first method to be the fastest actually.

The second was nearly 2 times faster in my case.
Offline Gudradain
« Reply #7 - Posted 2009-04-20 21:55:13 »

My point is that these are very different beasts:

for(int item: array)
   // stuff

for(int item: list)
   // stuff


It was 2 ArrayList<E>. (but I guess it still apply)
Offline Json

Junior Member


Exp: 7 years



« Reply #8 - Posted 2009-04-20 21:56:11 »

How was the ArrayList declared if I may ask?

// Json
Offline DzzD
« Reply #9 - Posted 2009-04-20 22:02:14 »

So my question is why does it fix it. Is it because with for(int i : list) it creates an Iterator object and that's what take more time?

this is something that may happend when you program at a "too high level", like in this one you dont tell to the processor/computer what kind of variables/objects that bunch of code will use so the code is very "Generics" but very slow too...

Quote
Switching the i++ to read ++i might speed things up somewhat as well believe it or not

? i++ & ++i are both using "negligable" cpu in comparaison of others instructions in the loop

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Gudradain
« Reply #10 - Posted 2009-04-20 22:20:03 »

How was the ArrayList declared if I may ask?

When I create the object containing the ArrayList at the begin of the game. That's the exact line :

1  
protected ArrayList<Integer> positionLevel = new ArrayList<Integer>();

Offline davidc

Senior Member


Medals: 5
Projects: 2



« Reply #11 - Posted 2009-04-21 05:08:36 »

1  
2  
3  
for(int i : list){
              //Do something
       }


The first example will be less efficient because it requires an implicit conversion between Integer and int, due to autoboxing. You might find it performs better like this:

1  
2  
3  
for(Integer i : list){
              //Do something
       }


However, "i" will still probably require conversion to int (either implicitly or explicitly) for it to be useful in your code.
Offline Gudradain
« Reply #12 - Posted 2009-04-21 05:45:34 »

@davidc I tried it but it doesn't seems to affect the speed.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 743
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #13 - Posted 2009-04-21 07:12:04 »

Why not put your ints in an int[]

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline davidc

Senior Member


Medals: 5
Projects: 2



« Reply #14 - Posted 2009-04-21 11:13:40 »

@davidc I tried it but it doesn't seems to affect the speed.

You might be doing an implicit conversion inside the loop itself, which affects the performance in the same way.

Why not put your ints in an int[]

That's what I would do if performance was the top priority and the code was being called often enough to warrant it. You lose the flexibility of an array list but avoid autoboxing altogether. If it comes down to it, you can create an array of fixed size and then reallocate if it needs to be bigger. This is fine if you know what the maximum size will be.


Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #15 - Posted 2009-04-21 11:24:08 »

You could try Primative collections for Java? There's a bunch of collections written in the same api style but specifically coded to only deal with one type of primitive at a time. That should give you the flexibility of a resizable array but without the overhead of iterators or autoboxing.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline Json

Junior Member


Exp: 7 years



« Reply #16 - Posted 2009-04-21 11:36:16 »

Then there is also the javolution libraries for performance.

http://javolution.org/

// Json
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

pw (35 views)
2014-07-24 01:59:36

Riven (34 views)
2014-07-23 21:16:32

Riven (22 views)
2014-07-23 21:07:15

Riven (25 views)
2014-07-23 20:56:16

ctomni231 (56 views)
2014-07-18 06:55:21

Zero Volt (48 views)
2014-07-17 23:47:54

danieldean (39 views)
2014-07-17 23:41:23

MustardPeter (43 views)
2014-07-16 23:30:00

Cero (59 views)
2014-07-16 00:42:17

Riven (56 views)
2014-07-14 18:02:53
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
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!