Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (476)
Games in Android Showcase (106)
games submitted by our members
Games in WIP (532)
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] 4 5
  ignore  |  Print  
  ArrayList vs LinkedList  (Read 12579 times)
0 Members and 1 Guest are viewing this topic.
Offline princec

JGO Kernel


Medals: 341
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #60 - Posted 2012-08-11 01:24:42 »

By all means use any collection you like. But the ArrayList method is fastest and uses least memory.

Cas Smiley

Offline jmart

Junior Member


Medals: 1



« Reply #61 - Posted 2012-08-11 03:51:15 »

The main point I am making is that you cannot say that ArrayList is best for all situations involving games, which is what was said.  And I totally agree that O notation does not help when dealing with smaller sets.  Every situation needs to have the correct collector picked out.  It could be that it is ArrayList, but it could be that it is something else.  Good unit testing with swappable collectors so you can test out the one that suites you.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 742
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #62 - Posted 2012-08-11 04:03:40 »

Did you run that by your professor yet?

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline coltonoscopy

Junior Member


Medals: 2



« Reply #63 - Posted 2012-08-11 04:03:57 »

The main point I am making is that you cannot say that ArrayList is best for all situations involving games, which is what was said.  And I totally agree that O notation does not help when dealing with smaller sets.  Every situation needs to have the correct collector picked out.  It could be that it is ArrayList, but it could be that it is something else.  Good unit testing with swappable collectors so you can test out the one that suites you.
I don't think anyone ever said ArrayList is best for all situations involving games. It's been consistently conveyed that we're still talking about the matter at hand and matters similar to such. Clearly, data structures aside from the ArrayList wouldn't exist if ArrayList were the be-all, end-all. It seems, on the contrary, that your point this entire time has been that performance is in direct correlation with a structure's big-O function and that this, rather, has been in dispute.

Straight flippin.
Offline coltonoscopy

Junior Member


Medals: 2



« Reply #64 - Posted 2012-08-11 04:04:31 »

Did you run that by your professor yet?
Perfection.

Straight flippin.
Offline jmart

Junior Member


Medals: 1



« Reply #65 - Posted 2012-08-11 04:16:01 »

I don't think anyone ever said ArrayList is best for all situations involving games.
Quote
No-one uses HashSet for this operation because the only properties of HashSet which we want - the enforced uniqueness and fast lookup time - come at a rather large cost compared to simply using ArrayList in a particular way, and that particular way just happens to be exactly how you'd use it to write a game. If we're looking at pure performance from memory and typical usage, ArrayList totally wins, every time.

That's what I was referring to.
Offline coltonoscopy

Junior Member


Medals: 2



« Reply #66 - Posted 2012-08-11 04:25:25 »

Quote
No-one uses HashSet for this operation

I think you may have misinterpreted what the poster was trying to say in the first place. With that specified in the post from the beginning, then when he mentioned ArrayList winning every time, it was every time for an operation like that one. Otherwise, he would have just said nobody uses HashSet, period, wouldn't he?

Straight flippin.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 742
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #67 - Posted 2012-08-11 06:39:47 »

I do appreciate you're trying to 'play the miscommunication card', instead of hoping the thread dies, but could you maybe explain to us what the misconception was here?

Quote from: Riven
Big O notation tells you absolutely nothing about performance

Dude that is awesome.  Wait till I tell my old Data Structures And Algorithm professor about this one.  Let the tests peak for themself... oh wait you already disregarded that test should not count either.  So throw away establish O notation that is backed by math and lets throw away tests.  We are then left with religion.  Is this a religion board or a computer science board.

I'd love to get that out of the way.

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

Junior Member


Medals: 2



« Reply #68 - Posted 2012-08-11 07:00:04 »

Well, he has to find time to go talk to his professor first. We'll probably have an answer by Monday.

Straight flippin.
Offline Roquen
« Reply #69 - Posted 2012-08-11 07:02:42 »

As an exercise try to come up with a rule to dictate when to use hashing vs. a binary tree.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline ctomni231

JGO Wizard


Medals: 98
Projects: 1
Exp: 7 years


Not a glitch. Just have a lil' pixelexia...


« Reply #70 - Posted 2012-08-11 14:45:13 »

Big O debate, this has existed for way too long. I think the true fact is that O(n) can't be compared to O(1).

It truly depends on what you are using an ArrayList for and what you are using a HashMap for. Since we are on a gaming forum, HashMap is probably going to lose the debate because we do not use collections over 1000 when designing games. It may sound gruff, but there are no benchmarks that will work for these test cases at all.

O(1) works better when [numbers approach infinity]
O(n) works better when [numbers approach 0]

The point where this evens out is not definitely not in the 1000's but probably higher. It fully depends on processor, technology used, etc. All that has to be said, is that it is a pointless debate since games are always trying to use small numbers. Making a double array is going to be a lot faster than making a HashSet... because you'll never get up to those high numbers to make HashSet useful. If by some chance you are using 1 billion images, then just change to HashSet. I really don't understand the debate.


Offline Roquen
« Reply #71 - Posted 2012-08-11 14:57:55 »

Here's the deal...the answer is always: "it depends".
Offline ctomni231

JGO Wizard


Medals: 98
Projects: 1
Exp: 7 years


Not a glitch. Just have a lil' pixelexia...


« Reply #72 - Posted 2012-08-11 15:00:02 »

Yeah, and it always forms pointless debates. This was one of the most argued gaming discussions when I used to do C++. Some things never change when you move from one language to another.  Tongue

Offline Best Username Ever

Junior Member





« Reply #73 - Posted 2012-08-11 18:16:04 »

I made a program to test the performance of different data structures that I think emulates the original poster's scenario. I threw something together too quickly to feel comfortable calling it a benchmark program, but I based it on personal experience with designing a platform game. Higher numbers are better; they're the number of objects processed in 60 seconds. Divide by 10 to get the number of "game loops" then by 60 to get the number of loops per second.

Test 1Test 2Test 3Test 4
Bag74166390741635407499835075218570
LinkedList71159380717956107181015071767130
ArrayList A44054120439369604371561043704460
ArrayList B41636000415450204141278041479300
HashSet47564890474523404806361047849390
TreeSet47799480479149104808620048086320
ArrayList C7595190759224076525007655840

The Bag, LinkedList, ArrayList A, HashSet, and TreeSet tests were all executed the same way. Elements were removed through each class's Iterator's remove() method not the main class's remove(o) method. ArrayList B was done with princec's method of copying surviving [ obstacles ] (my test might not be appropriate for particles) into a second ArrayList, clearing the first, and swapping the two. The last test was similar to the ArrayList B test but used retainAll instead of copying. I originally did it as a sanity check because ArrayList B seemed way too slow. Yesterday it seemed like it was faster than both Bag and LinkedList and really threw me because I did not notice it was an order of magnitude slower. You can ignore it. Cool I thought ArrayList B would at least be faster than ArrayList A and HashSet.

I will change a few things later, but for now you can scrutinize Exploder.java, ExploderFactory.java, and LinkedListTest.java
Offline Roquen
« Reply #74 - Posted 2012-08-11 21:40:02 »

@ctomni231: But it's not pointless.  Until someone reaches the point of proper critical thinking combined with an understanding of architectures and data structures they're stuck blindly flaying in the dark.  (Near) Optimally choosing a method requires an understand a given use-case's frequency of queries, temporal access patterns, etc. etc.
Offline ctomni231

JGO Wizard


Medals: 98
Projects: 1
Exp: 7 years


Not a glitch. Just have a lil' pixelexia...


« Reply #75 - Posted 2012-08-11 22:10:11 »

@Rouqen: I have no idea how we'd measure someone's knowledge of data structures vs. critical thinking, but...

Everything you say varies from system to system. Even though you may think that there might be a clear cut solution now, you can test your pattern on System A and you'll get result A. You'll test your same case on system B and get result B. Funny thing is Result A and Result B can be wildly different.

I hate to say it, but this whole debate has and will be going on for years. Optimization of code is a huge time sink. Using ArrayList vs. Hashmap really comes down to a case by case basis. It makes it very difficult to debate properly, because there is definitely no correct answer. That just leaves everyone debating this point "flaying in the dark". Sounds kinda pointless.

Offline Roquen
« Reply #76 - Posted 2012-08-11 23:11:23 »

If one never asks oneself "why" they do this or that...there's certain that they're not engaging in enough critical thinking.  Conversely if they can't make decisions there's a chance that they are wasting too much time question themselves.  WRT: data structures, it's pretty easy to figure out if someone has a working base knowledge or not.  Now I agree that things vary system to system...but I'm not sure exactly what you mean by "system" here because it sounds like you're talking about architecture BTW.  My whole point is that the "best" answer to pretty much any question in CS (without a ton of information) is "it depends".

Ultimately there is no debate, as I've repeated brought up "splay trees".  If one were to go by limit based analysis nobody would ever use this data-structure and yet it is very very useful.

The real danger here is placing artificial limits on ones capabilities by blindly following rules which are not universally true.  And in the end has really has nothing to do with that dirty word "optimization".
Offline ctomni231

JGO Wizard


Medals: 98
Projects: 1
Exp: 7 years


Not a glitch. Just have a lil' pixelexia...


« Reply #77 - Posted 2012-08-11 23:22:19 »

Quote
The real danger here is placing artificial limits on ones capabilities by blindly following rules which are not universally true.

This. And by "system", I am talking about system architecture (computer specifications) as well as programming languages (Java, C++, Python, Cobol). It is all bundled under system.

Offline Klems

Junior Member


Medals: 5
Projects: 1



« Reply #78 - Posted 2012-08-12 00:48:47 »

Clean code should be the main priority. The first rule of optimisation is "don't optimise if you don't have to".
But if you can optimise on the fly (using a LinkedList for an "Updatable" List for instance) without writing more code, what's the point of not doing it ?

I used a LinkedList for my Updatable List because that's probably faster than a single ArrayList (I remove a lot of Updatable entities and the list can get pretty heavy at times).
Two ArrayList are probably faster than a single LinkedList. But my code run fairly fast for the moment, why would I should optimise it now ? Premature optimisation may cause bugs, and in this case lead to ugly/verbose code.
I don't think data structures are really that important. In this exemple, how many FPS do you think we could gain by using two ArrayList ? Do we REALLY need to write the code (potentially more bugs and more loc) with two ArrayList ?
Though I'm not sure about this, I should write a benchmark.

You have to figure out where the real speed bottlenecks are. If you are writing a particle engine, chance are you could double the FPS by sorting the Renderable List using Textures to avoid unnecessary bindings.


You could write your own ArrayList implementation with a faster O(1) remove method (switch with the last element and decrement the size). In my case I don't care about the order.
Also I heard somewhere that using a for loop with an int and the get method is A LOT faster than using the iterator of an ArrayList. I didn't tested it but it could help some people here.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 742
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #79 - Posted 2012-08-12 01:24:29 »

Hm. First you say that the point is code quality, not speed, and you should only optimize bottlenecks, and then you start giving advice on using data structures that you haven't even worked with or benchmarked yet...

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

Junior Member


Medals: 5
Projects: 1



« Reply #80 - Posted 2012-08-12 01:40:50 »

Hm. First you say that the point is code quality, not speed, and you should only optimize bottlenecks, and then you start giving advice on using data structures that you haven't even worked with or benchmarked yet...
Because the point IS code quality, and because I haven't run on speed problems by now ?
If you really have to optimize speed, you should do your own test and check where the bottlenecks are. Because the data structure for your updatable list is probably not the cause: nobody gain 20 FPS by switching his LinkedList with two ArrayList.
But sure, it probably help if you want to run your game on a lower end PC.

As a matter of fact I did my own benchmark on this matter. Most of the time, the gain between using an ArrayList and a LinkedList is negligible. Even with a simple iteration (296 ArrayList / 315 LinkedList), which I just tested right now.
And by negligible I mean negligible on a modern PC, don't get me wrong.

What I haven't benchmarked yet is the potential speed gain of using a LinkedList to remove objects during the iteration.
I think the gain is so negligible I should'nt bother with it at all. Athough that's just a theory, as I said I should write a benchmark to be REALLY sure about it.
Offline princec

JGO Kernel


Medals: 341
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #81 - Posted 2012-08-13 00:43:44 »

Another tangent! Code quality doesn't mean diddly squat. Shipping games is what's important. The qualities I admire most in code is that it works and I can move on to the next thing to get the game out the door.

Not everyone's using a modern PC btw. There's a lot of people monkeying around in Android and let me tell it to you in no uncertain terms, you do not want to use LinkedLists. Or HashSets. Or even, really, iterators, I suspect.

Cas Smiley

Offline princec

JGO Kernel


Medals: 341
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #82 - Posted 2012-08-13 00:51:35 »

nobody gain 20 FPS by switching his LinkedList with two ArrayList.
Just to reiterate, not every place Java is running is a powerful desktop computer. Also raw throughput is not always the only goal. One reason I developed various techniques in games was because I was doing realtime television graphics and we couldn't allow a single frame drop. This of course means absolutely minimising garbage and LinkedLists make rather a lot of it. I still use these techniques today because I want rock solid framerates in my games. The number of people I see posting in Java game related threads about stuttering and juddering animation...

Cas Smiley

Offline Klems

Junior Member


Medals: 5
Projects: 1



« Reply #83 - Posted 2012-08-13 01:58:03 »

Another tangent! Code quality doesn't mean diddly squat. Shipping games is what's important. The qualities I admire most in code is that it works and I can move on to the next thing to get the game out the door.
I agree with you. I try to write the simplest code possible without sacrificing speed.
But writing a new List implementation for an Updatable List require time, and I'm probably not going to get it perfectly at the first try. You may be able to do it on the fly, but that's not my case. That's extra work I could put on something with a higher priority.

I write simple code. Simple code is easy. Why should I want to make it more complex ? Dumb code = good code.
As long as dumb doesn't mean slow.
Offline DrewLols

Senior Member


Medals: 1
Projects: 1


Noob going through metamorphosis...


« Reply #84 - Posted 2012-08-23 02:57:16 »

Well well well...  Did I mention well?  This thread seems to have taken on a life of its own.  Yeah, so I'll be using a plain ol' ArrayList unless I find that the cpu is being murderd.  Haven't really seen cpu usage go above 17%.  I can always just assume I'll be using SOME sort of list and will be able to easily change it in the future.

1  
2  
3  
4  
5  
List<Zippittydooda> zippittydoodas = new ArrayList<Zippittydooda>();
for(Zippitydooda day : zippittydoodas)
{
    day.lolwut();
}


Yeah...  That'll work out just fine!

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

Senior Member


Medals: 1


Lazy Middle Class Intellectual


« Reply #85 - Posted 2012-08-23 07:47:14 »

I just want to stop in and say that this thread is freaking AWESOME.

And for the rest of the people new to the thread that don't want to read all the awesomeness, the answer to the original question is ArrayList.

Sacramento Volleyball
"Whitty phrase goes here."
Offline 65K
« Reply #86 - Posted 2012-08-23 07:56:01 »

1  
2  
3  
4  
5  
List<Zippittydooda> zippittydoodas = new ArrayList<Zippittydooda>();
for(Zippitydooda day : zippittydoodas)
{
    day.lolwut();
}


Yeah...  That'll work out just fine!
It works.... but if using ArrayList for whatever reason, take the consequential step and don't use enhanced loops with its implicit iterator crap.

Offline Cero
« Reply #87 - Posted 2012-08-23 09:07:29 »

Actually lately I try to use Libgdx' Array Class, they claim its like ArrayList but with less garbage.

Offline princec

JGO Kernel


Medals: 341
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #88 - Posted 2012-08-23 10:36:09 »

Iterator garbage is miniscule to be honest, not something you should worry about on the desktop. It does come with a 10% performance penalty though.

Cas Smiley

Offline sproingie

JGO Kernel


Medals: 201



« Reply #89 - Posted 2012-08-23 18:06:42 »

Oh noez, a SINGLE garbage item.  Better crap up the entire program with clunky inflexible syntax and off-by-one errors to save a few bytes!

And on Android at least, they give the opposite advice: http://developer.android.com/guide/practices/performance.html (search down for "enhanced for loop")
Pages: 1 2 [3] 4 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.

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

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

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

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

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

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

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

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

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

Riven (50 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!