Results 1 to 1 of 1
Thread: Word Tree debate and runtime
- 07-29-2013, 04:58 PM #1Member
- Join Date
- Jul 2013
- Rep Power
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
""(f) / | \ 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)
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 05:02 PM.
- By rajpan in forum JavaServer Faces (JSF)Replies: 0Last Post: 08-29-2012, 02:33 PM
- By lemontree45 in forum New To JavaReplies: 3Last Post: 08-30-2011, 04:44 PM
- By jfAdik in forum Forum LobbyReplies: 0Last Post: 04-04-2010, 07:40 AM
- By fxRichard in forum Advanced JavaReplies: 2Last Post: 01-06-2009, 04:53 PM