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

Chroma

(Posted 2010) [#1]

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?

Dreamora

(Posted 2010) [#2]

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.

_Skully

(Posted 2010) [#3]

separate the TLists create an array element of them for each object ID


Const 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)

jpavel

(Posted 2010) [#4]

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.

Chroma

(Posted 2010) [#5]

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?

Zeke	(Posted 2010) [#6]

SuperStrict

Type myobject
	Global list:TList=New TList
	Global IDS:TLink[1000] 'max ID
	
	Field id:Int
	
	function GetByID:myobject(IID:Int)
		Return myObject(IDS[IID].value())
	End function
	
	Method addlast()
		ids[id] = list.addlast(Self)
	End Method
End Type

'Add objects
For Local i:Int=0 To 100
	Local obj:myobject = New myobject
	obj.id = i
	obj.addlast()
Next

Print "object count=" + myobject.list.count()

For Local i:Int = 0 Until myobject.list.count()
	Local obj:myobject = myobject.getbyid(i)
	If Not obj Then Print "Null object" ; End
	Print "Object " + i + "# id=" + obj.id
Next

this is also one way to get object using ID.
as you can see this is not suitable if you have millions of objects

Dreamora

(Posted 2010) [#7]

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

GfK	(Posted 2010) [#8]

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

Midimaster

(Posted 2010) [#9]

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

Kurator

(Posted 2010) [#10]

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

ziggy

(Posted 2010) [#11]

You could also use a hashtable or a key/value pair collections if there where implemented in Max... TMap are your best friends.

Chroma

(Posted 2010) [#12]

Awesome. This thread combined with this thread: http://www.blitzbasic.com/Community/posts.php?topic=79711#896976 really cleared it up.

Chroma

(Posted 2010) [#13]

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

Jesse

(Posted 2010) [#14]

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.

Gabriel

(Posted 2010) [#15]

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.

Chroma

(Posted 2010) [#16]

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