I'm tired of HashMaps

Discussion in 'Plugin Development' started by Jaker232, Dec 26, 2011.

Thread Status:
Not open for further replies.
  1. Offline

    halley

    http://wiki.bukkit.org/Java_data_structure_classes

    I made a link to this from the Plugin Tutorial. I did the basic post above, and explained Array and List with examples of syntax for common tasks. If you want to add/finish the Set and Map syntax examples in the same style I started, I'd appreciate it. If not, I'll deal with it sometime later.
     
  2. Offline

    bergerkiller

    @halley Maybe you can help me with this. I have to choose between a hashmap and a list right now.
    Code:
        private static List<ChunkCoordIndexer> calculatedIndices = new ArrayList<ChunkCoordIndexer>();
        public static int get(final int dx, final int dz, final BlockFace direction) {
            for (ChunkCoordIndexer indexer : calculatedIndices) {
                if (indexer.dx == dx && indexer.dz == dz && indexer.direction == direction) {
                    return indexer.index;
                }
            }
            return new ChunkCoordIndexer(dx, dz, direction).index;
        }
    basically, every unique set of 'dx, dz and direction' make one unique index. The calculation of this index takes pretty long considered how many times it is called (0.01 ms, getting called 400 times every tick). The list equivalent above takes 0.001 ms to loop through all elements. Can a Hashmap (with a special key of dx, dz, direction) perform better, or not?
     
  3. @bergerkiller: Would probably be better to know ChunkCoordIndexer. If it just stores the 3 ints and the BlockFace, what about something like that:
    Code:java
    1. private static Map<String, Integer> calculatedIndices = new ArrayList<String, Integer>();
    2. public static int get(final int dx, final int dz, final BlockFace direction) {
    3. String hash = dx+"--"+dz+"--"+direction.toString(); // or direction.hashcode() or whatever gives a good result.
    4. if(calculatedIndices.containsKey(hash)
    5. return calculatedIndices.get(hash);
    6. else
    7. // Do stuff to get and return the index here.
    8. }
     
  4. Offline

    bergerkiller

    @V10lator Background information:
    dx and dz are always in between -viewdistance and viewdistance (outside no chunks get added and if they do, the index is simply max_value anyway)
    8 directions are used.
    Code:
        private final int dx, dz;
        private final BlockFace direction;
        private int index = -1;
        private ChunkCoordIndexer(final int dx, final int dz, final BlockFace direction) {
            this.dx = dx;
            this.dz = dz;
            this.direction = direction;
            this.offset();
            calculatedIndices.add(this);
        }
    The offset function calculates the index.

    So basically, the map will contain on max (view distance = 13):
    27 * 27 * 8 = 729 * 8 = 5832 elements.
    What would be faster:
    - Have the map store all 5832 elements
    - Use an array of 8 lists with 729 items and loop through the list to get the index
    - Use an array of 8 hashmaps with 729 indices and get the index from this map

    The index of the 8-length array can easily be obtained from the direction (there are only 8). Which one is better?
     
  5. Offline

    Afforess

    @bergerkiller this looks like a place where you could squash the values into a long and use 1 long as a key in a map.

    Direction can fit in half a byte (0xf), then shift up 4 bits, store the x, then shift up 30 bits and store the z.

    This gives x and z 30 bits and the direction 4.

    I also highly recommend you look into the Trove library - it's a primitive collection library, you can get 10x performance over java utils package, and 25 percent memory usage.
     
  6. Offline

    bergerkiller

    @Afforess I kept it simple, used the hashcode system :)

    Code:
        public boolean equals(Object object) {
            if (object == this) return true;
            if (object instanceof ChunkCoordIndexer) {
                ChunkCoordIndexer other = (ChunkCoordIndexer) object;
                return other.dx == this.dx && other.dz == this.dz && other.direction == this.direction;
            }
            return false;
        }
        public int hashcode() {
            return this.dx * 20 + this.dz * 800 + this.direction.ordinal();
        }
    That combined with:
    Code:
                                for (Object o : this) ((IndexedPair) o).calculateIndex(this.x, this.z, this.sendDirection);
                                java.util.Collections.sort(this, new Comparator<IndexedPair>() {
                                    public int compare(IndexedPair p1, IndexedPair p2) {
                                        return p1.index - p2.index;
                                    }
                                });
    Truly reduces times a lot. Took around 0.1 ms to sort the entire list of 700 items. (the first time it does take longer, since it has to fill that hashmap. The first generation time takes around 7 ms)

    Unless you know a faster way to sort based on indices, of course ;)

    Code:
    21:39:46 [INFO] SORTING: 0.11244
    21:39:50 [INFO] SORTING: 0.20844
    21:39:51 [INFO] SORTING: 0.91928
    21:39:52 [INFO] SORTING: 0.11644
    21:39:52 [INFO] SORTING: 0.03132
    21:39:54 [INFO] SORTING: 0.11424
    21:39:54 [INFO] SORTING: 0.0952
    21:39:56 [INFO] SORTING: 0.14076
    21:39:57 [INFO] SORTING: 0.2014
    21:39:57 [INFO] SORTING: 0.10652
    21:39:58 [INFO] SORTING: 0.33792
    21:39:58 [INFO] SORTING: 0.45528
    21:39:58 [INFO] SORTING: 0.27672
    21:39:59 [INFO] SORTING: 0.12904
    21:39:59 [INFO] SORTING: 0.02616
    21:40:00 [INFO] SORTING: 0.20916
    21:40:00 [INFO] SORTING: 1.00008
    21:40:00 [INFO] SORTING: 0.2628
    21:40:00 [INFO] SORTING: 0.21844
    21:40:02 [INFO] SORTING: 0.1084
    21:40:02 [INFO] SORTING: 0.03012
    21:40:04 [INFO] SORTING: 0.11508
    21:40:04 [INFO] SORTING: 0.05664
    21:40:06 [INFO] SORTING: 0.136
    21:40:06 [INFO] SORTING: 0.111
    21:40:07 [INFO] SORTING: 0.14372
    21:40:09 [INFO] SORTING: 0.113
    21:40:11 [INFO] SORTING: 0.14604
    21:40:12 [INFO] SORTING: 0.14296
    21:40:14 [INFO] SORTING: 0.1454
    21:40:15 [INFO] SORTING: 0.14464
    21:40:15 [INFO] SORTING: 0.02488
    21:40:16 [INFO] SORTING: 0.11504
    21:40:17 [INFO] SORTING: 0.23452
    21:40:17 [INFO] SORTING: 0.10272
    21:40:18 [INFO] SORTING: 0.14676
    21:40:20 [INFO] SORTING: 0.14756
    21:40:20 [INFO] SORTING: 0.141
    21:40:21 [INFO] SORTING: 0.07968
    21:40:21 [INFO] SORTING: 0.114
    21:40:22 [INFO] SORTING: 0.09704
    21:40:22 [INFO] SORTING: 0.14124
    21:40:22 [INFO] SORTING: 0.14092
    21:40:23 [INFO] SORTING: 0.14544
    21:40:25 [INFO] SORTING: 0.15184
    21:40:26 [INFO] SORTING: 0.14172
     
  7. Offline

    KaiBB

    Why is this even in the Dev forums? And you don't seem very good at HashMaps, as you haven't answered a single one of my questions about HashMaps correctly. So maybe you won't be so tired of HashMaps when you know how to use them.
     
    ZNickq likes this.
  8. Offline

    Jaker232

    @NuclearW , blame him for moving it here.
     
  9. Offline

    KaiBB

    Why? :confused:
     
  10. Offline

    hatstand

    Better question, why should this discussion not be in the dev forum? It's relevant to plugin development.
     
  11. Why wouldn't it be in the dev forum? Its about Plugin Development....
    And although you bring up a good point about the OP not being good at hashmaps, neither are you ;)
     
  12. Offline

    KaiBB

    At least as good as him. And I thought this was more for development help not discussion. So my bad.
     
  13. I was just pointing it out ;) And I think the forum is anything revolving plugin development..Anyway who cares?
     
  14. Offline

    NuclearW

    What @hatstand and @tips48 said.
     
Thread Status:
Not open for further replies.

Share This Page