It is O(k) where k = length of lookup string. But, in practice, where the
set of strings that is being stored is a set of method names (mostly human
generated), you never hit the worst case.
Yeah, n was length of lookup string in my case to.
And in practice you will hit that most of the time in Ruby lookup,
seeing as you can never be sure you've hit the end. Take the simple
example of the two methods "foo" and "foo=". You need to follow the trie
to the second "o" node to find the method handle to return. So all
lookups will be O(n) where n is the length of the lookup string.
But, hashing is always O(k) where k = length of lookup string.
Yes, except that you don't always have to redo the hashing, since the
JVM strings actually caches it.
So, this basically boils down to the size of the constants in the O and
other implementation and platform details.
My main problem is the size and array lookup.
And since my experiences trying this, as I mentioned earlier, it ended
up significantly worse.
Cheers
--
Ola Bini (http://olabini.com)
Ioke creator (http://ioke.org)
JRuby Core Developer (http://jruby.org)
Developer, ThoughtWorks Studios (http://studios.thoughtworks.com)
Practical JRuby on Rails (http://apress.com/book/view/9781590598818)
"Yields falsehood when quined" yields falsehood when quined.
---------------------------------------------------------------------
To unsubscribe from this list, please visit:
http://xircles.codehaus.org/manage_email
