Java-Gaming.org Hi !
Featured games (81)
games approved by the League of Dukes
Games in Showcase (513)
Games in Android Showcase (119)
games submitted by our members
Games in WIP (577)
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  
  which collection to use?  (Read 5397 times)
0 Members and 1 Guest are viewing this topic.
Offline V

Senior Newbie





« Posted 2006-01-14 10:00:14 »

hey there Smiley

The game I'm working on heavily depends on non-incremental numbers associated with objects (for many different purposes), and I can't find a good type of collection for this. ArrayList, Vector and LinkedList all depend on incremental indices, all other collections associate Objects with Objects. Right now I'm using HashMap<Integer, Object>, but I guess that's far from being the optimal solution.

Is there any int -> Object collection implementation which I simply overlooked? If that's not the case, is HashMap<Integer, Object> a good enough solution or should I write my own collection for this purpose?
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 816
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #1 - Posted 2006-01-14 11:00:15 »

You might be interested in the IntHashMap class in one of the Apache projects.

org.apache.commons.lang.IntHashMap

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

Junior Duke


Exp: 15 years


I love YaBB 1G - SP1!


« Reply #2 - Posted 2006-01-14 12:23:51 »

Or you might take a look at the pcj ( http://pcj.sourceforge.net/ ) library and the IntKeyMap subclasses, which offer what you need.
Alternatively the apache commons primitive (http://jakarta.apache.org/commons/primitives/) might help. But I found that it's always lacking the specific collection I needed (in your case there seems to be no HashMap).

@Riven: I couldn't find IntHashMap in the current apache.commons.lang API docs. Can you post a link?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline tom
« Reply #3 - Posted 2006-01-14 12:34:40 »

I think HashMap<Integer, Object> is good enough. I think HashMap use Object.hashCode() as its key internally. The Integer class just returns its integer value in its hashCode() function. So you pretty much got exactly what you want. Although there is the overhead of wrapping the int in an Integer.

Offline V

Senior Newbie





« Reply #4 - Posted 2006-01-15 02:46:22 »

http://trove4j.sourceforge.net/

updated in 2005, while the pcj's last update was 2003 (prior to java 1.5).

thank you very much for your help Smiley
Offline kappa
« League of Dukes »

JGO Kernel


Medals: 78
Projects: 15


★★★★★


« Reply #5 - Posted 2006-01-15 22:53:05 »

from what i've seen ArrayLists are pretty fast for general stuff and random access. However LinkedLists are a little faster when having a problem that require you to scroll through the list from begining to end. You may also want to look at FastList at http://javolution.org/
Offline V

Senior Newbie





« Reply #6 - Posted 2006-01-29 07:34:43 »

As I said in my first post, I can't use arraylist or the like because the indices aren't incremental. anyways, thanks for the javolution link, I didn't know about that before and it seems pretty nifty Cheesy

that whole page seems to be an advertisement for those libs, though. any experiences? o_O
Offline Jeff

JGO Coder




Got any cats?


« Reply #7 - Posted 2006-01-29 22:41:16 »

Use Map.

Yes, thats an interface not a class.

The right thing to do whenevr using collections is to design your code to use the interfaces.  Then you can tune later as needed by swaping different implementations (eg HashMap, TreeMap, etc) or even writing your own.

Rule #1 of writing fast code:
First write clean, clear and well encapsulated code.  Second profile.  Thrid go back and fix bottlenecks.

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 V

Senior Newbie





« Reply #8 - Posted 2006-01-30 01:49:50 »

Yeash, but I couldn't find an interface for which there was any implementation for int->object association, that's why I asked in the first place Tongue
Offline Jeff

JGO Coder




Got any cats?


« Reply #9 - Posted 2006-01-30 02:44:06 »

Map<Integer,Object>.

Map associates any two objects

With Java5 autoboxing you can treat int like an object if you so desire.

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
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline V

Senior Newbie





« Reply #10 - Posted 2006-01-30 13:35:51 »

I know, but still using a direct int->object association is faster (saves one boxing and two hash calls per get, and I need tons of gets) than using a boxed int, that's why I asked if there was any specific implementation for that.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 816
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #11 - Posted 2006-01-30 13:38:18 »

Again: IntHashMap from Jakarta Commons

Here is the java2html page...

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

Senior Newbie





« Reply #12 - Posted 2006-01-30 14:16:18 »

I know, I just told Jeff why I asked for this in the first place. >_<
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 816
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #13 - Posted 2006-01-30 14:32:28 »

Err, sorry, I confused krausest's response with yours.

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

JGO Coder




Got any cats?


« Reply #14 - Posted 2006-02-02 00:53:08 »

I know, but still using a direct int->object association is faster (saves one boxing and two hash calls per get, and I need tons of gets) than using a boxed int, that's why I asked if there was any specific implementation for that.

Thats *really* your bottleneck?  You've proved this with a profiler??

I would be astonished if the rest of your code was so beautifully tight that this was significant.

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

JGO Overlord


Medals: 816
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #15 - Posted 2006-02-02 09:11:35 »

I would be astonished if the rest of your code was so beautifully tight that this was significant.

The rest of the code normally doesn't matter... only a few lines will be performance-critical.

It's very easy to create a bottleneck in accessing Maps with autoboxed ints in tight loops. Very easy.
I've done a lot of pathfinding-stuff where the difference between HashMap<Integer, Object> and IntHashMap was significantly astonishing Smiley

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

Junior Duke




There is nothing Nu under the sun


« Reply #16 - Posted 2006-02-02 15:49:10 »

Quote
Thats *really* your bottleneck?  You've proved this with a profiler??
I would be astonished if the rest of your code was so beautifully tight that this was significant.
I wrote a spatial index where autoboxing was, at one point in time, a bottleneck in the index. (About ~50 million objects in the index, with query times running in the low milliseconds). I ended up creating my own special "GeometrySet" interface which enabled me to avoid most boxing/autoboxing at the expense of more complexity.

Of course, I wouldn't randomly go around getting rid of all boxing, but it can be a bottleneck in tight loops that deal with _many_ objects.

About me: http://jroller.com/page/rreyelts
Jace - Easier JNI: http://jace.reyelts.com/jace
Retroweaver - Compile on JDK1.5, and deploy on 1.4: http://retroweaver.sf.net.
Online princec

JGO Kernel


Medals: 404
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #17 - Posted 2006-02-02 17:54:24 »

50million objects = 1.5 gigabytees of object overhead and unnecessary garbage collection trawling too... autoboxing bad! Evil!

Cas Smiley

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 816
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #18 - Posted 2006-02-02 18:06:25 »

30 byte per object?! Shocked Really?

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

Junior Duke




Ue ni taete 'ru hitomi ni kono mi wa dou utsuru


« Reply #19 - Posted 2006-02-02 18:30:45 »

You talk about minimum 2-3+ pointers + 1-0 identifier.
One pointer is on 32 bit computer 4 bytes, it's 8 bytes on 64 bit CPU.
You could look at my old post about my memory problems (with something like patricia trie). 12 - 24 bytes + some aditional object info looks like real object overhead. Test it.

Dipper is superior to any autoboxing (with exception of computationally expensive types), and it alows to use rather nice (and FAST) abstractions with sliding window.

Online princec

JGO Kernel


Medals: 404
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #20 - Posted 2006-02-02 18:45:11 »

30 byte per object?! Shocked Really?
Actually that might have been a little OTT Wink But it would not be unreasonable to implement a VM that allocated objects on 32 byte boundaries...

Cas Smiley

Offline V

Senior Newbie





« Reply #21 - Posted 2006-02-02 23:25:08 »

I never said this was my bottleneck, it's just that there are about 30000 values stored in hashmaps out of which about ~1000 need to be called per tick (1/60 second) or more, so I thought there might be a better way than boxing. It's not critical at all, but why not optimize it Smiley

My bottleneck is - surprise, surprise - java2d Wink
Offline Mr_Light

Senior Duke


Medals: 1


shiny.


« Reply #22 - Posted 2006-02-03 00:58:14 »

if your asking yourself why not make it efficient, the aswer should be yes.
if you truely wondering about optimising it, the answer should be no, not until your have profiled your app.

It's harder to read code than to write it. - it's even harder to write readable code.

The gospel of brother Riven: "The guarantee that all bugs are in *your* code is worth gold." Amen brother a-m-e-n.
Offline V

Senior Newbie





« Reply #23 - Posted 2006-02-03 16:17:40 »

when did I ever say I didn't profile it?? I even posted that I know what my bottleneck is in my very last post. >_<
Offline Mr_Light

Senior Duke


Medals: 1


shiny.


« Reply #24 - Posted 2006-02-03 16:56:00 »

ok I was beeing  dense then.  Grin

but even if you are profiling you pass my assertion, so no worries   Tongue

It's harder to read code than to write it. - it's even harder to write readable code.

The gospel of brother Riven: "The guarantee that all bugs are in *your* code is worth gold." Amen brother a-m-e-n.
Offline Jeff

JGO Coder




Got any cats?


« Reply #25 - Posted 2006-02-04 06:02:35 »

I never said this was my bottleneck, it's just that there are about 30000 values stored in hashmaps out of which about ~1000 need to be called per tick (1/60 second) or more, so I thought there might be a better way than boxing. It's not critical at all, but why not optimize it Smiley

Because, as the Great Abrash puts it....

"Things that don't matter don't matter."

So why waste time and energy on them.


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.

Longarmx (49 views)
2014-10-17 03:59:02

Norakomi (38 views)
2014-10-16 15:22:06

Norakomi (31 views)
2014-10-16 15:20:20

lcass (34 views)
2014-10-15 16:18:58

TehJavaDev (65 views)
2014-10-14 00:39:48

TehJavaDev (65 views)
2014-10-14 00:35:47

TehJavaDev (54 views)
2014-10-14 00:32:37

BurntPizza (72 views)
2014-10-11 23:24:42

BurntPizza (43 views)
2014-10-11 23:10:45

BurntPizza (84 views)
2014-10-11 22:30:10
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!