Fastest way to find an specific object in a TList
BlitzMax Forums/BlitzMax Beginners Area/Fastest way to find an specific object in a TList
| ||
Let's say I have a TList of Objects and there's a field called ID. If I want to find Object ID 3 (and all the objects are scrambled in the TList). What's the fastest most direct way of returning ID 3 without having to cycle through them in a loop? |
| ||
There is none unless you stored a reference outside. lists have no direct access as they don't want to have one to be able to add / remove objects on the fly as fast as possible. if you need indexed access, then an array would be the appropriate way to go. |
| ||
separate the TLists create an array element of them for each object IDConst TotalIDs:Int=3 Type it global list[TotalIDs]:Tlist field x:int=0 field id:int=0 Method New() for local s:int=0 to TotalIDs-1 list[s]=new Tlist next End Method End Type I:IT=new IT I.List[0].AddLast(I) |
| ||
You can use a Map to store your objects and retrieve them by some key (see the docs for TMap). In your custom type, override the Compare() method to compare the ID fields. ex.Method Compare:Int( withObject:Object ) Local other:TMyObject = TMyObject(withObject) If ID < other.ID Return -1 ElseIf ID > other.ID Return 1 Else Return 0 EndIf End Method Finding a specific object in a Map is much quicker than looping through a whole List. |
| ||
Hmm....what I'm trying to do is have my cake and eat it too. For instance. I want to be able to cycle through a list when I do broadcasts but also be able to access the object directly via a key. Is a map suitable for such operations? @ Dreamora: How about using both an array and a list. The array would provide direct access and the List and would allow a quick way to apply a method to a specificl object. In a list, an objects index # would change as a player was removed. So I clearly can't use a list for direct access. But if I had an array of say 16 (0-15) and inputted the type (player id) into the specific array and just added it to the list....when I needed direct access I go to the array...when I need to cycle through I go to the list. Sound feasible? |
| ||
this is also one way to get object using ID. as you can see this is not suitable if you have millions of objects |
| ||
if you don't need the lists, the straight forward way would be TMaps and using the ID (or a string from it) as key |
| ||
For instance. I want to be able to cycle through a list when I do broadcasts but also be able to access the object directly via a key. Is a map suitable for such operations? That's precisely what TMaps are for. As well as retrieving data based on a key, there's also an enumerator so you can easily use For/Eachin.Strict 'crate a new tmap Local myMap:TMap = New tMap 'some stuff for the enumerator Local key:String Local value:String 'add some values mymap.insert("pig","oink") mymap.insert("dog","woof") mymap.insert("cow","moo") mymap.insert("frog","ribbit") mymap.insert("sheep","baa") 'show two individual values by providing a key Print "**INDIVIDUAL KEYS**" Print "Sheep says " + String(mymap.valueforkey("sheep")) Print "Dog says " + String(mymap.valueforkey("dog")) 'show all Print "**SHOW ALL**" 'note how the results are in alphabetical order, ordered by 'key' For key = EachIn myMap.keys() value = String(myMap.valueforkey(key)) Print key + " says " + value Next |
| ||
perhaps this solution is too simple for you:Type MyType Field Name$ Field No% Global Number% Global MyTypes:TList=New TList Function Create(Name$) Local locT:MyType = New MyType locT.No = Number locT.Name=Name Number=Number +1 MyTypes.addlast locT End Function Function Element:MyType(Nr%) For locT:MyType = EachIn MyTypes If locT.No=Nr Then Return locT EndIf Next Return Null End Function Method DoIt() print "do it" End Method End Type MyType.Create("Tarzan") MyType.Create("Jane") Print MyType.Element(1).Name MyType.Element(1).DoIt |
| ||
I had some kind of a crazy idea to combine those two things (TMap, TLink) together and created the TMapList :D Advantages: Fast search by key values, but also fast Iteration over the Objects like the linked list. Disadvantage: More overhead in adding and removing items, and slightly more memory needed The trick is, that the map stores the keys and the TLinks to to the value objects. Its not complete, many Methods of the TList Interface are missing, but feel free to complete it. SuperStrict Type TMapList Field _map:TMap Field _list:TList Function Create:TMapList() Local mapList:TMapList = New TMapList Return mapList EndFunction Method New() _map = New TMap _list = New TList EndMethod Method AddLast:TLink(key:Object, value:Object) Local link:TLink = _list.AddLast(value) _map.Insert(key, link) Return link EndMethod Method AddFirst:TLink(key:Object, value:Object) Local link:TLink = _list.AddFirst(value) _map.Insert(key, link) Return link EndMethod Method RemoveByKey(key:Object) Local link:TLink = TLink(_map.ValueForKey(key)) If link <> Null link.Remove() EndIf EndMethod Method ValueForKey:Object(key:Object) Local link:TLink = TLink(_map.ValueForKey(key)) If link <> Null Return link._value EndIf Return Null EndMethod Method keys:TMapEnumerator() Return _map.Keys() End Method Method ObjectEnumerator:TListEnum() Return _list.ObjectEnumerator() End Method EndType 'crate a new tmap Local myMap:TMapList= New TMapList 'some stuff for the enumerator Local key:String Local value:String 'add some values mymap.AddLast("pig","oink") mymap.AddLast("dog","woof") mymap.AddLast("cow","moo") mymap.AddLast("frog","ribbit") mymap.AddLast("sheep","baa") 'show two individual values by providing a key Print "**INDIVIDUAL KEYS**" Print "Sheep says " + String(mymap.valueforkey("sheep")) Print "Dog says " + String(mymap.valueforkey("dog")) 'show all Print "**SHOW ALL**" 'note how the results are in alphabetical order, ordered by 'key' For key = EachIn myMap.keys() value = String(myMap.valueforkey(key)) Print key + " says " + value Next For value = EachIn myMap value = String(value) Print " value: " + value Next Print "removing oink.." mymap.RemoveByKey("pig") For value = EachIn myMap value = String(value) Print " value: " + value Next |
| ||
You could also use a hashtable or a key/value pair collections if there where implemented in Max... TMap are your best friends. |
| ||
Awesome. This thread combined with this thread: http://www.blitzbasic.com/Community/posts.php?topic=79711#896976 really cleared it up. |
| ||
Ok here's what I came up with. How fast is this compared to direct access with an Array and iterating through a TList?Local map:TMap = CreateMap() For i = 1 To 4 Local player:TPlayer = TPlayer.Create( i ) Map.Insert(String(player.id),player) Next 'Direct Access Local temp:TPlayer = TPlayer( Map.ValueForKey( String(3) ) ) Print "Direct Access" Print "This is Player 3: " + temp.id Print 'Iterating Through the TMap Local id:String, p:TPlayer Print "Iteration" For id = EachIn map.keys() p = TPlayer(map.valueforkey(id)) Print p.id Next End Type TPlayer Field id% Function Create:TPlayer(id:Int) Local p:TPlayer = New TPlayer p.id = id Return p End Function End Type End |
| ||
this will never be as fast as direct access with arrays. I don't know too much about Tmaps but I am willing to bet that Tmap gets alot slower with large quantity of items compered to arrays. My reasoning is that it still have to search through the map for the item(in a somewhat efficient way) but none the less it still has to search. Then again, if you are not planing to use it for say more than 100 items there might not be a noticeable difference. |
| ||
Someone really should write a BlitzMax container class which works like C++ Vectors or .Net Arraylists. I won't go into all the details on how these are implemented, but they're essentially arrays and can be indexed as arrays are, but adding and removing elements is "managed" so that indices are assigned as required and the arrays are not resized every time you add or remove an entry. One advantage with vectors is that you have more control over resizing them, and it would be good to borrow that benefit, as resizing arrays is not a fast operation. TMaps are great, but they really serve a different purpose, and indexing via a key is necessarily going to be slower than pure array-style integer indexing. |
| ||
Update: In the end, Zeke's code won me over. It let's me keep the ultra fast iteration and also let's me grab a player by ID when needed. Opinions? And btw, thanks all. Here's the code (which is basically identical to his): Local server:TServer = TServer.Create(8) For i = 0 To 7 server.AddPlayer(TPlayer.Create(i)) Next 'Get Player 5 Local temp:TPlayer = server.GetPlayerByID(5) Print "Player ID: " + temp.id End Type TServer Field maxplayers:Int Field PlayerList:TList Field PlayerLink:TLink[] Function Create:TServer(maxp:Int) Local server:TServer = New TServer server.maxplayers = maxp server.PlayerList = New TList server.PlayerLink = New TLink[maxp] Return server End Function Method AddPlayer(player:TPlayer) Self.PlayerLink[player.id] = Self.PlayerList.AddLast(player) End Method Method GetPlayerByID:TPlayer(id:Int) Return TPlayer(Self.PlayerLink[id].value()) End Method End Type Type TPlayer Field id:Int Function Create:TPlayer(id:Int) Local player:TPlayer = New TPlayer player.id = id Return player End Function End Type |