Searching Type Lists

Blitz3D Forums/Blitz3D Beginners Area/Searching Type Lists

pc_tek

(Posted 2010) [#1]

Is there an efficient way of searching through 1000's of types for a specific value?

Or just do it the easy and ineffient way of going through them all to find it?

stanrol

(Posted 2010) [#2]

there isn't

xtremegamr

(Posted 2010) [#3]

1000's of types

o.O
That is a LOT of types...

The answer to your question depends on what kind of data you're working with. Can you organize these types into some sort of tree?

pc_tek

(Posted 2010) [#4]

I don't mean lots of types...as in different types.

It's one type with 1000's of slots.

If I had the type...

Type alphabet
     field letter$
end type

How would I find the letter 'm' without the standard for...next loops?

Leon Drake

(Posted 2010) [#5]

oops

Leon Drake

(Posted 2010) [#6]

@stanrol wrong.

there is a way to use list types in b3d here is an example


global Bulletlist.Tlist = New tlist
global bullet.MyBullet = new MyBullet

bullet\parentlink = ListAddLast(Bulletlist,Object(bullet))


local mylist.TList = Bulletlist


repeat
 ;check your objects here
 bullet = MyBullet(mylist\TObject)

 if bullet <> null and bullet\x = 10 then ;or whatever means you need to identify that type could go here
 
   ListRemove(bullet\paretlink)
   delete bullet

 endif

 mylist = mylist\next
until mylist = Bulletlist


Type TList

  field Next.TList
  field Previous.TList
  field TObject.Object

End Type


Type MyBullet

  field x,y,x
  field parentlink.Tlist ; good idea to make it faster
end type


function ListRemove(link.TList)

  link\next\previous = link\previous
  link\previous\next = link\next
  delete link

end function

Function ListAddLast.Tlist(list.TList,TObject.Object)

  newlist.TList = new Tlist
  if list\previous = null then
    list\previous = newlist
    list\next = newlist
    newlist\next = list
    newlist\previous = list
    newlist\TObject = TObject
    return newlist
  else
    list\previous\next = newlist
    newlist\previous = list\previous
    newlist\next = list
    list\previous = newlist
    return newlist
  endif
  

end function

well as an example i haven't tested it cause i am busy with my kids at the moment, but its an alternative way of grouping type lists together without having to iterate through thousands of them,

hope this helps

pc_tek

(Posted 2010) [#7]

Thanks Leon...this gives me a few ideas :)

stanrol

(Posted 2010) [#8]

did Mark Sibly code B3D in Delphi ? TList reminds me of.

xtremegamr

(Posted 2010) [#9]

@Leon Drake: That code looks like a doubly-linked list, which is what Blitz uses internally for looping through types. How will that make searching through a list of types faster than just using a For...Each loop?

@stanrol: I'm pretty sure he coded it in C++; the geometry code for B3D that he posted a while back is in C++.

Leon Drake

(Posted 2010) [#10]

I would imagine it would be much faster iterating through a dynamically expandable list that only contains only a set amount of the types you want to check throug rather than using a for loop and iterating through every single object of that type that has been created.

for instance if i made 8000 chair objects, and some random amount of them are red green and blue. i dont know the exact number of the amount that are each color because they are created randomly and are destroyed

if i added each color to a different list then i could break down my search more for a specific item instead of searching through all 8000 of them

Adam Novagen

(Posted 2010) [#11]

You'd still have to go through all 8,000 at some point or other. Even databases, with their quick and efficient search techniques, have to go through all the contents once to compile their "index."

However, I can tell you that, if we're just talking raw number crunching for now, B3D can quite easily handle over 20,000 types without dropping below 60FPS, even on an old (like a 750MHz PIII) CPU.

Leon Drake

(Posted 2010) [#12]

@adam i dunno why but having to iterate through every object in a type seems like bad programming IMO

xtremegamr

(Posted 2010) [#13]

You'd still have to go through all 8,000 at some point or other...

Yeah, you may have to do that at some point, but you could do this during a loading screen in your game. Using Leon's chair example, you could create all of your chair types, then loop through them, adding each chair to a list based on color.

I'm not sure if the performance gains would be worth all the extra work, though.

@adam i dunno why but having to iterate through every object in a type seems like bad programming IMO

Meh. I think that's more of an opinion; I loop through every object in a type all the time. Then again, I'm not usually dealing with more than 100 objects.

Serpent

(Posted 2010) [#14]

@adam i dunno why but having to iterate through every object in a type seems like bad programming IMO

It depends on what you're trying to do. Most of the time, you can loop through entire object lists each frame and maintain an FPS of 60.
There are times though when looping through every object in a list would be a bad idea. For example, in an SPH program (Smoothed-Particle-Hydrodynamics), if you go through an entire list (of potentially 100s or 1000s or objects) to find particles that are close to each other then performance would be drastically decreased. In this case, it's a good idea to do keep the particles sorted in the list or in your own array or something so you don't have to look through as many of them.

This would apply to your situation. If you have a 2D array, you could store the handles to types in it. I.e. along one dimension the values could correlate with the values in the types, the second dimension is just for storing multiple types. I hope the following example illustrates it:

Complete Iteration:

Graphics 800,600,16,2
SetBuffer BackBuffer()

;The test type
Type MyType
	
	Field MyNum
	Field MyInfo$
	
End Type

;This character list is used to assign 'random' strings to different types,
;demonstrating that all different values can be extracted from types which
;is relevant when using the array-based search approach.
Const Charlist$ = "absdafjweifapqweofwiefjawecmawoeifjas123451235efvoeafmoae80asdf7098asdfasdifjaweofjoawemcowapifejwoejwaerf7e9faw423909r2jaewfaiejw90ja93jaewoijaf90fj4w93iawl3feaf"

;Initialise necessary variables.  For those of you who insist on SuperStrict code :)
Local number, amount, value, i, i2, SearchType.MyType, FoundType.MyType, time

;Create all of the types.  They will be in order by value, but the searching
;code will work regardless of their order.
;A random amount of each value type will be created.
For value = 0 To 10000
	
	amount = Rand(50,200)
	
	For i = 1 To amount
		
		SearchType = New MyType
		SearchType\MyNum = value
		;Assign a 'random' string to the MyInfo field
		SearchType\MyInfo = Mid$(Charlist, amount-49, 10)
		
	Next
	
Next


While Not KeyHit(1)
	
	Print
	Print
	Print "Please enter a value to search for:"
	value = Int(Input$(">> "))
	
	;Just a simple iteration through each object.  The other example will
	;show how to optimise this with an array.
	time = MilliSecs() ;It's timed :)
	amount = 0
	For SearchType = Each MyType
		
		If SearchType\MyNum = value Then
			
			amount = amount + 1
			FoundType = SearchType
			
		EndIf
		
	Next
	time = MilliSecs() - time
	
	;Display info from the search
	Print
	Print "The search took " + Str$(time) + " milliseconds."
	Print Str$(amount) + " objects with the value of " + Str$(value) + " were found."
	If amount > 0 Then
		Print "The last object's 'MyInfo' field was:"
		Print FoundType\MyInfo
	EndIf
	Print
	Print "Press any key to search again or escape to exit..."
	
	FlushKeys
	WaitKey
	
Wend

End

Using a 'Search Array':

Graphics 800,600,16,2
SetBuffer BackBuffer()

;The test type
Type MyType
	
	Field MyNum
	Field MyInfo$
	
End Type

;This character list is used to assign 'random' strings to different types,
;demonstrating that all different values can be extracted from types which
;is relevant when using the array-based search approach.
Const Charlist$ = "absdafjweifapqweofwiefjawecmawoeifjas123451235efvoeafmoae80asdf7098asdfasdifjaweofjoawemcowapifejwoejwaerf7e9faw423909r2jaewfaiejw90ja93jaewoijaf90fj4w93iawl3feaf"

;Initialise necessary variables.  For those of you who insist on SuperStrict code :)
Local number, amount, value, i, i2, SearchType.MyType, FoundType.MyType, time

;Create all of the types.  They will be in order by value, but the searching
;code will work regardless of their order.
;A random amount of each value type will be created.
For value = 0 To 10000
	
	amount = Rand(50,200)
	
	For i = 1 To amount
		
		SearchType = New MyType
		SearchType\MyNum = value
		;Assign a 'random' string to the MyInfo field
		SearchType\MyInfo = Mid$(Charlist, amount-49, 10)
		
	Next
	
Next


While Not KeyHit(1)
	
	Print
	Print
	Print "Please enter a value to search for:"
	value = Int(Input$(">> "))
	
	;Just a simple iteration through each object.  The other example will
	;show how to optimise this with an array.
	time = MilliSecs() ;It's timed :)
	amount = 0
	For SearchType = Each MyType
		
		If SearchType\MyNum = value Then
			
			amount = amount + 1
			FoundType = SearchType
			
		EndIf
		
	Next
	time = MilliSecs() - time
	
	;Display info from the search
	Print
	Print "The search took " + Str$(time) + " milliseconds."
	Print Str$(amount) + " objects with the value of " + Str$(value) + " were found."
	If amount > 0 Then
		Print "The last object's 'MyInfo' field was:"
		Print FoundType\MyInfo
	EndIf
	Print
	Print "Press any key to search again or escape to exit..."
	
	FlushKeys
	WaitKey
	
Wend

End

If you can be bothered to run the examples, you'll see that the performance varies considerably.
The example that iterates through the complete list takes around 15ms on my PC, but the example which uses a 'Search Array' takes under 1ms for me.

This could apply to what someone's doing. It uses more memory, but it cuts down on the searching considerably and is therefore considerably faster.

There you have it stanrol. Depending on what you need to do, there are ways of optimising type searching :)

xtremegamr

(Posted 2010) [#15]

On my system, the 'Complete Iteration' code takes 16ms, and the 'Search Array' code takes 15ms.

I even tried upping the object count to 100,000 (instead of 10,000), and both searches took 161ms.

What gives?

Ross C

(Posted 2010) [#16]

I think it's from the aspect of optimising your game to run without doing unnessesary things. Like pathfinding. You would split your entire level up, and use choke points, and search each area for the quickest route, rather than the entire level. This will cut down your iterations alot. I've found creating and destroying types to be particulary slow.

Oh and, 15 ms is 60 fps, just for your iterations. You chuck in graphics, pathfinding, game logic etc etc, and it all adds up. 161ms is less than 6 fps, which is useless for a game to do every frame.

Serpent

(Posted 2010) [#17]

On my PC the second example didn't even register as 1ms on the timer... I'll look again...

Serpent

(Posted 2010) [#18]

Running the examples again, i get the same results - Complete Iteration = 15ms, Search Array = 0ms :P

On my PC, when I increased the value count to 100,000 (and therefore the object count to 5,000,000-20,000,000), Windows spent a lot of time reading and writing memory to the cache on the hard drive. I think this really makes the results quite irrelevant. Depending on what was actually in RAM and what was on the Hard Drive, my search times seemed to vary considerably...

On my PC, using the array to search through the types is much faster, and it makes sense - searching through a potential 200 types in an array rather than a potential 2,000,000 types...

Charrua

(Posted 2010) [#19]

hi, probably this collection lib be useful

http://blitzmax.com/Community/posts.php?topic=86730

i coded in this thread an example in blitz3d of use
http://blitzmax.com/Community/posts.php?topic=86730#983964

Juan