Map and Set with fast iteration of the elements

Any community contributions to libgdx go here! Some may get included in the core API when permission is granted.

Map and Set with fast iteration of the elements

Postby ruben01 » Mon Sep 12, 2011 8:57 pm

Hi guys, for some of our games, we needed some map and sets, that allowed iteration of the elements without generating garbage, and while still being efficient.

so we created RandomAccessMap and RandomAccessSet this classes implement the map and set interfaces.

The set also implements RandomAccess which has a get(index) and a size() method to allow iteration on the elements.

The map implements RandomAccessWithKey that inherits from RandomAccess so you have get(index), size() and getKey(index) to iterate over the key,value pairs.

The set is implemented using an arraylist and objectintmap, what we do is use the objectintmap to store the index on the array of the element, and when removing we swap the last item of the array with the space left by the removed element. This way you maintain a O(1) for the set operations while having a continuous array to iterate on the elements of the set.

The map is made the same way but with two arraylists and the objectintmap, the second arraylist is used to store the keys, and you get O(1) for the map operations and can iterate asking for the key and value by index.

So far I added some tests for the map implementation to show a little about how it works (and also to have tests :-))

The github project is here

hope anyone finds it useful, and would rock to get this added into libgdx.
ruben01
 
Posts: 5
Joined: Wed May 25, 2011 9:07 pm

Re: Map and Set with fast iteration of the elements

Postby radioking » Mon Sep 12, 2011 9:10 pm

+1 for creative and speaking method names ;-)

If this makes life easier and if it is as performant as you are saying- why not adding it to libGDX.
The devs will evaluate it for sure- they got the masterplan...

May the source be with you! =)
Last edited by radioking on Wed Sep 14, 2011 11:08 am, edited 1 time in total.
Please "give sth. back" to community and contribute your knowledge to our libgdx-users project community wiki:
http://code.google.com/p/libgdx-users/
Please see Mario's note on User Wiki 2.0: http://www.badlogicgames.com/wordpress/?p=2411
radioking
 
Posts: 284
Joined: Wed Aug 03, 2011 10:28 am

Re: Map and Set with fast iteration of the elements

Postby NateS » Tue Sep 13, 2011 1:13 am

Sounds neat. Have you benchmarked it to see the different between iterating over the keys and values in an ObjectMap? ObjectMap may get a boost by accessing memory sequentially, so it may not be a huge difference. The ObjectMap capacity an load factor will affect iteration performance a little, as a high capacity will cause more nulls to be skipped during iteration.

I occasionally find myself wanting an efficient sorted map...
NateS
 
Posts: 1980
Joined: Fri Nov 12, 2010 11:08 am


Return to Libgdx Contributions

Who is online

Users browsing this forum: No registered users and 1 guest