Finite Loop faster alternative? - GameCreators Forum

Author

Message

luskos

19

Years of Service

User Offline

Joined: 28th Jun 2007

Location:

Posted: 22nd May 2010 12:23

Link

Hello.

What i`m looking is something to replace the finite loop "for-next",because it`s good for searching trough defined range but it goes slower while range goes bigger.

If the number of elements for searching are in range 100,1000,10000 and even 100000 it`s not a problem, but what if they are 1000000?

In other words what could be the best way to find a needle in a haystack?

Where there is a will, there is a way.
I often edit my posts, that`s who i am

Back to top

Profile PM

Van B

Moderator

23

Years of Service

User Offline

Joined: 8th Oct 2002

Location: Sunnyvale

Posted: 22nd May 2010 12:57

Link

It's unavoidable really, your always gonna need the recursive loops - the best you can do is optimise them.

For instance, if you optimise an array so that any unused entries are replaced with used ones. Like an array of enemy information, if you have a dead enemy in there, don't do anything with the data, but when you find a live enemy in there, replace the dead 'slot' with the live enemy data. If you can get through the actual data quicker by ensuring that the array replaces those empties, then you only have to for...next through the valid entries. I would keep a record of the maximum array index, for next to that, increase it to suit any new enemies, and optimize while stepping through.

Indexes can be used to good effect as well - like rather than scanning through an array to find a free 'slot' - have an array of free slots - when you kill an enemy, add it's ID to an array and use that the next time you need a free 'slot'.

I'm sure there's a good example by Sasuke on this sort of thing in code snippets.

Health, Ammo, and bacon and eggs!

Back to top

Profile PM Email

luskos

19

Years of Service

User Offline

Joined: 28th Jun 2007

Location:

Posted: 22nd May 2010 13:12

Link

Ok, understand what you say.Very informative.I`ll try to implement this when i need it.I`ll look for Sasuke`s snippets.

Thanks a lot.

Where there is a will, there is a way.
I often edit my posts, that`s who i am

Back to top

Profile PM

Sasuke

20

Years of Service

User Offline

Joined: 2nd Dec 2005

Location: Milton Keynes UK

Posted: 22nd May 2010 14:02 Edited at: 22nd May 2010 14:08

Link

Quote: "I'm sure there's a good example by Sasuke on this sort of thing in code snippets."

Hmm... Not me I think. But I did do stuff on arrays in multiple threads. 'Array Bounds' was it? not sure. I'll have a look around.

Edit, OK, not 'Array Bounds'. Hmm... where could it be I wonder

A dream is a fantasy, if you achieve that fantasy it was never a dream to begin with.

Back to top

Profile PM Email

Sasuke

20

Years of Service

User Offline

Joined: 2nd Dec 2005

Location: Milton Keynes UK

Posted: 22nd May 2010 14:12

Link

luskos, Quick question, what would you need an array this big for or where you just wondering, cause 1000000 is pretty big.

A dream is a fantasy, if you achieve that fantasy it was never a dream to begin with.

Back to top

Profile PM Email

luskos

19

Years of Service

User Offline

Joined: 28th Jun 2007

Location:

Posted: 22nd May 2010 15:59

Link

I don`t need that big i yet,just pointed this number you can pick some other number...I`m not sure what could of require this big array but i wanted to clear few things...

Where there is a will, there is a way.
I often edit my posts, that`s who i am

Back to top

Profile PM

Kevin Picone

23

Years of Service

User Offline

Joined: 27th Aug 2002

Location: Australia

Posted: 22nd May 2010 16:34 Edited at: 23rd Aug 2010 00:20

Link

Quote: "In other words what could be the best way to find a needle in a haystack?"

By arranging our data set better, so that we can avoid brute force searching it.

These types of problems don't only occur when we're searching hundreds of thousands of items though, you're just as likely to run into them, during nested loops.

A pretty common example that comes to mind in a lot of games, might be where we're comparing a list of say 100 bullets to 100 bad guys.

So the logic might look a bit like this.

+ Code Snippet


   For Bullet=1 to 100

      for BadGuy =1 to 100

          If  ThisBullet hits This badguy
               Kill bad guy
          endif

      next

   next

This type of nested structure means that the inner code is executing (100*100) 10000 times. The more active bad guys or bullets in the scene, then slower this loop is going to get. While we could perhaps pick a faster looping control and shave some time off the top, this really doesn't address the underlying problem. Which this structure can simply produce too many iterations.

There's a number of way to solving this particular example, such as partitions, sorting etc. My point being, that if we better structure our information, we can reduce the impact of the brute force searching.

Anyway, what exactly are you trying to do ?

New PlayBasic Learning Edition Released 24th April 2010

Back to top

Profile PM Website

Sasuke

20

Years of Service

User Offline

Joined: 2nd Dec 2005

Location: Milton Keynes UK

Posted: 22nd May 2010 16:40

Link

Well depending on what's in the array, say a list of entities, you'd first sort the array using a recursive function to get everything into order, say by type. Then create type pointers (index reference) to the first index of each type. That way you only need to search from the type your looking for and not every single type before you find the item you wanted. Just search the type you want from the pointer until you hit a different type or hit the end of the array.

Just in case you haven't encounter a recursive function before, here's an example of one that sorts resolutions in an order:

type udt_Resolution
   width as integer
   height as integer
   depth as integer
endtype

sDisplayMode as string
width as integer
height as integer
depth as integer

global dim _SystemRes() as udt_Resolution

// sort all resolutions
perform checklist for display modes 
    for n = 1 to checklist quantity()
        sDisplayMode = checklist string$(n)
        width  = val( first token$( sDisplayMode ,chr$(120) ) )
        height = val( next token$( chr$(120) ) )
        depth  = val( next token$( chr$(120) ) )
        array insert at bottom _SystemRes()
            _SystemRes().width  = width 
            _SystemRes().height = height
            _SystemRes().depth = depth
    next n
empty checklist

SortSystemRes()

// print sorted array
for n = 0 to array count(_SystemRes())
    print str$(_SystemRes(n).width) + "x" + str$(_SystemRes(n).height) + "x" + str$(_SystemRes(n).depth) `+"x"+_SystemRes(n).depth
next n

wait key
end

// Sort resolutions into decending order (Reclusive Function)
function SortSystemRes()

local temp as udt_Resolution
   
   for n = 1 to array count(_SystemRes())
   
      // check to see if the width is greater than last width and switch them 
      if _SystemRes(n).width > _SystemRes(n-1).width     
         temp = _SystemRes(n) : _SystemRes(n) = _SystemRes(n-1)
         _SystemRes(n-1) = temp : SortSystemRes()      
      endif
      
      // if there are any widths of the same value, check to see if the height
      // is greater than last height and switch them
      if _SystemRes(n).width = _SystemRes(n-1).width
         if _SystemRes(n).height > _SystemRes(n-1).height
            temp = _SystemRes(n) : _SystemRes(n) = _SystemRes(n-1)
            _SystemRes(n-1) = temp : SortSystemRes()            
         endif   
      endif    
          
   next n
   
endfunction

+ Code Snippet

type udt_Resolution
   width as integer
   height as integer
   depth as integer
endtype

sDisplayMode as string
width as integer
height as integer
depth as integer

global dim _SystemRes() as udt_Resolution

// sort all resolutions
perform checklist for display modes 
    for n = 1 to checklist quantity()
        sDisplayMode = checklist string$(n)
        width  = val( first token$( sDisplayMode ,chr$(120) ) )
        height = val( next token$( chr$(120) ) )
        depth  = val( next token$( chr$(120) ) )
        array insert at bottom _SystemRes()
            _SystemRes().width  = width 
            _SystemRes().height = height
            _SystemRes().depth = depth
    next n
empty checklist

SortSystemRes()

// print sorted array
for n = 0 to array count(_SystemRes())
    print str$(_SystemRes(n).width) + "x" + str$(_SystemRes(n).height) + "x" + str$(_SystemRes(n).depth) `+"x"+_SystemRes(n).depth
next n

wait key
end

// Sort resolutions into decending order (Reclusive Function)
function SortSystemRes()

   local temp as udt_Resolution
   
   for n = 1 to array count(_SystemRes())
   
      // check to see if the width is greater than last width and switch them 
      if _SystemRes(n).width > _SystemRes(n-1).width     
         temp = _SystemRes(n) : _SystemRes(n) = _SystemRes(n-1)
         _SystemRes(n-1) = temp : SortSystemRes()      
      endif
      
      // if there are any widths of the same value, check to see if the height
      // is greater than last height and switch them
      if _SystemRes(n).width = _SystemRes(n-1).width
         if _SystemRes(n).height > _SystemRes(n-1).height
            temp = _SystemRes(n) : _SystemRes(n) = _SystemRes(n-1)
            _SystemRes(n-1) = temp : SortSystemRes()            
         endif   
      endif    
          
   next n
   
endfunction

Don't think you need an example of the searching part, that's the easy part.

A dream is a fantasy, if you achieve that fantasy it was never a dream to begin with.

Back to top

Profile PM Email

Zotoaster

21

Years of Service

User Offline

Joined: 20th Dec 2004

Location: Scotland

Posted: 22nd May 2010 17:30 Edited at: 22nd May 2010 17:38

Link

As many have said, it comes down to the type of data you want to store and how to store it. If you're just storing numbers, store them sequentially and do a binary search, or using a binary search tree (BST). Look these up on wikipedia, or just shout if you don't understand.

The simplest way to explain optimization is to say that you don't just try and cut down the number of operations per loop, but you try and cut out as much of the loop as possible.

With Kevin's example, you don't want to loop 10,000 times just to check if a bullet kills a guy. How can you cut this down? Well a good example would be to split your area into 2 blocks (completely theoretical of course - not actually using objects). You know that if one enemy is in one block and the bullet is in the other, there's no way the bullet is going to hit this enemy. So you can ~half the number of enemies you need to search. You can split this block into two smaller ones, and keep splitting and splitting until they are sufficiently small, but not too small, each time only checking each block. That means that even if you have 1000 enemies, it'll only take maybe 5 loops to check if you are hitting one. This is called logarithmic complexity. Look up complexity analysis on Wikipedia too, and of course just ask if it doesn't make sense.

[edit]
Another good thing to look into is hash tables. They are essentially arrays but you don't need to search them to find items. The way they work is quite simple. Say you have an array that maps strings to objects (for example, players might have names and object numbers, and you want to get the object number by searching for the name). You could just loop through the array, check the name, and once you've found it, stop the loop and take the object number, or, you could use a hash table.

Hash tables work by not searching for a string, but finding it instantly. The way it works is using this funny thing called a 'hash function'. Very basically, if you give a hash function a string, it'll give you a number (you can do anything really to get a number from the string, for instance, add the ASCII codes of all the characters, and then make sure the result is smaller than your array (by 'modding' it)). Simple really. When you want to add an entry to an array, you don't just stick it in the end, but you put the string through the hash function, and it'll give you an array index to put it in (Warning: some indices might clash and you'll have to resolve this). When you want to find the entry, you don't search for it, but you simply just put the string through the hash function again, and it'll tell you exactly where it was put in the array. Pretty clever eh? Of course the arrays will have lots of empty spaces in them, and you'll have to create quite big ones to start with, but they're still cool.

"everyone forgets a semi-colon sometimes." - Phaelax

Back to top

Profile PM Email

IanM

Retired Moderator

23

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 22nd May 2010 22:36

Link

@Van,
I think you are remembering the combined inuse/freelist idea I put together. Basically the array is split into two halves - the lower half is inuse, and the upper half is free for future use, and you manage the boundary between them.

Here's the simpler one where the order of the items in the array does not matter:

type MyType_T
   Key as integer
   Data1 as integer
   Data2 as float
endtype

global dim MyArray() as MyType_t
set array index MyArray(), -1

PrintArray(0)

AddNewUnordered()
MyArray().Key = 123
AddNewUnordered()
MyArray().Key = 456

PrintArray(100)

RemoveUnordered(0)

PrintArray(200)

AddNewUnordered()
MyArray().Key = 789

PrintArray(300)

wait key
end

function AddNewUnordered()
   next array index MyArray()
   if array index valid( MyArray() ) = 0 then array insert at bottom MyArray(), 10   ` Grow in steps of 10 - tunable
endfunction

function RemoveUnordered(Index as integer)
   swap array items MyArray(), Index, get array index( MyArray() )
   previous array index MyArray()
endfunction

function PrintArray(x as integer)
   local i as integer
   local y as integer

y = 0
   text x, y, "Size: " + str$( array count( MyArray() ) )
   inc y, 15
   text x, y, "Index: " + str$( get array index( MyArray() ) )
   inc y, 30

for i = 0 to get array index( MyArray() )
      text x, y, "+ " + str$(i) + " : " + str$( MyArray(i).Key )
      inc y, 15
   next
   for i = get array index( MyArray() ) + 1 to array count( MyArray() )
      text x, y, "- " + str$(i) + " : " + str$( MyArray(i).Key )
      inc y, 15
   next
endfunction

+ Code Snippet

type MyType_T
   Key as integer
   Data1 as integer
   Data2 as float
endtype

global dim MyArray() as MyType_t
set array index MyArray(), -1

PrintArray(0)

AddNewUnordered()
MyArray().Key = 123
AddNewUnordered()
MyArray().Key = 456

PrintArray(100)

RemoveUnordered(0)

PrintArray(200)

AddNewUnordered()
MyArray().Key = 789

PrintArray(300)

wait key
end


function AddNewUnordered()
   next array index MyArray()
   if array index valid( MyArray() ) = 0 then array insert at bottom MyArray(), 10   ` Grow in steps of 10 - tunable
endfunction

function RemoveUnordered(Index as integer)
   swap array items MyArray(), Index, get array index( MyArray() )
   previous array index MyArray()
endfunction



function PrintArray(x as integer)
   local i as integer
   local y as integer

   y = 0
   text x, y, "Size: " + str$( array count( MyArray() ) )
   inc y, 15
   text x, y, "Index: " + str$( get array index( MyArray() ) )
   inc y, 30

   for i = 0 to get array index( MyArray() )
      text x, y, "+ " + str$(i) + " : " + str$( MyArray(i).Key )
      inc y, 15
   next
   for i = get array index( MyArray() ) + 1 to array count( MyArray() )
      text x, y, "- " + str$(i) + " : " + str$( MyArray(i).Key )
      inc y, 15
   next
endfunction

... and here's the sorted one:

type MyType_T
   Key as integer
   Data1 as integer
   Data2 as float
endtype

global dim MyArray() as MyType_t
set array index MyArray(), -1

PrintArray(0)

AddNewOrdered(123)
AddNewOrdered(456)

PrintArray(100)

RemoveOrdered(123)

PrintArray(200)

AddNewOrdered(789)

PrintArray(300)

wait key
end

function AddNewOrdered(Key as integer)
   local Index as integer

Index = SearchOrdered(Key, 1)  ` find match or insert point

if Index > get array index( MyArray() )
      ` Append
      next array index MyArray()
      if array index valid( MyArray() ) = 0 then array insert at bottom MyArray(), 10   ` Tunable
      MyArray().Key = Key
   else
      if MyArray(Index).Key <> Key
         ` Insert
         next array index MyArray()
         if array index valid( MyArray() ) = 0 then array insert at bottom MyArray(), 10   ` Tunable
         MyArray().Key = Key
         rotate array MyArray(), 1, Index, get array index( MyArray() )
      endif
   endif
endfunction Index

function RemoveOrdered(Key as integer)
   local Index as integer

Index = SearchOrdered( Key, 0 )  ` find exact match only

if Index >= 0
      rotate array MyArray(), -1, Index, get array index( MyArray() )
      previous array index MyArray()
   endif
endfunction

function SearchOrdered(Key as integer, Nearest as integer)
   local High as integer
   local Low as integer
   local Middle as integer

Low = -1
   High = get array index( MyArray() ) + 1

while High - Low > 1

Middle = (High + Low) / 2
      if MyArray(Middle).Key < Key
         Low = Middle
      else
         High = Middle
      endif
   endwhile

if Nearest = 0
      if High > get array index( MyArray() ) then exitfunction -1
      if MyArray(High).Key <> Key then exitfunction -1
   endif
endfunction High

function PrintArray(x as integer)
   local i as integer
   local y as integer

y = 0
   text x, y, "Size: " + str$( array count( MyArray() ) )
   inc y, 15
   text x, y, "Index: " + str$( get array index( MyArray() ) )
   inc y, 30

for i = 0 to get array index( MyArray() )
      text x, y, "+ " + str$(i) + " : " + str$( MyArray(i).Key )
      inc y, 15
   next
   for i = get array index( MyArray() ) + 1 to array count( MyArray() )
      text x, y, "- " + str$(i) + " : " + str$( MyArray(i).Key )
      inc y, 15
   next
endfunction

+ Code Snippet

type MyType_T
   Key as integer
   Data1 as integer
   Data2 as float
endtype

global dim MyArray() as MyType_t
set array index MyArray(), -1

PrintArray(0)

AddNewOrdered(123)
AddNewOrdered(456)

PrintArray(100)

RemoveOrdered(123)

PrintArray(200)

AddNewOrdered(789)

PrintArray(300)

wait key
end






function AddNewOrdered(Key as integer)
   local Index as integer

   Index = SearchOrdered(Key, 1)  ` find match or insert point

   if Index > get array index( MyArray() )
      ` Append
      next array index MyArray()
      if array index valid( MyArray() ) = 0 then array insert at bottom MyArray(), 10   ` Tunable
      MyArray().Key = Key
   else
      if MyArray(Index).Key <> Key
         ` Insert
         next array index MyArray()
         if array index valid( MyArray() ) = 0 then array insert at bottom MyArray(), 10   ` Tunable
         MyArray().Key = Key
         rotate array MyArray(), 1, Index, get array index( MyArray() )
      endif
   endif
endfunction Index


function RemoveOrdered(Key as integer)
   local Index as integer

   Index = SearchOrdered( Key, 0 )  ` find exact match only

   if Index >= 0
      rotate array MyArray(), -1, Index, get array index( MyArray() )
      previous array index MyArray()
   endif
endfunction



function SearchOrdered(Key as integer, Nearest as integer)
   local High as integer
   local Low as integer
   local Middle as integer

   Low = -1
   High = get array index( MyArray() ) + 1

   while High - Low > 1

      Middle = (High + Low) / 2
      if MyArray(Middle).Key < Key
         Low = Middle
      else
         High = Middle
      endif
   endwhile

   if Nearest = 0
      if High > get array index( MyArray() ) then exitfunction -1
      if MyArray(High).Key <> Key then exitfunction -1
   endif
endfunction High




function PrintArray(x as integer)
   local i as integer
   local y as integer

   y = 0
   text x, y, "Size: " + str$( array count( MyArray() ) )
   inc y, 15
   text x, y, "Index: " + str$( get array index( MyArray() ) )
   inc y, 30

   for i = 0 to get array index( MyArray() )
      text x, y, "+ " + str$(i) + " : " + str$( MyArray(i).Key )
      inc y, 15
   next
   for i = get array index( MyArray() ) + 1 to array count( MyArray() )
      text x, y, "- " + str$(i) + " : " + str$( MyArray(i).Key )
      inc y, 15
   next
endfunction

Both rely on my plug-ins for identifying where the boundary between inuse and free array items is, and for fast swapping/shifting of items within the array

Utility plug-ins collection (updated 02 Mar 2010) and
http://www.matrix1.demon.co.uk

Back to top

Profile PM Email Website

Neuro Fuzzy

19

Years of Service

User Offline

Joined: 11th Jun 2007

Location:

Posted: 22nd May 2010 23:27

Link

didn't read over any post but the first, so excuse meh if this has already been covered, or isn't applicable, but...:

for a computer, doing lots of anything will be big. If you have a faster loop that goes fine for 1000000 elements, it probably still wont for say 100000000 elements.

If you want to search through a giant array, the best thing is usually to keep it sorted in some way. Check out ianM's matrixutils for a nice sort function, or program your own quicksort or the like, and make sure the array stays sorted whenever you add elements. Then, you can use a binary search (pick the element in the middle, and if the one you're looking for is greater, search the right half, if it's less, search the left half, and repeat), and you can find the element really quickly.

Back to top

Profile PM Email

IanM

Retired Moderator

23

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 23rd May 2010 00:06

Link

Just an extra note on Neuro Fuzzy's suggestion - if you take a look at the second piece of code that I posted, you'll find a ready-written binary search routine that you can use.

Utility plug-ins collection (updated 02 Mar 2010) and
http://www.matrix1.demon.co.uk

Back to top

Profile PM Email Website

luskos

19

Years of Service

User Offline

Joined: 28th Jun 2007

Location:

Posted: 23rd May 2010 19:47

Link

It goes harder to follow

Everything including sorting is clear and thanks to Ian and it`s great plugin this is no bother anymore

About binary search.Let see if i understand it well.

Metaphoricly speaking the binary searh is like metal detector and we use it for our haystack to find the needle.But the haystack is too big.So we divide it by half and search only one half.If it`s not there we pick 2nd and divide it by half again and so on.Until we find the needle.

The example is not best suited because fast search of a needle for real is involved with some luck which do not apply for programs and computers.

Where there is a will, there is a way.
I often edit my posts, that`s who i am

Back to top

Profile PM

IanM

Retired Moderator

23

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 23rd May 2010 23:00

Link

That metaphor doesn't quite work because a haystack isn't sorted, and it's the sorting that gives you the ability to decide which half of the array that the item you want is in.

But it'll do

Utility plug-ins collection (updated 02 Mar 2010) and
http://www.matrix1.demon.co.uk

Back to top

Profile PM Email Website

luskos

19

Years of Service

User Offline

Joined: 28th Jun 2007

Location:

Posted: 24th May 2010 08:48

Link

Then another example.The routine is like a man approving people for job, but there he needs one man.If we say there are 1000 people.500 women and 500 men.He sort them by this criteria and he know that he need a man, so the women go home.He sort again by their strenght, half of the men are strong other half not, go home.He sort by height, and so on and so on...until there is our guy getting the job

This is more suitable i think, but anyway i get the idea.

I read an article in wikipedia about linear and binary searches.
It`s quite simple actually.If i forget something allways can come by to refresh my memory in this thread.

I hope all this can help someone else to understand the methods.

Thank you all for the help to the nice guys.

Where there is a will, there is a way.
I often edit my posts, that`s who i am

Back to top

Profile PM

Van B

Moderator

23

Years of Service

User Offline

Joined: 8th Oct 2002

Location: Sunnyvale

Posted: 24th May 2010 14:36

Link

Yeah, that does ring a bell Ian. I also think that Lee posted some tips for this stuff in one of the newsletters (a while ago now though, maybe 8 months).

The main thing with these techniques is that you have to make them your own - they have to suit the particular data set that is being used by the developer. So it's best to concentrate on understanding the techniques, then applying those to your own code. For example there might be some benefit in storing data just for indexing. If you understand it, then you can optimize it to suit your own needs and get maximum benefit.

Health, Ammo, and bacon and eggs!

Back to top

Profile PM Email

Sorry your browser is not supported!

DarkBASIC Professional Discussion / Finite Loop faster alternative?