Editing revision 2 of ZoomTargeting/MemoryIssue

Robo Home | Changes | Preferences | AllPages

Editing old revision 2. Saving this page will replace the latest revision with this text.

Currently I am reserving memoryspace for every zoom level whether it is used or not. I use a simple (6 dimensional) array for that. The drawback of this is that memory is reserved for segments that I never use and memory soon spins out of control. Now I want to implement a dynamic array (Vector or ArrayList or something). The question is, which type of dynamic array would be most suitable for this situation? Most importantly I require the lowest possible memory footprint.

-- [[Vic]]

Both an ArrayList and a Vector would work here. The constructor for each allow you to specify the size of the Arraylist to be built. They will also grow as more items are added to them. The "growing" part can be expensive in terms of CPU cycles so you will most likely need to play with them to see how it works out with skipped turns. Of the two, I would imagine that the ArrayList would be more appropriate than the Vector. I am also unsure if this will buy you anything in terms of memory footprint as I think in the end both classes use an Array with wrapper methods to implement their functionality. -- [[Sparafucil3|jim]]

LOL, I already implemented this gun about three months ago for Statistician -- it's sitting on my hard drive right now.  This gun was the main feature of Statistician (and his namesake) and it will be one of Tax's main guns.  You can probably find me talking about it here and there on the wiki.  Although, it will be better implemented in Tax due to the ability to segment stats more intelligently with his neural network.  Oh, to answer your question, I used a HashMap that stores strings of movement.  For instance, if I tokenize a bot's velocity into the letters a-p, where a is -8 and p is +8, then I might have a string that looks like this: "aaaacegiiii".  I stick that in the HashMap, along with a two-dimensional array of all my segments, and I just update the array as I need to.  This makes sure that you only use memory for the patterns that you have seen, and it is a very fast pattern-matcher.  -- [[nano]]

Interestingly, this approach also allows an infinite amount of "zooming".  Of course, there are memory limits, but I ran my algorithm at a maximum of 200 frames of movement, and it ran fast with no memory problems.  Thank God for a fast and efficient HashMap implementation.  -- [[nano]]

Ok, thanx. What would I use for index if I'd want to implement an ArrayList? Say, for instance, in my original multidimensional Array I want to access Angle[0][1][1][0][1][1]. I need to do some sort of mapping from the 6 original indices to a single one. A possibility might be to convert these indices to a single integer, in this case ranging from 0 to 63 (6 bits). But can I insert the Angle at position 54 [ArrayList: add(54, Angle)] without my ArrayList or Vector immediately reserving memory space for the preceding 0 to 53? I think not, but I'm not sure. Does anyone know for sure?

That probably means the HashMap is the better solution. I can put my single Index 54 in it along with my Angle value [HashMap: put(Indexobject, Angleobject). However, a HashMap stores both key and value objects. Suppose my original value to store is an int. I now need to construct a wrapper object for it, an Int. Also I need to construct an Int object for my key. Assuming an Int takes equal memoryspace (it is just an int with wrapper methods, right?) then I must conclude that using a HashMap requires double the amount of memory PER ENTRY. So, if I have less than 32 entries I should use the HashMap, else I should stick to my original Array. This is getting complicated... Although I think that in practise I almost never will get more then 32 MicroSegments per Segment. I'll try the HashMap and report back if it works...

-- [[Vic]]

It might be more sensible to just use a binary string instead of using an Integer object (might as well use java.lang.Integer, though, if you do that), meaning you would access the said angle by using map.get("011011") or something.  Might be simpler.  If you use the array thing, it might make sense to just go ahead and allocate the thing (4 bytes * size of the array for that many null pointers), it may not be a big hit when it's empty anyways.  If you know some segments won't be hit, though, that's a consideration (particularly if it happens to be a lot of segments) -- [[Kawigi]]

It would sure be easier and more readable to use such a binary string. But how does the HashMap store this?
I guess it would generate a hash number so it will not use more memory then using my Int.. Is this assumption correct? -- [[Vic]]

That should be correct.  If a HashMap turns out to be weightier than you can handle, you could also try just implementing your own Hashtable.  For even more efficient memory (but a compromise on speed somewhat), you could throw everything into a BST or something. -- [[Kawigi]]

Binary Search Tree I presume.. Hmm gotta think about that tomorrow....it's getting late here. By the way, I already tried using a normal array and memory consumption goes through the roof, even with a high percentage of nullpointers. -- [[Vic]]

Kawigi, I don't understand how I would use a BST in my situation. I'm still interested since you spoke of more efficient memory so could you explain a little? But for now I've decided to go and try make my own container class. I only need a byte (8 bits) of memory for my key and I'm pretty sure all the java.util containers use an int (32 bits). Besides, it's a good exercise :-) -- [[Vic]]

Well, you sort them into the BST by key.  The root key can either be the first MicroSegment you use, or an intelligently chosen constant one.  Then you sort new MicroSegments into the BST as you have them.  It shouldn't really ever take more memory than it needs, and in the best case, look-ups and insertions are O(log(n)).  In the worst case, without intervention, look-ups are O(n), which probably isn't what you want.  You can reduce that by a constant (in half, actually) by picking an intelligent root node all the time.  If you think look-ups are more common/time critical than insertions, you can do checks to make the tree more balanced for consistent O(log(n)) look-ups at the expense of some checks and possible AVL rotations within the insertion part.  -- [[Kawigi]]

Just use a TreeMap. ;)  If memory is a problem with a HashMap (it was never really a problem with mine -- do you have less than 256MB?), then you can try it with a TreeMap.  If that isn't sufficient, <i>then</i> consider implementing your own structure.  These two Java implementations are incredibly fast and efficient (though they can be improved upon), and I would definitely try both before hacking it out on my own. -- [[nano]]

Ok, I've used the HashMap in the end and ... hey! it works :-) Even without optimizing initial capacity and load factor the memory consumption is a fraction of what it was. Thanks for your help guys! -- [[Vic]]

This is belated, but have you considered BSTs? -- [[Kuuran]]

Summary:
Consciousness check: 5 * 11 =
This change is a minor edit. Send email notification that ZoomTargeting/MemoryIssue has been changed.
(Visit Preferences to set your user name.)

View other revisions
Robo Home | ZoomTargeting | Changes | Preferences | AllPages