Ola Bini wrote:
I replaced our method tables with tries a few years back. The
performance ended up being quite bad since the trie implementation
need to handle more than just alphabetic characters, so each trie node
needs to have an internal array that is a bit too large. Array lookup
is also not that quick to do repeatedly in the JVM (bounds checking).
The end result was that for the case of method tables it performance
much worse - at least with my implementation.
Hashes are generally O(1) even though O is a bit large. A trie would
be O(log2 n) or something like that.
Cheers
Actually, a trie is worst case O(n) where the size of O depends on speed
of array lookup and so on.
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
