Still havnt found a good use for TMap
BlitzMax Forums/BlitzMax Beginners Area/Still havnt found a good use for TMap
| ||
| Im aware of TMap functionality but yet I havnt found a use for it. All I use is TList and Array. Can someone point of a good use of TMap where TList is less useful or cannot function at all? |
| ||
| Lists and arrays just store elements. Maps store elements alongside a search key. If you needed to retrieve an element by matching against a particular key (e.g. find an object by name string), you would probably want to use a map. In contrast, lists have no key at all, so all you can do is loop over every element; and arrays have indices instead of keys, which are very fast but implicitly controlled by the array structure. Maps allow you to use any object as a key, which is useful for non-continuous data or where the key has an actual connection to the object's value somehow. |
| ||
| Hmm. A 'real world' example would be MaxGUI. TGadgets are subclassed objects of the original OS objects. The original OS object is referenced by a unique integer handle value, and ( on Mac and Windows ) that integer value is used as the key while the instance of the associated BMax TGadget object is the element. When the OS wants to 'communicate' with the OS object ( for/caused by user interaction ) it will send the OS handle value to MaxGUI ( sometimes via callback ) which looks up the associated TGadget from the TMap ( using the OS handle as the key ) and pass the interaction data on to the BMax instance. |
| ||
| My locale class uses TMaps for returning a localised version of string from a given stringID. And it's plenty fast enough to use on-the-fly. Could not do that with a TList. |
| ||
| I use TMaps for reading my configuration files (like ini files). Just read the pair in the from the config file, then when I want to know the value of the option, I search by key. somekey=somevalue anotherkey=anothervalue etc... Then when I want to know what some key was equal to, I pull it from the TMap. This way, I do not need to know ahead of time what values will be in the configuration file for storing into variables or anything and I do not have to care what order they are in the config file. |
| ||
| In other languages a TMap is sometimes called a Dictionary. And that is definitely one use for it. I once used them to store tiled levels that were huge but very sparse. The key would be built by adding the x and y position separated by an underscore, eg. "12_1058". It was an excellent low memory but high performance method for storing levels of this sort. |
| ||
| Something you should know about TMap data is that they are stored and searched using a binary tree. This helps speed up access times. |
| ||
| It was an excellent low memory but high performance method for storing levels of this sort. Do you mean low performance? that is, the tradeoff of that method is using little memory, but being computationally more expensive. |
| ||
| So what your saying if I Insert to a Map Same object to Key And Value For Example: MapInsert( map:TMap,DataCell,DataCell ) Type DataCell Field Name$="Test" Field SomeInfo... End Type And I Want to Get The DataCell using Its Name I will Get It Faster then searching Tlist Objects List looking for the specific Name? |
| ||
| It depends on the number of items in the data collection. Imagine you have a TList with over 65000 elements. If the item you're looking for is at the end of the list then you'd be doing over 65000 iterations to get to your element. In a TMap, as mentioned above it uses a binary search algo, so the max number of search iterations would be 16 to get to your element. I think the actual processing of the TMap search is more expensive than using a TList, so if you have a relatively small number of items ( less than a couple of hundred ) then a TList is computationally faster, any more items then a TMap takes the lead for speed, but I stand to be corrected as to where that 'tipping point' is. Remember, a TMap relies on you using a unique key to element relation, whereas a TList doesn't use keys at all. |
| ||
| Kryzon - you could call it low performance, but it was much higher performance than using an array on a low memory device. It was actually running on an old Windows CE phone many years ago. Also, don't forget that if speed isn't an issue then a TMap might just be better fit, and be just fast enough. |
| ||
| Isn't a TMap kind of a hash table thing.. so if you wanted to store like a database of lots of information or something it would give you quick access to finding elements based on keys? |
| ||
| Some languages have associative arrays implemented using hash tables but TMap isn't. |
| ||
| Isn't a TMap kind of a hash table thing.. so if you wanted to store like a database of lots of information or something it would give you quick access to finding elements based on keys? Essentially, yes.Mr Google tells me that Hash Tables have an average time complexity of O(1), whilst Balanced Binary Trees have O(Log n). |
| ||
| You use different containers for different tasks. so you use an array when you want to retrieve your objects with an integer index. you use a list if you want to iterate over all objets n it and do something with it. and a dictionary (or TMap) is used to get elements by using a unique key. the last two times I used a TMap I've used it for -storing gamescenes, and naming them "intro", "settings", "main" etc. -storing a super large 3d world in chunks (aka minecraft) the keys I used for the dictionary were strings that told me the location like "01_20_56" (x,y,z). that way the memory requirements where a fraction of the cost compared to an initialized 3d array. |
| ||
| Mr Google tells me that Hash Tables have an average time complexity of O(1), whilst Balanced Binary Trees have O(Log n). Col already touched on this in post #10, but remember that time complexity is a mathematical abstract that has increasingly little to do with performance of real-world systems. (Or rather it still has and always will have everything to do with it, but you have to be careful that what you intended to write ends up bearing some resemblance to what is being run.) |
| ||
Maps are extremely useful in many situations. Some of the things I used them for in BMax: Instead of generating my user interfaces in code, I used to write some XML files with the GUI description, just like this:<interface> <window key="win"> <title>My Main Window</title> <coords x="0" y="0" width="640" height="480" /> <flag>titlebar</flag> <flag>resizable</flag> <flag>clientcoords</flag> <flag>center</flag> </window> <canvas key="canvas" parent="win"> <coords x="0" y="0" width="640" height="480" /> </canvas> </interface> And then, I wrote a generic "LoadGUI" function that I can use on every project, which parses the XML, creates the correct gadgets, attached to their respective parents, and returns a TMap object which contains a set of key/value pairs with the handle to each gadget identified by the string on its "key" attribute on the XML file. So basically, you call LoadGUI, and later you get the needed gadgets from the map and store them in variables or whatever you need. This is just one example, but there are many many uses for maps. |
   |