On Mon, Aug 10, 2009 at 11:16 AM, Ola Bini <[email protected]> wrote:
> 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. 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. But, hashing is always O(k) where k = length of lookup string. So, this basically boils down to the size of the constants in the O and other implementation and platform details. Subbu.
