Java-Gaming.org    
Featured games (78)
games approved by the League of Dukes
Games in Showcase (428)
Games in Android Showcase (89)
games submitted by our members
Games in WIP (466)
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  
  Choosing the right collection  (Read 3333 times)
0 Members and 1 Guest are viewing this topic.
Offline Sanxion

Junior Member




Java games rock!


« Posted 2002-10-28 07:02:18 »

I'm storing my server events in Frame objects. Each frame is assigned a number and is stored in a hashtable where the number is the key and the Frame is the object. My Scheduler keeps track of current frame and gets it from the hashtable if the key exists. Basically I would only have to look at the first object in the collection if it were sorted. I'm not sure what collection I should be using. Is hashtable a good choice?
Offline rabbit

Innocent Bystander




Java games rock!


« Reply #1 - Posted 2002-10-28 09:12:29 »

Look at the  "Java Optimisations" book available at http://java.sun.com

There is a review of Collections, which are benchmarked according to  their usage.

A quick reference :

Class             Add             Iterate             Random             Remove

ArrayList             0 ms       660 ms             0 ms             2,360 ms
LinkedList       50 ms       1,100 ms             26,800 ms       0 ms
Vector             0 ms       880 ms             0 ms             2,580 ms
TreeSet             330 ms       1,430 ms             N/A                   60 ms
HashSet             110 ms       1,430 ms             N/A                   50 ms

A quote from the book :

"These results illustrate how important the selection of algorithms and data structures can be. Look at the results from the different List implementations. ArrayList and Vector, two similar classes that are both array-based structures, show similar performance characteristics. Since Vector provides synchronization by default, it's slightly slower. If you compare the ArrayList and LinkedList results, however, you'll see that they have very different performance characteristics. While these two structures are capable of performing the same operations, operations that are practically free on the ArrayList are very costly with the LinkedList and vice-versa. The results also show how the set-based structures have very different performance characteristics from the list-based structures. "

I hope it could help you !

- Rabbit -

[ Note for french people : i've made a translation of this book. I can not yet distribute it, but i'm working on it ]

Offline pepe

Junior Member




Nothing unreal exists


« Reply #2 - Posted 2002-10-28 12:36:58 »

Beware of these timings. They do not take in account the extra work that can happen sometimes and take some time (ArrayList that needs to alocate a new array, hash tables that need rehashing, ....)
Keep in mind that these classes don't have a predictible timing. There are also some tweaking of creation parameters that can slow down or accelerate depending on the use that is done of the classes. A method said to be fast can be very slow if used in wrong way. (for example setting increment size too low for an ArrayList)

Home page: http://frederic.barachant.com
------------------------------------------------------
GoSub: java2D gamechmark http://frederic.barachant.com/GoSub/GoSub.jnlp
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Jeff

JGO Coder




Got any cats?


« Reply #3 - Posted 2002-10-28 17:08:03 »

While its true that any direct emasurementsa re VM and implementatiion specidifc, there are some genralities you can make that hold true for the fundemental datastures.

For instance, scanning through an ArrayList shoudl always be faster then scanning through a linked list but insertions (and liekly deletions) will be faster ina linked list.

Trees are a good all around compromise structure and are good for searches, though both arrays and linked lists beat them out in their own best-performance areas.

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline Sanxion

Junior Member




Java games rock!


« Reply #4 - Posted 2002-10-30 10:29:56 »

Okay this got me thinking. Is it faster to Iterate through an ArrayList of objects and examine a variable (key) to find the object I'm looking for, than use a hashtable where the key is stored in the collection.
Offline Orangy Tang

JGO Kernel


Medals: 51
Projects: 11


Monkey for a head


« Reply #5 - Posted 2002-10-30 11:13:57 »

Probably only if your list is pretty small, or if you've got a shzit-load of collisions in your hash.. Remember that removal from random places in an arrayList is pretty slow if you want to maintain the ordering...

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

Junior Member





« Reply #6 - Posted 2002-11-06 10:14:43 »

What is the range of numbers?
Is insertion order related to retrieve order in any way (like first in first out or whatever)?
Keeping a structure sorted will _usually_ be more expensive than inserting in/deleting from a Hastable. Or do you have to test several keys to retrieve the correct key?
Offline Jeff

JGO Coder




Got any cats?


« Reply #7 - Posted 2002-11-07 20:52:48 »

Everyone else is giving you pretty good advice. My only addition is this...

If performacne is your issue you almost never want to iterate through an array looking for something unelss it is evry very small.  If you keep it sorted 9)which does cost) thre are much faster search algorithms then linear search.  A binary chop is, AIR, on the average twice as fast as a linear scan.  A proportional chop is even faster.

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
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.

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

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

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

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

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

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

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

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

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

CJLetsGame (221 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!