dcsimg
A Flash Developer Resource Site

Results 1 to 3 of 3

Thread: Dictionary/Binary search method?

  1. #1
    Member
    Join Date
    Sep 2009
    Posts
    78

    Dictionary/Binary search method?

    Hi there,

    On another website I came across the term "binary search method". I've never seen this term before, and was curious as to what exactly it is. Can anyone tell me, or direct me to a tutorial or article which explains this?

    Also, on the same website I saw someone suggesting that a person use a Dictionary. What exactly is a Dictionary in as3? I've seen mentions to it, but I haven't really seen anything more than those mentions.

    Just curious for once what these two things are, and how possibly to use them. If anyone could describe to me what they are/how to use them, or point me to a tutorial or article for them, that'd be great

  2. #2
    Ө_ө sleepy mod
    Join Date
    Mar 2003
    Location
    Oregon, USA
    Posts
    2,441
    A binary search (if I recall this correctly) is a branching search where you divide your possible results in half on each pass. So to find the letter "F" in the alphabet, you divide the alphabet in half and pick one half - you know F comes before M so you choose the first half. Then you do that again, F is earlier than G -- the halfway point between A and M -- so you choose the first half of the set again. So in two passes you've narrowed down to the first quarter of your results, A-F. You keep doing that until you find the match in the list.

    A Dictionary is a special collection object that can be indexed by any other kind of object - similar to an array which is indexed by an integer or a string:

    PHP Code:
    var a:Array = new Array();
    var 
    d:Dictionary = new Dictionary();

    a['five'] = 5;            //  string index
    a[1] = myButton;        //  int index

    d[myButton] = 123;        //  object index
    d[stage] = "top level";    //  object index 
    Please use [php] or [code] tags, and mark your threads resolved 8)

  3. #3
    Junior Member
    Join Date
    Dec 2009
    Posts
    15
    Link to the Actionscript.org thread mentioned.

    The reason I mentioned the Dictionary type was that I believed it was AS3's hash or tree structure. The documentation doesn't list it as such or mention it's algorithmic complexity, but I would still guess it to be a hash or a tree anyway. I believe Arrays indexed with strings also fall into this group (and are not actually Arrays), but I am unsure of that, so I just suggested a Dictionary be considered "to be safe".

    A hash is a container like an Array, but with some different properties. For instance, Arrays generally have poor insertion and removal properties towards the middle and beginning of the the items they represent, but maintain an order on those items and provide fast iteration and insertion/removal at the end (given proper abstraction). A hash, on the other hand, has very fast insertion, removal, and lookup, but can sometimes be slow to iterate, have high overhead, and does not maintain any order. There are many other advantages and disadvantages of both datastructures.

    A tree is another type of data structure commonly used in programming with it's own good and bad behaviors.

    A Trie is a type of Tree. My Trie example uses Dictionaries to store children nodes, but an Array, even indexed numerically, could have also been used without sacrificing too much performance. The Trie is constructed so that lookup time becomes a function of word length versus the total number of words.

    The explanation of a trie requires knowledge of how trees work. Explaining that could be difficult in a forum post like this, but the good news is that there are an endless number of explanations online already. You should take some time to understand and implement these structures as they're incredibly useful and fairly fundamental. Once understood, the trie algorithm should be much easier to understand. If not, though, I'd be happy to explain.

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