Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (524)
Games in Android Showcase (127)
games submitted by our members
Games in WIP (593)
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 14803 times)
0 Members and 1 Guest are viewing this topic.
Offline coltonoscopy

Junior Devvie


Medals: 2



« Reply #30 - Posted 2012-08-10 06:23:14 »

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(...) .


See Riven, now you're just losing me; I'm still a fledgling! XD

I understand why you wrote the equals method now, and it's clear that things go on under the hood that derive from Object that I wasn't previously aware of (though I have seen equals() and hashCode() before in other programs). Was my reasoning regarding the HashSet reasonable though, or is there something else that I'm missing? It seems impractical--if not impossible--to me given that whatever objects are passed into it are implemented with equals and hashCode. By the way, thanks for taking the time to teach me a few things! Cheesy

Colton

Straight flippin.
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #31 - Posted 2012-08-10 06:27:22 »

The first part was serious (and it indeed adds a burden to developers... adding those methods to every class that will ever have instances of it in a HashSet / HashMap Lips Sealed)

The second part was a bad joke, sorry.

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

Junior Devvie


Medals: 2



« Reply #32 - Posted 2012-08-10 06:34:01 »

The first part was serious (and it indeed adds a burden to developers... adding those methods to every class that will ever have instances of it in a HashSet / HashMap Lips Sealed)

The second part was a bad joke, sorry.
Oh, now what you're saying makes sense. Whoops! Yeah, that's a rather seeming design flaw. Luckily, I don't work with them very often, and when I do, I find I'm using it in an application where I don't have to worry about things like that (a recent example is a map of tiles to characters for my level save system, which maps tile types to Unicode characters that get outputted into a file).

I also get your joke now... very funny  Wink It's times like these when you wish you could hear someone's vocal intonation! Cheesy

Best regards,
Colton

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

« JGO Spiffy Duke »


Medals: 422
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #33 - Posted 2012-08-10 08:46:43 »

Those clowns are attracting the zombies!

More seriously:

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. Besides, again in typical usage in a game, you almost always want the order of the elements added into the collection to remain fixed, for various reasons that will become apparent to you eventually, and therefore you'd want to use a LinkedHashSet if you were dead set on using a Set implementation.

Cas Smiley

Offline Roquen
« Reply #34 - Posted 2012-08-10 10:10:02 »

Note that Big O notation doesn't take alot of real-world stuff into account.
Offline jmart

Junior Devvie


Medals: 1



« Reply #35 - Posted 2012-08-10 17:00:29 »

princec,

I disagree.  There are many ways in which collections can be used in a game.  To imply that ArrayList is the best and only way is just way wrong.

Are you going to tell me that if I have a bunch of objects reporting that they can be removed and then removing them from a collection is better implemented with an ArrayList (with its O(n) search) is better than HashMap/Set (with its O(1)) search?

There are drawbacks to ArrayList, like removing and searching and adding to a full list.  The big benefit ArrayList is its fast indexing.  I am actually a big fan of LinkedHashSet and LinkedHashMap, as they act like Hash's but keep their objects ordered.

*Thanks to the person who corrected me when I wrote O(logn) search time for Hash in previous post
thanks
jose
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #36 - Posted 2012-08-10 17:18:25 »

Note that Big O notation doesn't take alot of real-world stuff into account.
Surely it does, however, people easily mistake Big O notation for something that gives an indication of performance. It's about performance degradation for a growing data set.

O(n2) could easily outperform O(1) for a data set smaller than 1 billion, in which case the algorithm featuring O(1) is barely usable for any real world problem.



Are you going to tell me that if I have a bunch of objects reporting that they can be removed and then removing them from a collection is better implemented with an ArrayList (with its O(n) search) is better than HashMap/Set (with its O(1)) search?
Yes. Big O notation tells you nothing about absolute performance.

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

Junior Devvie


Medals: 1



« Reply #37 - Posted 2012-08-10 17:28:40 »

Ok so lets write up some code and test this out then.  Instead of all of us arguing lets all of us work together here and figure this stuff out.  That way we all leave smarter, happier, and agreeing on the test results.   Smiley

I will take a crack at writing up a test or two... not to prove anyone's point but to get to bottom of which collection is good for what circumstances.


thanks
jose
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #38 - Posted 2012-08-10 17:47:12 »

There is no way to benchmark this. You can write two different benchmarks and have two different winners.

The point I was making is that you shouldn't look at the Big O notation the way you did. You should pick the algorithm that bests suits your needs (performance wise or maintainability wise). Don't let the 'performance degradation under growth' determine what you're going to use, unless you experience performance issues for bigger data sets.

The reverse is also true, don't always pick the fastest algorithm, because it's probably not your bottleneck in the first place.

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

Junior Devvie


Medals: 1



« Reply #39 - Posted 2012-08-10 17:50:22 »

The problem is that in this case we are talking about Collections, which have the same/similar interface.  That means the maintaiability it damn near the same.  If you do not go by big-o then please elaborate?


thanks
jose
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen
« Reply #40 - Posted 2012-08-10 17:56:03 »

@Riven - that's what I meant said better.

@Whomever else:
Classic example is a splay tree.
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #41 - Posted 2012-08-10 18:08:03 »

@Riven - that's what I meant said better.
I know I don't have to explain it to you Smiley

I was indeed trying to clarify it for jmart.

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

« JGO Spiffy Duke »


Medals: 422
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #42 - Posted 2012-08-10 18:14:16 »

The problem is that in this case we are talking about Collections, which have the same/similar interface.  That means the maintaiability it damn near the same.  If you do not go by big-o then please elaborate?
Experience usually trumps big O; you can disagree with me but it won't make you right Smiley

If you're writing a game - which is what I do all day long for a living - you are almost absolutely guaranteed to get the best performance from an ArrayList if you're using it to store thousands of things that need twiddling every frame. You'll use less memory, and it'll be considerably faster than any other solution. By all means use a LinkedHashSet if you want to complicate things for yourself and make it slower and use more memory. Although realistically memory isn't exactly an issue for most people and neither is performance on the desktop.

To recap:

Use a pair of ArrayLists. Scan sequentially to update each item. Then copy any item that is still "alive" into the second ArrayList. Swap. This is absolutely one of the fastest things you can do on a modern CPU.

Cas Smiley

Offline Roquen
« Reply #43 - Posted 2012-08-10 18:16:19 »

@Riven - yeah I figured...my replies are generalized to everyone
@Cas - indeed.
Offline jmart

Junior Devvie


Medals: 1



« Reply #44 - Posted 2012-08-10 18:26:41 »

The problem is that you are not really backing it up.  You are just repeating yourself as if by repeating it you are increasing its truthiness.  I am backing my statements up by facts, a search on a HashSet is O(1) and a search on ArrayList if O(n).  I mean you really can't get passed that.  Here is another truth, if your ArrayList if full and you add one more spawned object to it, it will result in the whole ArrayList being copied.  These are facts.  Here is another fact, if you remove an object from an ArrayList that happens to not be the last object, then the objects need to get moved to their correct new locations.  These facts do not go away.  Call backs, aka notification over polling, has been proven to be a good approach in computer science many many years ago.... these are facts.  If you are doing call backs, already proven to be better then polling, then you need a search algorithm that is fast, hence hashing make a lot of sense here because it is O(1).  Saying, listen i know on paper these things you are saying are right but you still have to take my word for it does not make it true.

just saying
Offline princec

« JGO Spiffy Duke »


Medals: 422
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #45 - Posted 2012-08-10 18:27:19 »

As a random aside so far in my computer games career I've only found two places where the actual data structure and algorithm has had a measurable effect on performance:

1. Deep in the heart of the SpriteEngine there's a radix sort algorithm that sorts the sprites on about 5 or 6 variables each. Using a Comparator and the built-in Collections sort (tweaked quicksort?) was an order of magnitude slower.

2. The A* pathfinder in Droid Assault and Revenge of the Titans used a very fast integer BinaryHeap implementation (by @pjt33 of these parts I think). I tried using a few more general structures which were way too slow or generated far too much garbage. Also I ended up using a boolean grid for the closed list rather than the more usual Set approach because, again, a grid with random access is vastly faster than any implementation of Set.

Every other optimisation based on the choice of using raw arrays, ArrayLists, HashSets, LinkedHashSets, etc. has really just been lost in the general noise. Of course if you meticulously optimise everything you gain a few FPS, or in my case, allow the game to run full speed on a computer that's on average 2 months older than Joe Average's computer.

Cas Smiley

Offline princec

« JGO Spiffy Duke »


Medals: 422
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #46 - Posted 2012-08-10 18:29:48 »

The problem is that you are not really backing it up.  You are just repeating yourself as if by repeating it you are increasing its truthiness.  I am backing my statements up by facts, a search on a HashSet is O(1) and a search on ArrayList if O(n).  I mean you really can't get passed that.  Here is another truth, if your ArrayList if full and you add one more spawned object to it, it will result in the whole ArrayList being copied.  These are facts.  Here is another fact, if you remove an object from an ArrayList that happens to not be the last object, then the objects need to get moved to their correct new locations.  These facts do not go away.  Call backs, aka notification over polling, has been proven to be a good approach in computer science many many years ago.... these are facts.  If you are doing call backs, already proven to be better then polling, then you need a search algorithm that is fast, hence hashing make a lot of sense here because it is O(1).  Saying, listen i know on paper these things you are saying are right but you still have to take my word for it does not make it true.
Haha, these may be facts, but they are not figures. The figures are:

A pair of ArrayLists used this way is approximately 5x faster than a LinkedList, and uses something like a quarter of the RAM. There you go.

Cas Smiley

Offline Roquen
« Reply #47 - Posted 2012-08-10 18:34:05 »

As I noted earlier:  splay tree.  Going by Big-O notation you'd never use a splay tree.  In the real world a splay tree can smoke a hashtable (regardless of n).  The specific case depends on temporal access patterns.  splay tree search is log(n) on average and worst case 'n'. vs. hashing's '1'.

Also in the real world programming it's important to remember what X (don't remember whom) said: "All those fancy algorithms are slow when 'n' is small...and it's usually small".
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #48 - Posted 2012-08-10 18:34:39 »

I am backing my statements up by facts, a search on a HashSet is O(1) and a search on ArrayList if O(n).  I mean you really can't get passed that.
We can't get past that indeed.

You are just repeating yourself as if by repeating it you are increasing its truthiness.
We are repeating it, because you as of yet failed to grasp that Big O notation tells you absolutely nothing about performance.

I'm not going repeat myself, but I'll simply refer to the reply I made earlier.

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

Junior Devvie


Medals: 1



« Reply #49 - Posted 2012-08-10 18:35:00 »

Well LinkedList didnt come up but here is a scenario in which LinkedList is better.

Lets say you have to insert into the back of a queue, e.g. list[0].  In ArrayList this would take O(n), but in LinkedList its O91).  Another pesky fact.  The bottom line you cannot blindly use ArrayList for everything as is being suggested.  You have to take a look.  If you collections are being used specifically for certain things, then should be able to hit O(1).
Offline jmart

Junior Devvie


Medals: 1



« Reply #50 - Posted 2012-08-10 18:38:33 »

Quote
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.
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #51 - Posted 2012-08-10 18:41:07 »

Big O notation tells you absolutely nothing about performance
Big O notation tells you absolutely everything about performance degradation under growth

If your professor disagrees, he's misinformed.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Roquen
« Reply #52 - Posted 2012-08-10 18:50:43 »

Let me repeat myself:  SPLAY TREE.  Do some web searching and compare Big-O notations vs. competing data-structures.  (Of course this is merely 'an' example)
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #53 - Posted 2012-08-10 18:51:29 »

Example: say I want to bring a bunch of physical boxes to Iceland, and as I live in The Netherlands, that might take me a few days by my nifty speedboat. The boat is tiny, so I can only bring 1 box at a time.

What is this in Big O notation?
   Shipping 1 box: 5 days
   Shipping 2 boxes: 10 days
   Shipping 3 boxes: 15 days
   Shipping n boxes: 5*n days
Answer: O(n)



Now let's assume I have this huge ship, that will have room for all the boxes I'd ever want to ship to Iceland. It will take 80 days, but I'd bring it all in 1 shipment.

What is this in Big O notation?
   Shipping 1 box: 80 days
   Shipping 2 boxes: 80 days
   Shipping 3 boxes: 80 days
   Shipping n boxes: 80 days
Answer: O(1)


Guess what I'll pick for my shipment of a few boxes? O(n) beats O(1) for that data size!
Guess what I'll pick for my shipment of many boxes? O(1) beats O(n) for that data size!

Hence: Big O notation tells you nothing about performance.

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

JGO Kernel


Medals: 202



« Reply #54 - Posted 2012-08-10 19:24:17 »

Y'all do realize that algorithmic analysis goes a little deeper than one single notation, and covers upper and lower bounds too?

But I am getting a laugh out of all these categorical statements like "It tells you nothing! nothing!"



Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #55 - Posted 2012-08-10 19:34:31 »

Sure, but we were discussing Big-O notation, not algorithmic analysis in general Smiley

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Roquen
« Reply #56 - Posted 2012-08-10 19:36:22 »

@sproingie: Sure. But you have to know the something about the data, access patterns and size.  It's basically an indicator of sanity and not a razor.  Average case may have little meaning if your data isn't random.  Worst case will have no meaning if it impossible to fall into worst case.  But you know all of this. (Again the person I'm responding to may not be whom I'm speaking to).  When I first started to really grok this stuff is after I wrote a custom sort for a (smallish) 'n'.  It beat the crap out of all the standard methods I tried and when I analysed it I was shocked to discover that it was worst case O(n3).  Of course the trick is that the data patterns were insured it to never be worst case.
Offline Jimmt
« League of Dukes »

JGO Kernel


Medals: 138
Projects: 4
Exp: 3 years



« Reply #57 - Posted 2012-08-10 20:15:56 »

mm. True Big O notation doesn't say anything about likeliness of best/worst case scenarios.
Offline princec

« JGO Spiffy Duke »


Medals: 422
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #58 - Posted 2012-08-10 22:13:38 »

Quote
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.
It is neither... it's an exchange of empirical results board. You write your sprite engine using LinkedLists and I'll stick to ArrayList. I'll get twice as many sprites on screen as you.

What your Algorithms and Data Structures professor seems to have forgotten to tell you is that you can't compare two algorithms using Big O notation. You cannot say O(n) is faster than O(1) or that O(n log n) is faster than O(n2). As Riven is trying to tell you, Big O can only tell you how a particular algorithm will degrade as n increases -- not relatively how fast it is compared to a different algorithm. Spoonfeed: an algorithm that executes in O(n2) but is 10,000 times faster than an algorithm that executes in O(n) can comfortably outperform it until n becomes rather large. If it turns out n is not going to be large - and it won't be - well you get my drift.

So: ArrayList is 5 times faster, in actual use, than LinkedList. Write a benchmark and prove it to yourself!

Cas Smiley

Offline Best Username Ever

Junior Devvie





« Reply #59 - Posted 2012-08-10 23:12:05 »

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(...) .

I absolutely agree with you on hashCode and equals. I'm not really a fan of compareTo either. I would rather have a standard where compare(a, b) equals(a,b) and hashcode(a) are implemented in a separate object. But I don't agree with you on your method of comparing clowns. Its so much more useful to keep the default behavior in most cases. As a rule I only override the equals or hashCode functions if and only if I'm working with an immutable type. It's fine to leave hashcode and equals for elements of Java Collections. It's only when you implement Collection and use == or an objects identity hash that the interface's contract is considered broken. (But don't ask me why it's considered "correct" to ignore compareTo if you supply a Comparator. Where is the HashCoderator class?)

Use a pair of ArrayLists. Scan sequentially to update each item. Then copy any item that is still "alive" into the second ArrayList. Swap. This is absolutely one of the fastest things you can do on a modern CPU.

Cas Smiley

My method can be done using minimal reads and writes, uses half the space, and probably has similar memory cache properties. It's not an implementation of a List but no one explained why you would restrict yourself to using a List given the first poster's requirements.
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.

toopeicgaming1999 (38 views)
2014-11-26 15:22:04

toopeicgaming1999 (33 views)
2014-11-26 15:20:36

toopeicgaming1999 (8 views)
2014-11-26 15:20:08

SHC (24 views)
2014-11-25 12:00:59

SHC (24 views)
2014-11-25 11:53:45

Norakomi (25 views)
2014-11-25 11:26:43

Gibbo3771 (23 views)
2014-11-24 19:59:16

trollwarrior1 (36 views)
2014-11-22 12:13:56

xFryIx (75 views)
2014-11-13 12:34:49

digdugdiggy (52 views)
2014-11-12 21:11:50
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
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!