By all means use any collection you like. But the ArrayList method is fastest and uses least memory.
Cas 
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.
Did you run that by your professor yet?
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.
Perfection.
[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.
[/quote]
That’s what I was referring to.
[quote]No-one uses HashSet for this operation
[/quote]
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?
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=“jmart,post:51,topic:39437”]
I’d love to get that out of the way.
Well, he has to find time to go talk to his professor first. We’ll probably have an answer by Monday.
As an exercise try to come up with a rule to dictate when to use hashing vs. a binary tree.
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.
Here’s the deal…the answer is always: “it depends”.
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. 
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.
[tr][td][/td][td]Test 1[/td][td]Test 2[/td][td]Test 3[/td][td]Test 4[/td][/tr]
[tr][td]Bag[/td] [td]74166390[/td] [td]74163540[/td] [td]74998350[/td] [td]75218570[/td] [/tr]
[tr][td]LinkedList[/td] [td]71159380[/td] [td]71795610[/td] [td]71810150[/td] [td]71767130[/td] [/tr]
[tr][td]ArrayList A[/td] [td]44054120[/td] [td]43936960[/td] [td]43715610[/td] [td]43704460[/td] [/tr]
[tr][td]ArrayList B[/td] [td]41636000[/td] [td]41545020[/td] [td]41412780[/td] [td]41479300[/td] [/tr]
[tr][td]HashSet[/td] [td]47564890[/td] [td]47452340[/td] [td]48063610[/td] [td]47849390[/td] [/tr]
[tr][td]TreeSet[/td] [td]47799480[/td] [td]47914910[/td] [td]48086200[/td] [td]48086320[/td] [/tr]
[tr][td]ArrayList C[/td] [td]7595190[/td] [td]7592240[/td] [td]7652500[/td] [td]7655840[/td] [/tr]
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. 8) 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
@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.
@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.
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”.
[quote]The real danger here is placing artificial limits on ones capabilities by blindly following rules which are not universally true.
[/quote]
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.
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.
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…