Java-Gaming.org    
Featured games (91)
games approved by the League of Dukes
Games in Showcase (578)
games submitted by our members
Games in WIP (499)
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 3 ... 5
  ignore  |  Print  
  ArrayList vs LinkedList  (Read 11761 times)
0 Members and 1 Guest are viewing this topic.
Offline DrewLols

Senior Member


Medals: 1
Projects: 1


Noob going through metamorphosis...


« Posted 2012-08-03 01:41:45 »

In my 2D platformer game, any object that can interact with the world around it is called an Interactable and is expected to be added to a level.  So far, I've been adding each Interactable into an ArrayList which I constantly loop through to make each Interactable run.

So far, this method hasn't really faltered because I'm not typically adding and removing objects constantly.  I'm considering using a LinkedList, however, seeing as I plan to have Interactables be added and removed at a fast pace.  Would using a LinkedList be important in this scenario?

Did you know that 90% of statistics are wrong?
Offline ra4king

JGO Kernel


Medals: 322
Projects: 2
Exp: 4 years


I'm the King!


« Reply #1 - Posted 2012-08-03 02:01:38 »

Stick with ArrayList because the objects are put into a backing array, which is faster to loop through than a LinkedList's nodes.

Offline Jay_PC

Senior Newbie





« Reply #2 - Posted 2012-08-03 02:27:11 »

Also Doesn't LinkedList leave null spaces in the List if you remove an object? or was that Hashtable...
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline theagentd
« Reply #3 - Posted 2012-08-03 02:35:44 »

LinkedList is rarely useful, since it has so much overhead even when it is supposed to be faster. For a very very large list where objects are constantly removed randomly hundreds of times per frame or so, LinkedList might be faster. The problem with LinkedList is that it creates an Entry object which it wraps in each object added to store the next and previous entries. This allocation (and later garbage collection) makes it a lot slower to add and remove stuff than ArrayList in most use cases. ArrayList's only weakness is removing objects in the beginning or middle of the list, since all following objects have to be shifted to fill the hole created. The longer the list the slower it becomes.

Even when you have lots of stuff to remove, ArrayList can be a good choice. Lists are often used to keep track of game objects. So you say "But wait! The objects will always be added at the end of the list, but as they die they will be removed! I have thousands of objects, so I should use a LinkedList to avoid shifting thousands of objects on every remove()!". Nope! Most likely the best solution is to use TWO ArrayLists and pingpong your objects between them. By doing that you can avoid all shifting while still getting fast (and random) access to all objects.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
ArrayList<GameObject> currentList, nextList;

//Lists created at load time


//Example game loop:

while(true){

    update(); //Updates all objects
   render(); //Draws all objects

}

private void update(){
    for(int i = 0; i < currentList.size(); i++){
        GameObject go = currentList.get(i);
        go.update();
        if(go.isAlive()){
            nextList.add(go);
        }
    }
   
    //Alive objects are now in nextList. Clear currentList.
   currentList.clear();
   
    //Swap current and next list
   ArrayList<GameObject> temp = nextList;
    nextList = currentList;
    currentList = temp;
}


Also Doesn't LinkedList leave null spaces in the List if you remove an object? or was that Hashtable...
Nope, LinkedList does not leave null spaces. Only arrays do that (obviously). Hashtables/HashMaps KIND OF do that, but that's simply because the key no longer maps to anything, so it returns null instead. Not really the same in my opinion.

Myomyomyo.
Offline sproingie
« Reply #4 - Posted 2012-08-03 04:04:38 »

A great deal of shifting can also be avoided by using an ArrayDeque.  But using two ArrayLists is also pretty legit, it's basically like having your own little semispace gc.
Offline princec

JGO Kernel


Medals: 282
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #5 - Posted 2012-08-03 11:42:31 »

Though it has to be said, considering the number of things that might be found in an ArrayList, removing things from the head of the queue is really often so fast you'd never ever notice it. It depends on how many things are likely to be in it...

Consider a real-life example of, hmm... Particles. So you've got 5,000 particles in a frame (a high figure, but not unlikely). They're stored in an ArrayList. Each entry in the ArrayList takes 4 bytes, so that's 20kb of RAM, fitting neatly in the L1 data cache on many if not all desktops.

Now, imagine the rather unlikely even that every single particle dies one frame, and you discover this as you iterate through the ArrayList (using an integer index, not an iterator, just for absolute efficiency's sake). You have to shuffle 4,999 particles down 4 bytes. It's all in the L1 cache so memory access is effectively free to the CPU; you spend 4,999 cycles moving your particles assuming the loop that copies the data is about as simple and efficient as it can be. Then you have to do it again on the next particle. 4998 cycles. Repeat to solve triangular number, approximately (5000x5000)/2, or in the end 12,500,000 clock cycles, without ever having to touch the L2 or L3 caches most likely, let alone system RAM, until the end of the operation.

That's 12.5m cycles out of your 3.3 million or so you've typically got in a single video frame (2GHz core). Oh dear, you just spent 4 frames ditching a mere 5000 particles. Judder. Imagine if you had, somehow, 10000 particles. That'd be nearly a second wasted doing something utterly trivial and would present itself as a horrible jarring delay in your buttery smooth animation.

But what if, weirdly but possibly, the worst case occurred when even going backwards - every other particle died in one frame? Well, then you'd be compacting a slowly more complex list of particles even if you were scanning backwards. Scanning forwards would be exactly the same speed too.

So you'd be crafty and use the third and final technique which is to make a copy of the original arraylist, and copy the surviving particles into it each frame. This performs consistently no matter how many live or dead particles you have in any particular frame or the pattern of their expiration.

Anyway - for the OP - basically you need to do Just That. Each frame, scan your list of Interactables, and copy each live one into a second ArrayList, and then point your game at that ArrayList. Flip between two ArrayLists, alternating each frame, rather than creating (and expanding!) an ArrayList every frame, or that'll be slow.

Cas Smiley

Offline jmart

Junior Member


Medals: 1



« Reply #6 - Posted 2012-08-03 20:05:50 »

It seems like ArrayList might not be the best. 

How are you removing items from the list?  Specifically do you know the item you are removing and then removing it or are you looping through the list to find out which have to be removed?
Offline ra4king

JGO Kernel


Medals: 322
Projects: 2
Exp: 4 years


I'm the King!


« Reply #7 - Posted 2012-08-03 20:40:26 »

It seems like ArrayList might not be the best. 

How are you removing items from the list?  Specifically do you know the item you are removing and then removing it or are you looping through the list to find out which have to be removed?
Interesting first post. Welcome to JGO anyhow! Tongue

Offline jmart

Junior Member


Medals: 1



« Reply #8 - Posted 2012-08-03 20:48:33 »

Thank you for the welcome.  I despise the first post question.  Figure I try to answer some questions and be useful before asking questions myself. Smiley
Online jonjava
« Reply #9 - Posted 2012-08-03 20:54:30 »

It seems like ArrayList might not be the best. 

How are you removing items from the list?  Specifically do you know the item you are removing and then removing it or are you looping through the list to find out which have to be removed?

Look at theagentd's example code and princec's in depth explanation for your answer! :]

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Spasi
« Reply #10 - Posted 2012-08-03 21:11:04 »

I've been using GapList recently. Until the code that uses the list shows up in a profiler, it's a good option if you don't want to worry about the differences between ArrayList and LinkedList.
Offline jmart

Junior Member


Medals: 1



« Reply #11 - Posted 2012-08-03 21:17:27 »

The solution proposed by theagentd and princec work when every object in the list needs to be checked for state.  But DrewLol did not state that that is how he is deciding what gets removed.  He might have an object report that it has died and now needs to be removed.  In the scenario removing fromt he list involves an O(n) search.  In that case a HashSet or HashMap might actually be better because it has O(logn) search time.

 
Online jonjava
« Reply #12 - Posted 2012-08-03 21:21:47 »

He might have an object report that it has died and now needs to be removed.

How do you mean?

Offline UprightPath
« Reply #13 - Posted 2012-08-03 21:30:58 »

I'm making a guess here, but something like...

You have a system set up so that an object will notify some controller object that it has finished being useful and should be removed from the list. Something like a bullet that's just discovered that it impacted against a wall. It'll tell the physics controller "I impacted, remove me from the list of collision objects please!"

In that case, depending on how you wrote your code, the physics controller would have to spend some time searching through its list of objects and remove it.

Online jonjava
« Reply #14 - Posted 2012-08-03 21:52:51 »

Since the controller loops through the list of objects in order to call their update() method it can simply check if the object it's updating has reached its usefulness and discard it right there without looping through the list an unnecessary amount of times per discarded object like theagentd's code does?

Moreover if the object itself needs to notify the controller you might discard the object mid-update or cause concurrency issues. A situation where the controller is no longer in control but the objects it's supposed to control pushes the controller around.

I can't really conceptualize the scenario you're describing, I could be wrong.

Offline matheus23

JGO Wizard


Medals: 97
Projects: 3


You think about my Avatar right now!


« Reply #15 - Posted 2012-08-03 22:02:22 »

I've been using GapList recently. Until the code that uses the list shows up in a profiler, it's a good option if you don't want to worry about the differences between ArrayList and LinkedList.
<offtopic>Do you have the code for the implentation? It's not in Java 6... </offtopic>

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline Spasi
« Reply #16 - Posted 2012-08-03 23:32:48 »

<offtopic>Do you have the code for the implentation? It's not in Java 6... </offtopic>

There's a link at the end of that article. Anyway, you can download it here.
Offline matheus23

JGO Wizard


Medals: 97
Projects: 3


You think about my Avatar right now!


« Reply #17 - Posted 2012-08-03 23:36:33 »

<offtopic>Do you have the code for the implentation? It's not in Java 6... </offtopic>

There's a link at the end of that article. Anyway, you can download it here.

Wohooow! thank you Smiley

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline jmart

Junior Member


Medals: 1



« Reply #18 - Posted 2012-08-04 03:08:54 »

If I have a game that is moving at 30 - 40 frames a second I am not going to be looping through lists of objects needlessly at each of those frames.  For the most part nothing is happening of interest during most of those loops.  You need to save your CPU for animation, math, collision detection, event handling.  A callback to a controller when an event occurs is more efficient.
Offline Best Username Ever

Junior Member





« Reply #19 - Posted 2012-08-10 04:48:32 »

The solution proposed by theagentd and princec work when every object in the list needs to be checked for state.  But DrewLol did not state that that is how he is deciding what gets removed.  He might have an object report that it has died and now needs to be removed.  In the scenario removing fromt he list involves an O(n) search.  In that case a HashSet or HashMap might actually be better because it has O(logn) search time.

I was wondering why no one else had steered DrewLols away from using a List at all. Out of all the Java Collections a HashSet seems to be the best option for his scenario. (By the way, hash tables have O(1) add, remove, and query times. Not log n.) In my projects I use a Bag (though slightly different then Kappa's and more like a special purpose set than a general purpose bag or multiset.)

My class* implements
1  
2  
3  
4  
5  
6  
void add(GameObject o) // Whether I use automatic resizing depends on the project
int size() // Standard element count method
void clear() // Standard remove everything method
void resize(int capacity) // Intended for explicitly changing capacity if I don't use a fixed capacity
Iterator<GameObject> iterator() // See note **
// ** One other method

* I often work directly with an array
** In order to remove "dead" objects I either implement a normal remove(GameObject o) method OR, more frequently, implement something like call removeDeadObjects() or inline code to do the same once per update, OR use Iterator's remove method since it can be done in O(1) time with one swap.
Offline coltonoscopy

Junior Member


Medals: 2



« Reply #20 - Posted 2012-08-10 05:05:01 »

Best Username Ever,

Wouldn't that not work if the OP needed to add two Interactables of the same kind into his set?

Colton

Straight flippin.
Offline Best Username Ever

Junior Member





« Reply #21 - Posted 2012-08-10 06:42:18 »

I don't think so. By "kind" do you mean class? Sets can't store duplicates. Bags and Lists can, but storing multiple references to the same instance sounds like a source of bugs.
1  
2  
3  
4  
5  
6  
Car c1 = new Car(), c2 = new Car();
Building b = new Building();
collection.add(c1);
collection.add(c2); // Fine so far
collection.add(b);
collection.add(c1); // Does this get stored once or twice? Is it updated once or twice per update to c2?
Offline coltonoscopy

Junior Member


Medals: 2



« Reply #22 - Posted 2012-08-10 06:59:20 »

I don't think so. By "kind" do you mean class? Sets can't store duplicates. Bags and Lists can, but storing multiple references to the same instance sounds like a source of bugs.
1  
2  
3  
4  
5  
6  
Car c1 = new Car(), c2 = new Car();
Building b = new Building();
collection.add(c1);
collection.add(c2); // Fine so far
collection.add(b);
collection.add(c1); // Does this get stored once or twice? Is it updated once or twice per update to c2?

Ah, I did a test, and you're right! Very interesting, because my understanding of Sets was that they stored unique entries, and I guess individually allocated Objects of any kind are considered unique to the HashSet. Maybe this is common knowledge, but I just took a data structures course, and since that's what I was taught, I figured it would hold true for this scenario. :p Cool! Cheesy

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
package test;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class HashSetTest
{  
    public static void main(String args[])
    {
        Set<Clown> clowns = new HashSet<Clown>();
       
        clowns.add(new Clown());
        clowns.add(new Clown());
        clowns.add(new Clown("Jack"));
        clowns.add(new Clown("Jill"));
        clowns.add(new Clown("Jill"));
       
        Iterator i = clowns.iterator();
       
        while (i.hasNext())
        {
            Clown c = (Clown)i.next();
            System.out.println(c.getName());
        }
    }
}

class Clown
{
    private String name;
   
    public Clown(String name)
    {
        this.name = name;
    }
   
    public Clown()
    {
        name = "John";
    }
   
    public String getName()
    {
        return name;
    }
}


1  
2  
3  
4  
5  
6  
7  
run:
Jill
John
John
Jill
Jack
BUILD SUCCESSFUL (total time: 0 seconds)


Best regards,
Colton

Straight flippin.
Offline _Al3x

JGO Coder


Medals: 7
Projects: 1


Indie Games FTW!


« Reply #23 - Posted 2012-08-10 07:06:43 »

It get stored twice, notice that what you store are references to objects, not the actual objects. Smiley

About updating, collection won't update anything, since all it holds is a memory adress, if what's in that adress changes, it doesn't need to be updated anywhere else.

Smiley

Offline coltonoscopy

Junior Member


Medals: 2



« Reply #24 - Posted 2012-08-10 07:09:17 »

It get stored twice, notice that what you store are references to objects, not the actual objects. Smiley

About updating, collection won't update anything, since all it holds is a memory adress, if what's in that adress changes, it doesn't need to be updated anywhere else.

Smiley
Oh yes, that makes perfect sense now. Forgive me; I'm still learning! :] This is highly educational for me though, far beyond what school has ever taught me.

On a side note, Best Username, I've decided I may wish to start using Bags in my own games! ;] I know credit goes to kappa for it, but thank you for introducing me! I'm looking forward to doing some test cases to see how much faster it works in comparison to ArrayLists.

Best regards,
Colton

Straight flippin.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 605
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #25 - Posted 2012-08-10 07:09:56 »

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
class Clown
{
    private String name;
   
    public Clown(String name)
    {
        this.name = name;
    }
   
    public Clown()
    {
        name = "John";
    }
   
    public String getName()
    {
        return name;
    }

+    public boolean equals(Object obj) {
+        if(obj instanceof Clown) {
+            Clown that = (Clown)obj;
+            return this.name.equals(that.name);
+        }
+        return false;
+    }

+    public int hashCode() {
+         return this.name.hashCode();
+    }
}


1  
2  
3  
4  
5  
6  
7  
run:
Jill
John
- John
- Jill
Jack
BUILD SUCCESSFUL (total time: 0 seconds)

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

Junior Member


Medals: 2



« Reply #26 - Posted 2012-08-10 07:11:53 »

Riven,

Thanks! I guess I should jot down that one in my programming notebook for future purposes... my game engine could probably use a bit of that, now that I think about it  Shocked

EDIT: Wait, so I was technically right about this? Shocked

Well, actually, I suppose without implementing equals() the hash set would work just fine for the OP's purposes, but it just depends on whether or not that kind of functionality is added into the class. If it were me and I wanted to get the supposed performance benefits, then I guess I wouldn't add it into classes I know would be added into the set, but now that Riven basically just ripped my code a new one and taught me a lesson I think I'd much rather implement things that way!

Colton

Straight flippin.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 605
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #27 - Posted 2012-08-10 08:03:35 »

I don't quite get how performance has anything to do with it. Implementing .equals(...) and .hashCode( ) is critical for HashMap/HashSet to work.

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

Junior Member


Medals: 2



« Reply #28 - Posted 2012-08-10 08:09:56 »

I don't quite get how performance has anything to do with it. Implementing .equals(...) and .hashCode( ) is critical for HashMap/HashSet to work.
Sorry Riven! I meant the performance of the HashSet, not the classes to be placed within the HashSet! :p

It's just that he was saying he could get certain performance benefits with using the HashSet for these purposes, but it seems to me that if the objects passed into the set are equal, then this wouldn't be useful in a situation like the OP described, where he has essentially a stage of Interactables; my point was, what if there are two Interactables with the same attributes? They wouldn't be preserved in the set if this were the case, making the data structure worthless. Thus, in order to get the performance benefits he was talking about, he would have to omit those two methods you wrote in my code, which circumvented the set recognizing two objects with identical attributes. Otherwise, it would retain what makes it a set, and without the equals() and hashCode() methods, it seems to do little more than act as a list for those half-complete objects.

That's just my reasoning, anyway; I could be very wrong.  Lips Sealed

Colton

Straight flippin.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 605
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #29 - Posted 2012-08-10 08:16:23 »

You could argue that java.lang.Object was poorly designed, as tieing the root class of a type hierarchy to some collection based on hashes, seems rather awkward. I mean, you don't see Object defining compareTo(...) or compare(..., ...) to directly tie in with TreeMap or PriorityQueue...

Anyway, enough off-topic-ness. Your 'Clown' class threw me off, it's commonly accepted that two clowns with the same name are indistinguishable, hence the implementation of .equals(...) .


Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Pages: [1] 2 3 ... 5
  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.

xsi3rr4x (31 views)
2014-04-15 18:08:23

BurntPizza (28 views)
2014-04-15 03:46:01

UprightPath (43 views)
2014-04-14 17:39:50

UprightPath (26 views)
2014-04-14 17:35:47

Porlus (42 views)
2014-04-14 15:48:38

tom_mai78101 (64 views)
2014-04-10 04:04:31

BurntPizza (124 views)
2014-04-08 23:06:04

tom_mai78101 (224 views)
2014-04-05 13:34:39

trollwarrior1 (190 views)
2014-04-04 12:06:45

CJLetsGame (198 views)
2014-04-01 02:16:10
List of Learning Resources
by SHC
2014-04-18 03:17:39

List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30
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!