Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (483)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (550)
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  
  Improving Map performance by knowing all keys up front?  (Read 2624 times)
0 Members and 1 Guest are viewing this topic.
Offline actual

JGO Coder


Medals: 23



« Posted 2012-12-16 02:33:19 »

I have run across a number of cases where I have a Map where once I set it up, the keys never change (although the values against them do). I don't necessarily know what the keys will be until I create the map but once I do they are fixed.

I was wondering, is there a way to take advantage of this fact to design a Map like data structure that retrieves values more efficiently than the standard implementations?

The class signature would roughly follow the Map interface and might look something like:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
public class FixedKeyMap<K,V> {
   
   // Takes in a list of keys for the map.
  // These keys cannot be added to or removed from.
  // All values are initially set to null.
  public FixedKeyMap(List<K> keys) {}

   // If the Key is valid, replace its value with this one.
  // Otherwise do nothing or throw an exception.
  public void put(K key,V value) {}

   // If key is valid then get the value associated with it
  // Otherwise return null or throw an exception.
  public V get(K key) { }

   // If key is valid then sets its value to null. Does not remove it.
  // Otherwise, do nothing or throw an exception.
  public void remove(K key) { }

   // Sets all values to null but does not remove keys.
  public void clear() {}

   // Returns a set containing all of the keys.
  public Set<K> keySet() { }
}


I looked at the HashMap source and it looks like you would be able to pull out a lot of code around load factors and capacities and simplify some of the other code because the size would be known at creation time.

Anyone have any thoughts on how such a thing might be designed to take advantage of the fact that the keys are all known up front? Could you get rid of the hashing function altogether?

I do recognize that this is a micro optimisation and may or may not be worth the effort for a given application but the question seemed interesting and so I thought I would ask if others had any ideas.
Offline Best Username Ever

Junior Member





« Reply #1 - Posted 2012-12-16 02:55:35 »

I have wanted such a class for a while now. I can think of three ways to do this. For small maps, just use an array. For large maps I only can think of two. 1) Construct a minimal perfect hash function on the keyset at runtime. Huh 2) Put them in a sorted array and use a binary search for key look ups. Stare
Offline Nate

JGO Kernel


Medals: 145
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #2 - Posted 2012-12-16 04:25:25 »

If you create the map and then only do gets, a cuckoo map would be an option. It essentially spends effort during puts to make gets efficient. libgdx has an implementation and also an identity map and a few for primitive keys/values (all based on cuckoo).

Otherwise you can give each of your keys an ordinal and then use an array for the values. This isn't general purpose of course.

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

JGO Kernel


Medals: 202



« Reply #3 - Posted 2012-12-16 05:29:56 »

http://www.anarres.org/projects/jperf/

If you use any alternative Map implementation, you should profile to make sure it's saving you anything.  And yes, if all your use sites are static you can get rid of the hashing altogether and just use the values themselves (or references to them, basically the same thing in java), but that's kind of a trivial use case.  Best you might otherwise do is use Enums and let the JIT optimize the switch table.
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.

CopyableCougar4 (19 views)
2014-08-22 19:31:30

atombrot (30 views)
2014-08-19 09:29:53

Tekkerue (26 views)
2014-08-16 06:45:27

Tekkerue (23 views)
2014-08-16 06:22:17

Tekkerue (15 views)
2014-08-16 06:20:21

Tekkerue (24 views)
2014-08-16 06:12:11

Rayexar (63 views)
2014-08-11 02:49:23

BurntPizza (40 views)
2014-08-09 21:09:32

BurntPizza (31 views)
2014-08-08 02:01:56

Norakomi (38 views)
2014-08-06 19:49:38
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

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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!