Fast way to access objects of a list
BlitzMax Forums/BlitzMax Beginners Area/Fast way to access objects of a list
| ||
| Besides looping through a list using For... eachin, is there a faster way to access a list of Types, perhaps using a link? For example, if I have a list of 10000 objects and I only want to pull out 100 of them, is there a way without looking at all 10000 of them? I know there is valueatindex but is there a better way? Thanks in advance for the help. Last edited 2012 |
| ||
| Storing a link will let you retrieve that particular object. Otherwise, no, you've run up against one of the limitations of lists. Depending on the overall nature of what you want to do with the structure, consider using an array or a map (TMap) instead. Lists: very fast at adding extra items (even in the middle), removing items, and iterating over the whole collection. Very slow at replacing or finding a specific item Arrays: very fast at replacing or finding a specific (numbered) item, fast at iterating over the whole collection. Very slow at adding or deleting cells outright, especially in the middle Maps: reasonably fast at adding, removing, and finding items. Slow at iterating over the whole collection If you have a list of 10000 objects, it will take on average 5000 comparisons to locate the one you want (where a comparison is the whole process of testing an object and getting the next one). If you have a map of 10000 objects, it will take an average of 14 comparisons to locate the one you want. Since this is logarithmic, if your collection increases to a million objects, the list will require 500000 comparisons while the map requires only 20 (counter: since this is logarithmic and a more complicated comparison, for under ~50-100 objects it's often not worth using a map). So, what other operations do you want to perform on your collection? How is it built, how often does it change, and most importantly, how often and when in your program are you searching for objects from it? Outside the main loop? Iterating over 10000 objects doesn't matter anyway. Once per frame it's still probably fast enough. Inside a tight inner loop however and you should seriously consider an array. Last edited 2012 |
| ||
| Hi Yasha, thanks for that detailed answer, it's appreciated. How would I retrieve an object by it's link? I looked through the functions but it's not obvious to me even though it's probably staring right at me. |
| ||
| Also remember that you can have objects in more than one list. So if you want to have all your objects in a list for drawing, you can have a DrawList containing them all, but if you also want to iterate through all the enemies to see if they are in range of the player, you can have an EnemyList with just the enemy objects contained within it. You do have to remember if you want to remove an object from play, you need to remove it from all lists it is contained in for the GC to properly collect the object from memory. |
| ||
| Don't forget about hashtables. I cant think of a situation where anyone would choose tMap over a hashtable. |
| ||
| How would I retrieve an object by it's link? Links are just the nodes or cells in a list that actually hold the objects - an internal implementation detail of the list. Generally to use them you have to manipulate the list manually. The link itself has a Value() method that will return the stored object... but to be honest I can't see any circumstances where this would be useful (you may as well say "if you have the object in a local, then you can easily access it" - I was just replying to the fact you mentioned links in the OP). Basically if you have a link, you must have already found the object by some other means (also, most means of finding an object just return the object, so finding the link first actually adds a layer of complexity). (The real reason things like links are even present is simply because lists themselves are implemented in lower-level BlitzMax code.) Don't forget about hashtables. I cant think of a situation where anyone would choose tMap over a hashtable. True in most cases, although BlitzMax not coming with any built-in hashtable may be a minor obstacle to that for the new user. (Finding one shouldn't be too hard, but you need to know what to look for.) There are still some tradeoffs. Again, it depends very much on what the collection is being used for and how it is being accessed. Last edited 2012 |
| ||
| There are several hashtable implementations in the code archives. I've some speed tests and the one by 'Otus' is the fastest. |
| ||
| Let me get more detailed. Let's say on my game level I have a list of 10000 game objects but I only need to draw 200 of them depending on where the user is looking in the game world. When I add an object to that list I save the link for deleting purposes. Rather than iterate through that entire list to find a few hundred objects, which may even be a higher count depending on the level, I was thinking of creating an array that will hold the link of each object, saving the link when the object is created. For example, if the user is at X, Y in the game world, I can just plug that same number into an array, pull out the link and get the object. Am I being overly complicated here or is there really no benefit to doing it this way? |
| ||
| The other idea I had is keeping an array of object indexes. I will have to sort this list, so I would keep two lists, one original and one that gets sorted. As I create the object and add it the original list, I'll add that index to an array. When I need to pull out the objects needed, just refer to the aray to get the indexes, pull the needed objects into a new list and sort that. |
| ||
| I can just plug that same number into an array, pull out the link and get the object. I'm not seeing why you would do this instead of just ignoring the list and putting the objects into the array, if you really want to access them by index. As TomToad said above, objects can be referenced from more than one place. If you have some other reason why the objects should be in a list, put them in a list, and also put them in an array if you want to access them by index in an unrelated way. Unless there's a direct connection between the indices and the list (I'm having difficulty understanding this, admittedly), there is no reason for the containers to know about each other. depending on where the user is looking in the game world You might want to investigate a custom container based on quadtrees or octrees (depending on whether you game is 2D or 3D). This is one of those things trees do well - quickly splitting a large collection into "relevant" subgroups based on a kind of ordering. Quadtrees and octrees allow the subgroups to be ordered in a two- or three-dimensional way, respectively (octrees are commonly used in some 3D game engines to determine which surfaces need to be drawn - there's your hint), as opposed to TMap's one-dimensional ordering. |
| ||
| Unless my understanding is completely wrong, an array cell only stores one piece of information, my objects will have a variety of fields attached to it. But I gather from this thread that a separate list for lookup purposes seems to be the way to go. |
| ||
| an array cell only stores one piece of information An array cell holds one value of the type specified for the array, which can be any of the BlitzMax data types. When you assign an object to an array, the four-byte pointer to the object is what is stored. In literal/technical terms, the array is an array of pointers (in the same way that all lists are lists of pointers). In useful terms, both arrays and lists can hold objects of any type, built-in or user-defined. TLinks are objects themselves, so an array of those would be mechanically identical to an array of your particular objects. If you don't fully understand objects being passed by-reference (i.e. objects are only created with "New": if you create an object, stick it in varA, then do "varB = varA", you have one object referenced by two variables, not two objects), then working with custom containers is a far more advanced topic than you need to be studying right now. If an object could only ever exist in one place, BlitzMax would have no need for a garbage collector, among other things. ...anyway, have you actually tested this? The golden rule of programming is that "premature optimisation is the root of all evil". You should always design your program with the simplest possible algorithms and structures, then profile it to find out where the hot spots are (always test: programmers are famously bad at guessing this), and then optimise those spots only. It's far more important to make your code work, and then to work right, before you make it work right-and-fast (and if it's not right, fast is irrelevant). It's also entirely possible that a list is perfectly adequate for your needs: Blitz3D internally uses only a linked list for its scene management, and is blazingly fast despite that. Last edited 2012 |
| ||
| Lol Yasha that is awesome advice and I should listen to it. I'm very guilty of that, I know how to complete a task, but than I always think how do I write it the first time around and prepare for every scenario making my thought process much more complicated. I do have another question on the same topic that I had trouble with it before. How do I retrieve an object from a list with a link? |
| ||
| The golden rule of programming is that "premature optimization is the root of all evil". I disagree! When you writing a game that can potentially be pushing a lot of sprites you need to have a detailed understanding of everything that's eating your framerate. It's very worth while to think well before implementing something about the effect it will have on performance. not doing so cause you to end up coding yourself into a corner where refactoring the game for performance would cause you to rip the whole renderer apart. In my current engine a map can contain massive amount of objects, but only need to draw a portion of that on screen. Arrays would be way to go because of the iteration speed, but because objects get added and removed at runtime, arrays are not possible because missing values prevent depth sorting. The way I did it was use one linked list to hold all of the objects and another to only hold objects within the boundaries of the screen. Anytime the camera is rotated or translated. the drawlist is wiped and refilled from the objlist, then z-sorted. Also this does not have to happen every frame in case your drawlist also contains a huge number of objects. it can be set on a timer or however you want. Whenever you have a chance to spread some task over multiple frames it helps a lot. Here is a small vid (2mb) of my testbed. In the video, of the 14k objects on the map only a few thousand are drawn as needed. You can actually see 2 numbers at the top-left. one is the total object count and the other is drawlist count. Currently the testbed never falls below 1500 fps because premature optimization can pay off. |
   |