Results 1 to 1 of 1
  1. #1
    t014y is offline Member
    Join Date
    Jul 2013
    Rep Power

    Default Word Tree debate and runtime

    For a mental exercise I have created a dictionary class with a tree like structure. Each node in the tree has a boolean that determines if the given path is a word and and array of pointers to the 26 possible next letters. The idea is that for less memory than a hashmap you can get quicker lookup then a binary search.

    The structure looks something like this...

    a(f) -> letter(boolean) meaning the letter you are at and the boolean stating if it is a word

    Java Code:
                       /           |             \
                   a(t)         b(f)           f(f)
               /     |             |               |    \
             n(t)   p(f)        y(t)          a(f)    i(f)
              |       |            |              |         \
            n(t)    e(t)        e(t)          t(t)        t(t)
    so here we have the words {a, an, ann, ape, by, bye, fat, fit}

    Now then, on to the testing setup. Based on how I understand runtime this should search in c time where c = the number of letters in a word (relatively constant compared to the number of words). And binary search runs in log(n) time where n = the number of words in the list. In order to test this I loaded a dictionary into this structure and into a Vector and then timed the lookup on every word using the 2 different methods. What I found was that the binary search was roughly 2 times faster.

    So the question is why is this?

    I have done some thinking on this and debated with friends and I have come to the conclusion that I think it is because an english dictionary is not large enough to take advantage of the O(c). I say this because the dictionary I loaded was about 83k words long and ln(83k) is about 11.3, given that this is the worst case for binary search if half of my words greater than 5 letters with some as long as 20 letters it seem this is possible.

    Please tell me what you think and if you have any ideas.

    P.S. if you are curious when loading the the words if the input file was sorted the Vector loaded faster and if the file was not sorted the tree loaded faster by about 5 times. (I used quick sort on the vector. and the file was with all the z's in order then they y's in order and so on, not quite worst case)

    P.P.S. sorry if this got posted twice. I tried to submit, then it asked me to log in, then it sent me to a blank page then I looked on the forum and didn't see it...
    Last edited by t014y; 07-29-2013 at 06:02 PM.

Similar Threads

  1. Display rich:tree in expandable mode when page loads with tree
    By rajpan in forum JavaServer Faces (JSF)
    Replies: 0
    Last Post: 08-29-2012, 03:33 PM
  2. Replies: 3
    Last Post: 08-30-2011, 05:44 PM
  3. Replies: 0
    Last Post: 04-04-2010, 08:40 AM
  4. Replies: 2
    Last Post: 01-06-2009, 04:53 PM

Posting Permissions

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