Map vs List
BlitzMax Forums/BlitzMax Programming/Map vs List
| ||
| If you don't need to do any form of sorting is it better to use maps? |
| ||
| No. It's better to use lists when you don't need maps and only use maps when you need them. If you don't know if you need them, you don't need them. Use lists. |
| ||
| Aren't maps faster? When/Why would you want to use a list over a map? When would it be better to use a map? Sorry if I'm asking a lot of questions, I'm really curious |
| ||
| Sorry if I'm asking a lot of questions, I'm really curious Not at all. I assumed you had a specific function in mind, which is why I tried to cut to the answer and not clutter you up with information you didn't need. If you're asking because you're trying to learn more about maps, they're perfectly valid questions. Aren't maps faster? Faster for what? With collections, you have more than one yardstick for speed. There's the insertion speed (the time it takes to add a new item to a collection) but there's also the removal time, iteration time, etc. Depending on the collection, they might be faster in some areas and slower in others. I haven't benchmarked maps, but if they're faster than lists in general then there's something wrong with BlitzMax's implementation of lists. Lists are just that. When you create a new item, you just stick it on the end of the list. When you add a new item to a map, you have to traverse the map to the find the right place to store it. The one area where Maps are faster is retrieving an object by index, but more on that later. So, no, I suspect Maps are not faster for anything except retrieval by key. When/Why would you want to use a list over a map? If you don't specifically need a map, you would always use a list. I realize that's a backwards answer from where you're sitting, but it's the only one I have. Maps are associative arrays. That means that every object in a map is associated with another object. They're known as Key and Value pairs. So every time you add an object to map (objects added to a map are the Value) then you associate that "Value" with a "Key". The key might be anything. It could be another Object (eg: any BlitzMax type) but it might also be a string, if you want to search your collection by name. So a simple example might be writing a computerized encyclopaedia. You have a lot of "entries" for your encyclopaedia, so these are the "Values" in your map. When a user wants to look something up, he is going to supply a word, a name, or in BlitzMax, a string. So you would associate each entry "value" with a string "key". The collection inserts your "value" in the right place in the map (sorted by the "Key") and then it can find that "Value" much quicker than you could in a list when you later ask for it by providing the "Key". If you don't need an associative array, there's no sense using a Map. If you don't need to index one object by another, use a List instead. When would it be better to use a map? Usually for searching and retrieving things in a collection in a faster manner than a list. Searching in a list means manually sorting the list or at worst going through every single entry in a list to see if what you're looking for is there. Searching a map will always be quicker because maps are always sorted, making searching a faster process. Another purpose might be if you need your collection to always be sorted. If you have a list which is updated constantly, but must always be displayed or processed in a particular order, it might make sense to use a Map, which will keep itself sorted automatically, instead of having to do so manually. It will depend on how much searching, sorting and inserting you need to do though. If you were inserting hundreds of items per frame, it might be quicker to insert them all in a list and then only sort once. If you're inserting less frequently, the map might work out faster, as it won't need to process the entire collection. |
| ||
| Wow thanks for the incredible answer! I definitely understand it now :) |
| ||
| Also refer to this thread for further valuable info. |
| ||
| Maps are a compromise between arrays and lists. Unlike arrays, they are not fixed in size. Unlike lists, each item is "indexed". In an array, you can only use numbers but with maps you can use strings or objects. For example, if you have a bunch of sound files for certain words, you could store them in a map where the key is the word. So the sound file that says "hello" is stored in the map with the key... "hello"! Then if a user types in a sentence (assuming all the sentence words have sounds), you can quickly and easily retrieve the sounds from the map and play them. For situations where you don't need to randomly access a particular item as a one-off occurrence, use a list. This is most game situations. Usually you loop through the entire list and update everything inside it. A map for that situation would be slower. Warning: for a particular map, the keys must either be ALL strings or ALL objects. The values can be anything safely. |
   |