A Flash Developer Resource Site

Results 1 to 11 of 11

Thread: [Speed] AS1 Search

  1. #1
    SaphuA SaphuA's Avatar
    Join Date
    Oct 2002
    Location
    The Netherlands
    Posts
    2,182

    [Speed] AS1 Search

    Hehe,

    Since the discussion is so active lately I thought it wouldn't be bad posting this.

    On a Dutch forum I'm active someone was wondering about how to search through huge amounts of data. A discussion awoke and I was kind of surprised only few people knew their Algorithms. That's why I decided to make a Binary Search in Flash AS1. Please not that this works on sorted data only.

    I thought the app I made would be interesting for some people here aswell, since this is knowledge every programmer should have. So I've included the source with this post. Please be aware that the app creates an array with 456796 words, it'll most proberbly ask for permission to continue running. So use this at your own risk

    Code:
    // AAAAA-AZZZZ (456796)
    var collection = new Array();
    for (var a = 0; a<26; a++) {
    	for (var b = 0; b<26; b++) {
    		for (var c = 0; c<26; c++) {
    			for (var d = 0; d<26; d++) {
    				collection.push("A"+String.fromCharCode(a+65)+String.fromCharCode(b+65)+String.fromCharCode(c+65)+String.fromCharCode(d+65));
    			}
    		}
    	}
    }
    // Init Search
    function search(word) {
    	return binary(word, 0, collection.length-1);
    }
    // Binary Search
    function binary(word, from, to) {
    	var index = Math.floor((to-from)/2)+from;
    	if (collection[index]>word) {
    		return (to<=from ? -1 : binary(word, from, index-1));
    	} else if (collection[index]<word) {
    		return (to<=from ? -1 : binary(word, index+1, to));
    	} else if (collection[index] == word) {
    		return index;
    	}
    }
    // Interaction
    this.onMouseDown = function() {
    	var word = "A"+String.fromCharCode(65+Math.floor(Math.random()*26))+String.fromCharCode(65+Math.floor(Math.random()*26))+String.fromCharCode(65+Math.floor(Math.random()*26))+String.fromCharCode(65+Math.floor(Math.random()*26));
    	var time = getTimer();
    	var index = search(word);
    	if (index != -1) {
    		trace("... Found string "+word+" at index "+index+" in "+(getTimer()-time)+"ms");
    	} else {
    		trace("... Word  "+word+" was not found in the current collection.");
    	}
    };
    // Output
    trace("------------------------------");
    trace("Binary search demo");
    trace("------------------------------");
    trace("Author: SaphuA");
    trace("Date: 07-02-2007");
    trace("------------------------------");
    trace("This demo generates a huge (456796 items) sorted array");
    trace("and allows the user to perform multiple searches on it");
    trace("using the binary search. This demo is merely ment to");
    trace("demonstrate the power of the algorithm itself and to");
    trace("prove that Flash isnt as limited as some people think.");
    trace("(Press mousebutton to start a test)");
    trace("------------------------------");
    trace("Total amount of words in collection: "+collection.length);
    trace("------------------------------");
    Average itterations per search. (N = 456796)
    Linear: N/2 = 228298 i/s
    Binary: log N = 5.7 i/s
    Last edited by SaphuA; 02-07-2007 at 03:06 PM.

  2. #2
    SaphuA SaphuA's Avatar
    Join Date
    Oct 2002
    Location
    The Netherlands
    Posts
    2,182
    Geez, they keep thinking adding different crazy things to keep the forum clean. You can't edit your post after 10 minutes you posted.

    I wanted to note that the Linear search means searching through the whole array using a simple for-loop (left to right) untill you find the value. This would on average take as long as half the amount of items in the array per search.

  3. #3
    Zombie Coder EvilKris's Avatar
    Join Date
    Jun 2006
    Location
    Fukuoka, Japan.
    Posts
    796
    Binary tree search. Wow, taking me back to college with that. Nice job.

  4. #4
    Senior Member
    Join Date
    May 2003
    Location
    Austria
    Posts
    146
    Yeah, that reminds me of my algorithms and datastructure lectures...

    A recursive algorithm allocates much more memory than an iterative, so it would be better if you implent it like the following pseudo code on wikipedia

    You can also speed things a little bit up if you use...
    Code:
    (high+low)>>1
    ..instead of..
    Code:
    Math.floor((high+low)/2)

  5. #5
    M.D. mr_malee's Avatar
    Join Date
    Dec 2002
    Location
    Shelter
    Posts
    4,139
    yaaaa data structures.

    Since i never learned programming at school or uni, i've got a big fatty ass book to teach me.

    Data structures rock, one of my goals is to create an AS3 class for every search/tree structure available.

    Nice one
    lather yourself up with soap - soap arcade

  6. #6
    Senior Member
    Join Date
    May 2003
    Location
    Austria
    Posts
    146
    Quote Originally Posted by mr_malee

    Data structures rock, one of my goals is to create an AS3 class for every search/tree structure available.
    That would be great. I am used to the collections availiable in the JAVA API and hate it when I have to write a data structure from scratch in Flash. Actually I could not take any advantage of such a class because I am still using Flash MX

    Just in case soemone is interested in a binary search tree class in AS 1:

    Code:
    function Tree() {
    	this.root;
    }
    Tree.prototype.insert = function(object) {
    	var node = new Node(object);
    	this.root = this.insert2(this.root, node);
    };
    Tree.prototype.insert2 = function(treeNode, node) {
    	if (treeNode == undefined) {
    		treeNode = node;
    	} else if (treeNode.value == node.value) {
    	} else if (treeNode.value>node.value) {
    		treeNode.left = this.insert2(treeNode.left, node);
    	} else {
    		treeNode.right = this.insert2(treeNode.right, node);
    	}
    	return treeNode;
    };
    Tree.prototype.search = function(object) {
    	return this.search2(this.root, object);
    };
    Tree.prototype.search2 = function(treeNode, val) {
    	if (treeNode == undefined) {
    		return false;
    	} else if (treeNode.value == val) {
    		return true;
    	} else if (treeNode.value>value) {
    		treeNode = this.search2(treeNode.left, val);
    	} else {
    		treeNode = this.search2(treeNode.right, val);
    	}
    	return treeNode;
    };
    Tree.prototype.inOrder = function() {
    	this.inOrder2(this.root);
    };
    Tree.prototype.inOrder2 = function(node) {
    	if (node == undefined) {
    		return;
    	}
    	this.inOrder2(node.left);
    	trace(node.value);
    	this.inOrder2(node.right);
    };
    function Node(value) {
    	this.value = value;
    	this.right;
    	this.left;
    }
    //Edit: usage
    t = new Tree();
    t.insert("D1");//or insert numbers
    t.insert("A1");
    t.insert("M1");
    t.insert("Z");
    t.insert("M");
    trace(t.search("M1"));
    trace(t.search("f"));
    t.inOrder();
    Last edited by andreaskrenmair; 02-07-2007 at 07:16 PM.

  7. #7
    Axis Games Djugan's Avatar
    Join Date
    Oct 2003
    Posts
    238
    Like Malee, I never took a programming course in school, so I don't have a clue what a data structure is.

    I read through the AS1 code quickly and I understand that it makes words (I think it does at least). But what would the purpose of it be? What are data structures used for?

    Thanks ;-)

  8. #8
    SaphuA SaphuA's Avatar
    Join Date
    Oct 2002
    Location
    The Netherlands
    Posts
    2,182
    Djugan,
    The creation of words isn't the important part of the code. The important part is that the binary function is able to look through sorted data (words in this case) to find an items index number within the array. It's an extremely fast search function. The function itself isn't new, I just wanted to show that you achieve a lot with a bit knowledge and some thinking.

    Andreas,
    Thanks for those tips. It's not that relevant in this case (the function gets only called about 6 times per search), but it's still interesting knowledge.

    The tree is very nice aswell, thanks for sharing.

  9. #9
    Senior Member
    Join Date
    May 2003
    Location
    Austria
    Posts
    146
    6 times per search, really? I remember that you need about log2(N) + 1 searches in the worst case. So in your case N = 456796 that would result in around 20 times per search (in the worst case) (which still does not allocate much memory).

    I think this really shows the strength of this technique. 20 against 456796 searches in the worst case. So it is very good for such slow languages like AS1.

    Djugan, the binary search is an algorithm. A data structure is a way to save data. So an array is a data strucure for example. The goal is to save the data in an efficient way. In algorithms like A* you need a sorted list or an array in order to get the shortes path. Or have a look at BSP trees which can also be used in games.
    Last edited by andreaskrenmair; 02-08-2007 at 06:12 PM.

  10. #10
    SaphuA SaphuA's Avatar
    Join Date
    Oct 2002
    Location
    The Netherlands
    Posts
    2,182
    I was talking about average, not worst case (or I might have calculated it wrong). But still, 20 iterations is much better then 456796.

    I'm realy into these kind of algorithms lately. Here's a QuickSorter, something very interesting aswell. It's able to sort loads of random data in a Flash (get it ). The major drawback (as explained in the output) is that when your collection holds more then aprox 250 sorted records before calling the function it will cause the Flashplayer to cancel the search because of an infinite recursive call. This is because the way the QuickSort is set up. It handles random data better then already sorted.
    Code:
    // Collection
    var collection = new Array();
    for (var i = 0; i<10000; i++) {
    	collection.push(getRandomWord());
    }
    function getRandomWord() {
    	return getRandomChar()+getRandomChar()+getRandomChar()+getRandomChar();
    }
    function getRandomChar() {
    	return String.fromCharCode(65+Math.floor(Math.random()*26));
    }
    // Swapping
    function swapValue(from, to) {
    	var bup = collection[from];
    	collection[from] = collection[to];
    	collection[to] = bup;
    }
    // Init Sorting
    function initQuickSort() {
    	trace("Sorting...");
    	var t = getTimer();
    	quickSort(0, collection.length-1);
    	trace("... Sorted in "+(getTimer()-t)+"ms.");
    }
    // Quick Sort
    function quickSort(from, to) {
    	var i = from;
    	var k = to;
    	if (to-from>=1) {
    		var pivot = collection[from];
    		while (k>i) {
    			while (collection[i]<=pivot && i<=to && k>i) {
    				i++;
    			}
    			while (collection[k]>pivot && k>=from && k>=i) {
    				k--;
    			}
    			if (k>i) {
    				swapValue(i, k);
    			}
    		}
    		swapValue(from, k);
    		quickSort(from, k-1);
    		quickSort(k+1, to);
    	}
    }
    // Check Sorting
    function testSorted() {
    	trace("Testing...");
    	var errors = 0;
    	for (var i = 0; i<collection.length-1; i++) {
    		if (collection[i]>collection[i+1]) {
    			trace("... Error located at index "+i+".");
    			errors++;
    		}
    	}
    	trace("... Tested ("+errors+" errors).");
    }
    // Interaction
    this.onMouseDown = function() {
    	initQuickSort();
    	trace("");
    	testSorted();
    	trace("------------------------------");
    };
    // Output
    trace("------------------------------");
    trace("Quicksort demo");
    trace("------------------------------");
    trace("Author: SaphuA");
    trace("Date: 08-02-2007");
    trace("------------------------------");
    trace("This demo is merely ment to demonstrate the power of");
    trace("the algorithm itself and to prove that Flash isn't as");
    trace("limited as some people say it is.");
    trace("Note:");
    trace("The major drawback with this method is that it's mostly");
    trace("active when the data is already sorted before calling the");
    trace("function. The Flashplayer will see this heavy action as a");
    trace("never ending recursive call and will cancel the movie.");
    trace("This means that the method is only usefull when the data");
    trace("is as random as can be, it will then be able to easily");
    trace("sort tenthousands of records.");
    trace("(Press mousebutton to start sorting)");
    trace("------------------------------");
    trace("Total amount of records in collection: "+collection.length);
    trace("------------------------------");

  11. #11
    Axis Games Djugan's Avatar
    Join Date
    Oct 2003
    Posts
    238
    Quote Originally Posted by andreaskrenmair
    Djugan, the binary search is an algorithm. A data structure is a way to save data. So an array is a data strucure for example. The goal is to save the data in an efficient way. In algorithms like A* you need a sorted list or an array in order to get the shortes path. Or have a look at BSP trees which can also be used in games.
    Thanks for the explanation ;-)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  




Click Here to Expand Forum to Full Width

HTML5 Development Center