TMaps
BlitzMax Forums/BlitzMax Programming/TMaps
| ||
| Can somebody explain these in simple, understandable detail? Just having a conversation with a couple of people on IRC about TMaps, and we're all agreed that the documentation for TMaps is rubbish, and yet TMaps seem to be the be-all and end-all to some people. What are they? How and when are they used? Any real-world examples of use? |
| ||
| They're like a dictionary. They're a collection of objects indexed with a key. The key can - like a dictionary - be a string, but it can also be any object. Keys must be unique though. In other words, if you add a definition for "milk" and then add another definition for "milk" the first defintion is replaced with the second. They're used any time you want to store things and retrieve them with any kind of 1 to 1 relationship. By 1 to 1 relationship, I mean that you are only ever going to retrieve one object for any given key. So it wouldn't be any good for grouping objects together and giving them a group name. The indexed objects are kept sorted, as you insert new objects they are placed into the correct slot, so you never need to manually sort things as you do with lists and arrays. Following the dictionary analogy again - when you want the definition of a word, but all you have is the word, you can look them up that way. Because the index is always updated, it's much faster to retrieve it than looking through a huge array or list. I use them for all my game entities. Every game entity has a name, and when I want to find an object by name, I look it up in the TMap. Actually, I used it for dozens of things, but that's one of the first things I did with them. |
| ||
| I think we all understand that. It's like a hash in Perl or a std::map in C++. The thing is... documentation Earlier today I gave them a try and I couldn't make out of the documentation on how to use them. |
| ||
| Yep, understand the one-to-one thing. I've just never really understood what use that is. |
| ||
| I found this thread handy for grokking TMaps. |
| ||
As in that topic I used the Insert() method as well but it started complaining at me. All I did was something like this:
Local map:TMap = New TMap
map.Insert("use_vsync", -1)
|
| ||
| As in that topic I used the Insert() method as well but it started complaining at me. Isn't the idea that you insert objects rather than, say, the int in your example there? That's what I was doing and it seemed to work fine. eg myTmap.Insert(key:string,instance:whateverType) |
| ||
| GfK: how about this for a purpose: You want to count the number of times a certain color is present in a 24bit image, to draw a histogram or something. How would you do that without maps: Define an array of 256*256*256 elements (representing r,g and b) and then for each pixel in the image, simply: mycolorarray[foundR,foundG,foundB]:+1 You can see that predefining a 256^3 array is quite something for your memory, and most of it is not being used, ever. One-on-one into a tmap would be like simply storing a color as you find it. The key would be the rgb combi, and the value you store for that key is the amount of times you found that color in your image. This means you never have wasted memory! |
| ||
| @Sledge: I expected it to be like std::map from C++, in which is possible. I had hoped to use the TMap as a place to store some configuration data. |
| ||
| @Htbaa: You should be fine to do that as long as you wrap your values in a type. Actually, you could probably get away with storing your value as a string (as strings are already a kind of object) then casting to int upon retrieval. |
| ||
| I use it to store key strings and keycode pairs for keyboard configurations. |
| ||
| The good thing about them is, that the hashs are automaticly sorted. I use them in my level editor as some kind of temporary map storage system, where the key is something like "x,y,layer" and the object is a TTile instance. When I write the data-file it is sorted and could be loaded faster into the maparray (not benchmarked, just feeled speed). Also it is easier to handle for an editor, where you have to set tons of tiles and don't want to slice the array over and over again. |
| ||
| I used something similar in a game where you had a 2D playing field that wasn't a fixed size but could potentially be something like 10,000 x 10,000. The contents of the map were created dynamically (like a trail) where the player had been. There wasn't any point using an array, but I did need the quick access to each map 'slot' that an array gave you. So I used a Tmap like data structure, and used a key that was calculated like this: myKey$ = playerx+"_"+playery Then it was simple to check if a map place/slot existed like this: myMap.Contains(somex+"_"+somey) and then check what it contained like this: myMap.ValueForKey(somex+"_"+somey) This system saved a lot of memory, as there were always very large areas of slots with nothing in them. But also had a lot of the structure, flexibility and usefulness of a real array. |
| ||
| I use it for many things. sorting, making sure aone object is only in a list one time, and well z-sorting for graphics. |
| ||
| It sounds a lot like a TList. I use Tlist to store lists of a certain type, like TParticle for example. Each type instance can have a name field if I want and I can iterate though the list checking the name field on each type to find the one I want. However, I never actually do this as I just use pointers to the type instances I'm interested in and iterate though the list and look for those instead. So, in the scenario above, a TMap would just contain the names and a link to the type instead so it's a bit faster right? Does it use Binary Searches (or similar) on the name index to speed up access? How does a TMap automatically sort itself when new items are added? Don't you have to specify your own Sort function like for TLists? Sorting numbers is obvious, but not strings as you could choose to do it case insensitive, and as for objects, you might want to sort on a field or something... I have my own insert functions for TList that look for the right place to add new items to avoid having to waste time sorting the whole list which may already be sorted. Anyway, it sounds like I'm either already using TLists like they were TMaps or I'm missing something... |
| ||
| Yes, it uses a binary search. It isn't really designed for sorting altho of course it does do that as a by product. It's mostly for quick access when you have large amounts of data. I wouldn't describe it as being like a TList. A TList is a linked list, a TMap is a binary tree. :) You might be using TLists like they are TMaps, but unless you have items which share the same name then you probably should be using TMaps (even items with the same name could be easily worked into TMaps tho). Might work out quite a bit faster. |
| ||
| OK thanks. So it's all about the indexing I guess. |
| ||
| GA, your file resource system would benefit from a TMAP I think as you wouldn't have to iterate the list checking the string ID against the object name. |
| ||
| tonyg: Yes agreed that the TImageBank and TSoundBank should be TMaps. Interestingly, paranoid as I am about code performance, I normally set up a load of variables which I assign from Image/Sound banks when a screen is first shown so that I don't have to repeat the TList iteration on the fly later on. |
| ||
| I thought TMap's are basically hash tables which use a hash function to map a key to each slot, so kind of like a TList with direct access jumping to a specific type instance. Not sure where a binary search comes into play, if at all. |
| ||
| The keys are stored in a tree to make them quicker to find or else you'd be iterating through a list of keys to find a pointer to an object. |
| ||
| What if your keys are objects not strings? How can you store them in trees as how can you sort them? |
| ||
| It creates a tree of TNode objects to which your key is attached and doesn't so much sort them as adjust the parent/child relationships to put them in the best place. I believe Bmax uses a red/black tree |
| ||
| I believe it is a Red/Black balanced tree. Each object that you store as a key has a compare method, I believe. The algorithm doesn't care as long as the object knows how to compare itself to another of its type and returns 1,0,-1. I'm using TMaps for having coversation topics associated with script objects in my conversation system. Also, I'm using it to store player variables that might grow over time. Thus my player save algorithm does not need to change as I expand the player object to include new variables and old and new save files are always compatible with each other. I'm also going to use TMaps or a similar tree structure as a game event queue. |
| ||
| I use TList to manage sprite names, animation names. Like Grey I iterate when needed, havn't experienced any speed problems. |
| ||
| I use TList to manage sprite names, animation names. Like Grey I iterate when needed, haven't experienced any speed problems What made you use TLists in the first place rather than TMaps? I always try to use the best available method from the start to cut-down on refactoring which has caught me out before. I know if it does the job its good enough but better to design rather than refactor. |
| ||
| Because I've learned to program Blitzmax without any documentation at all. The only thing I had to go on was this forum (which luckily has some of the best member content I've ever seen) and one of the worst limited, documented help files I've ever seen. I've just recently found out that TLists can store different object types. Yes, I realize there are better ways to do things. Hell I thought for months that TMap was a tile map engine. :) lol... |
| ||
| Because I've learned to program Blitzmax without any documentation at all. And you never even considered to check the module sources? Seriously, reading the source will give you way more knowledge about how things work than reading the docs. |
| ||
| thanks Tonyg and redspark. I thought there must be a compare method for objects, like with TList. MGE: Yeah used TList because I understood it and didn't know what a TMap was. I did read the Bmax docs occasionally and I asked lots of forum questions and learn like that. I've never looked at the source either, I don't like fiddling with the modules. I'm glad that some people do though as they often help me out ;-) |
| ||
| So it's not just a hash table then. Because a hash table would automatically jump straight to an array index based on the hash function applied that created the key... so it's more of a combination of a linked list with a hash function, which really largely defeats the whole point of having a key in the first place, you might as well just have a binary search in an array - although I suppose you get less wasted memory that way. |
| ||
| ... and it's easy to insert and remove objects. |
| ||
| Everyone always brings this up, but no one ever posts example code.. well then, hand it over? |
| ||
| Example code for what? |
| ||
| |
| ||
| Yeah this is straightfoward, thanks. |
| ||
| ahh... so basically it's TList iteration without need for iteration! :) |
| ||
| Kewl, thanks tonyg. |
| ||
| Because it is a balanced tree it always has the same order of magnitude for insert, search and delete operations. (log(n), I believe) |
| ||
| ahh... so basically it's TList iteration without need for iteration! :) More or less, I guess, but it's important to remember that inserting a key a second time will replace the first value with the second. Usually you use TMaps in a situation where this is desirable - it may well be the reason you're using them - but if you need multiple entries for the same key ( eg: in a dictionary you might want multiple definitions for a word with the same spelling ) you should not be using TMap's. Otherwise, it's about the same. You can even iterate through the contents of a Map when you need to, because it has methods called Values() and Keys() which give you an enumerator object, which is what EachIn uses. So in the same way that you can say For A=EachIn MyList you can say For A=EachIn MyList.Values() or For A=EachIn MyList.Keys() depending on whether you want key or value. |
| ||
| Redspark helped me to convert my Framework's TImageBank, TSoundBank and TGameText (for localisation) to TMap, thanks dude! |
| ||
| Quick tangent question - what are the ramifications of declaring a global inside a type? I'm assuming, looking at that code, that it will instance the map if it isn't already declared? |
| ||
| It's the same as creating static variable. It will exist globally within that type only, defined once and available within the type for the programs duration. |
| ||
| Yeah I do it all the time, it's handy. |
| ||
| Hells, yeah. *tries to upmod this thread* |
| ||
| To iterate through a map, you have to use a special enumerator: lets assume myTMap is your TMap and you want to iterate through all elements in it, like in a TList myTmap contains some Elements of the Type "elementType" and contains at least one Field "myElementDataField"
temp:TMapEnumerator = MapValues(myTMap)
For Local element:elementType = EachIn temp
DebugLog(" Value: "+element.myElementDataField)
Next
|
| ||
| ahh... so basically it's TList iteration without need for iteration! :) technically it does iterate through the map.. actually, it may iterate more elements that's why it is a poor choice for sequential access to data. it's a fantastic choice when searching by value though because it will tend to iterate through less elements (when I say elements, I don't mean stored objects) to find your object. It really shines with searching large data sets. so a map is certainly not a replacement for a list. |
| ||
| Here is a way to visualise the data stored in your TMap: I've also placed it in the Code Archive. :) |
| ||
| TMaps are one of the greatest features of the BlitzMax language. |
| ||
| There just Hash tables? Is there a difference I'm missing? |
| ||
| TMaps don't use a hash though. |
| ||
| They are not hash tables! They are binary trees. Huge difference. Hash tables create a (non unique) index from the key (using a mathematical algorithm) and then insert the data into a bucket (often with other items). Binary trees search for an appropriate place to put the data in a tree structure, using a non-mathematical, simple comparison algorithm. |
| ||
| Yes I see('looks at mod'), it is a binary tree using string comparison for branch selection. Not the fastest for all occasions but it is a very good general purpose solution. |
| ||
| Hash tables create a (non unique) index from the key (using a mathematical algorithm) and then insert the data into a bucket (often with other items). This isn't necessarily true [edit: ah, misread - yeah, technically the index isn't guaranteed to be unique, and often isn't, but that's not really important as long as appropriate hash collision code is in place] My hash table code in the archive allows you to selectively overwrite any entries in a bucket with a matching key, if you so choose, make sure you don't have two keys that are referencing the same object, remove any entries with a given key, remove only entries with a given key and a given object, or search the whole hash table for an object (when the key is unknown, for some reason) and remove any entry that matches the object. The only thing not implemented there is that the table will not automatically grow. I should really tidy up the code and add a few more utility functions and get the auto-growth parameters and functions implemented. As it is though, it's quite fast - in my tests it was regularly faster than Lua table lookups (which are essentially hash table lookups, coded in C). http://www.blitzmax.com/codearcs/codearcs.php?code=1907 It also allows you to write an overloaded Compare method for you objects that can be called on any entry results you have - so you could store multiple items with the same key, assign them each some priority value, and then using a custom Compare() method retrieve only the highest priority entry for that given key, for example. |
| ||
| I guess its stuff like this that is making people move to unity3d. Most people not already in a pro development job wants to just make games without spending a week working out why they even need TMaps. Its ironic blitz started out as being as easy as possible to use and morphed into something that might as well be C++. |
| ||
| You don't *have* to use it. I think for most purposes you can perfectly go without them. |
   |