Be a Supporter!

AS3: Binary Search

  • 2,538 Views
  • 14 Replies
New Topic Respond to this Topic
matrix5565
matrix5565
  • Member since: Feb. 28, 2006
  • Offline.
Forum Stats
Member
Level 16
Game Developer
AS3: Binary Search Aug. 20th, 2009 @ 09:31 PM Reply

AS3: Main

Intro
|Link to article on Wikipedia|
When you're working with large array's, you often have to search for specific elements. Speed can become an issue if your array's length is in the thousands and it will quickly bog down performance. Binary searches allow you to drastically increase the speed by which you find the information you're looking for. In my testing I found this to be about twice as fast as a Array.indexOf() for very large arrays.

How It Works
Binary searches start with the array's middle element, then, depending on whether the search term is higher or lower than that term, it will move to the appropriate place in the array (higher or lower). You can immediately see why the array MUST BE SORTED for this method to work, otherwise it will likely not find the term.

The Code

function bsearch(array:Array,searchValue:*,sortOption:uint = 16):*
{
	var tempArray:Array = array; //use a temporary array for sorting
	if (sortOption != 0) //a sort option of 0 will assume the array is already sorted
		tempArray = tempArray.sort(sortOption); //else it will sort by the given sort option (explained below)
	
	var b:int = 0;//bottom search index
	var t:int = tempArray.length-1;//top search index
	
	while (b <= t)//as long as the indexes have not crossed
	{
		var index:uint = (b+t)/2//search the middle of the indexes
		
		if (tempArray[index] == searchValue)//have you found the value?
		{
			if (sortOption != 0)//the value was found! If the array was presorted it will return the index, otherwise it will just return true
				return true;
			else
				return index;
		}
		else if (tempArray[index] < searchValue)//if the value checked is lower than the search term, it will check the higher portion
		{
			b = index+1;
		}
		else//otherwise it will check the lower portion
		{
			t = index-1;
		}
	}
	
	if (sortOption != 0)//if the item is never found it will return false or -1 (depending on whether or not the array was already sorted
		return false;
	else
		return -1;
}

For the sortOption use one of the Array sort options, or 0, if you've already sorted it.

Cons
This search method will not find all instances of the term, nor will it return the first or last instance. It will only return the first instance it finds. Also the speed increase will vary greatly depending on where the variable is located.

Conclusion
Thanks for reading, if you have any questions or comments, feel free to post below!

7IsUnlucky
7IsUnlucky
  • Member since: Jun. 12, 2007
  • Offline.
Forum Stats
Member
Level 26
Blank Slate
Response to AS3: Binary Search Aug. 20th, 2009 @ 10:13 PM Reply

That is
The coolest thing I have ever seen

but I still don't like AS3 >:(

420 blaze it faggot

liam
liam
  • Member since: Dec. 11, 2004
  • Offline.
Forum Stats
Member
Level 22
Blank Slate
Response to AS3: Binary Search Aug. 20th, 2009 @ 11:01 PM Reply

Jeez, that did not compile at all in Flash CS4.. your if/else syntax is kinda fucked up.. and with your use of the "standard" (I suppose) placement of curly braces, it's just messy as hell :/

Nice though.


Sup, bitches :)

BBS Signature
thedayturns
thedayturns
  • Member since: Aug. 8, 2009
  • Offline.
Forum Stats
Member
Level 01
Blank Slate
Response to AS3: Binary Search Aug. 21st, 2009 @ 01:10 AM Reply

At 8/20/09 11:01 PM, liaaaam wrote: Jeez, that did not compile at all in Flash CS4.. your if/else syntax is kinda fucked up.. and with your use of the "standard" (I suppose) placement of curly braces, it's just messy as hell :/

Hardly. The if/else syntax is pretty typical... and if he would have corrected the curly bracket placement, Flash would have died on an autocomplete because a code like (if(bla) { // stuff) breaks it.

Anyway, nice code, but it's hardly AS3 specific. In fact, it would be kind of neat to have like a theoretical programming section.

GustTheASGuy
GustTheASGuy
  • Member since: Nov. 2, 2005
  • Offline.
Forum Stats
Member
Level 08
Blank Slate
Response to AS3: Binary Search Aug. 21st, 2009 @ 02:51 AM Reply

Three words: balanced binary tree.


BBS Signature
Afro-Ninja
Afro-Ninja
  • Member since: Mar. 2, 2002
  • Offline.
Forum Stats
Moderator
Level 44
Game Developer
Response to AS3: Binary Search Aug. 21st, 2009 @ 03:53 AM Reply

At 8/21/09 01:10 AM, thedayturns wrote: In fact, it would be kind of neat to have like a theoretical programming section.

er.. the programming forum


BBS Signature
henke37
henke37
  • Member since: Sep. 10, 2004
  • Offline.
Forum Stats
Member
Level 30
Blank Slate
Response to AS3: Binary Search Aug. 21st, 2009 @ 05:14 AM Reply

Too bad that actionscript in banned there. Why? Because we got tired of reading the same stupid questions and "give me the codes" post all the time. We need an advanced forum for people who know what they are doing.


Each time someone abuses hittest, God kills a kitten. Please, learn real collision testing.

GustTheASGuy
GustTheASGuy
  • Member since: Nov. 2, 2005
  • Offline.
Forum Stats
Member
Level 08
Blank Slate
Response to AS3: Binary Search Aug. 21st, 2009 @ 05:54 AM Reply

I don't think there's a need. There are more suitable communities for people who know what they're doing.


BBS Signature
FlashtooREV
FlashtooREV
  • Member since: Jun. 9, 2009
  • Offline.
Forum Stats
Member
Level 06
Blank Slate
Response to AS3: Binary Search Aug. 21st, 2009 @ 06:12 AM Reply

At 8/21/09 05:14 AM, henke37 wrote: We need an advanced forum for people who know what they are doing.

Someone tried to do that with a thread, but Kirk locked it as he saw no future in it.


Ceterum censeo Carthaginem delendam esse.

Deadclever23
Deadclever23
  • Member since: Nov. 27, 2006
  • Offline.
Forum Stats
Member
Level 12
Blank Slate
Response to AS3: Binary Search Aug. 21st, 2009 @ 08:35 AM Reply

At 8/21/09 06:12 AM, FlashtooREV wrote:
At 8/21/09 05:14 AM, henke37 wrote: We need an advanced forum for people who know what they are doing.
Someone tried to do that with a thread, but Kirk locked it as he saw no future in it.

Guilty as charged.


"To live is the rarest thing in the world. Most people exist, that is all."
- Oscar Wilde

BBS Signature
Paranoia
Paranoia
  • Member since: Apr. 22, 2005
  • Offline.
Forum Stats
Member
Level 35
Game Developer
Response to AS3: Binary Search Aug. 21st, 2009 @ 08:50 AM Reply

At 8/21/09 06:12 AM, FlashtooREV wrote:
At 8/21/09 05:14 AM, henke37 wrote: We need an advanced forum for people who know what they are doing.
Someone tried to do that with a thread, but Kirk locked it as he saw no future in it.

There isn't enough demmand for it. Whenever something suitably amazing comes up we can just use the reg lounge or a new thread, and the handful of people who will get it can gravitate towards it.


BBS Signature
matrix5565
matrix5565
  • Member since: Feb. 28, 2006
  • Offline.
Forum Stats
Member
Level 16
Game Developer
Response to AS3: Binary Search Aug. 21st, 2009 @ 01:00 PM Reply

At 8/20/09 10:13 PM, 7IsUnlucky wrote: That is
The coolest thing I have ever seen
but I still don't like AS3 >:(
At 8/21/09 01:10 AM, thedayturns wrote: Anyway, nice code, but it's hardly AS3 specific. In fact, it would be kind of neat to have like a theoretical programming section.

Actually, this code should port to AS2 quite nicely depending on if/how you sort array's.

matrix5565
matrix5565
  • Member since: Feb. 28, 2006
  • Offline.
Forum Stats
Member
Level 16
Game Developer
Response to AS3: Binary Search Aug. 21st, 2009 @ 01:30 PM Reply

Wow, I decided to do a super scientific speed test and here are the results (in milliseconds):
Binary Search: <1
indexOf: 12368

The code:

import flash.utils.getTimer;

var startTime:int;
var finishTimes:Array = [];
var testArray:Array = [];

for (var i:int = 0; i <= 10000000; i++)
	testArray.push(i);
	
var rand:int = Math.random()*10000000;	

startTime = getTimer();
for (var a:int = 0; a <= 100; a++)
	bsearch(testArray,rand,0);
finishTimes.push(getTimer()-startTime);

startTime = getTimer();
for (var b:int = 0; b <= 100; b++)
	testArray.indexOf(rand);
finishTimes.push(getTimer()-startTime);

trace(finishTimes); //0, 12368

That was only one test, but the numbers varied a lot, between ~300 and ~15000, but the binary search never took more than 1 millisecond.

henke37
henke37
  • Member since: Sep. 10, 2004
  • Offline.
Forum Stats
Member
Level 30
Blank Slate
Response to AS3: Binary Search Aug. 21st, 2009 @ 03:19 PM Reply

That is because a binary search in a balanced tree is O(ln n) while a linear search is O(n). The cost is balancing the tree. Also, don't forget the cpu memory cache, a proper binary tree needs a lot of pointers, and pointers are horrible for the cache. If it is just a couple of items, stick to a linear search.


Each time someone abuses hittest, God kills a kitten. Please, learn real collision testing.

Arby
Arby
  • Member since: Oct. 24, 2004
  • Offline.
Forum Stats
Member
Level 28
Blank Slate
Response to AS3: Binary Search Aug. 21st, 2009 @ 04:56 PM Reply

Just an FYI, that exact same code will work in AS2 if you get rid of all the types.

Lol @ AS2 failing to have an int type. Didn't actually know that before...

Gust, your binary tree is no match for my TRINARY TREE!

Shush! it's useful in... I don't know.... hopefully something.. =/ but it's log3(n) search time!

At first there was nothing, then it exploded. - Big bang