I have no reason to believe otherwise since you actually implemented tries.
As I said, I wasn't thinking about hashes when I posted that note, sorry to
waste everyone's time on this. :-)
No waste. =)
It's good to get fresh approaches - and there was no way you could have
known I'd already done
On Mon, Aug 10, 2009 at 12:06 PM, Ola Bini wrote:
>
>> 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 i
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
On Mon, Aug 10, 2009 at 11:16 AM, Ola Bini 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 i
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
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
to be honest, I forgot about hashing altogether .. embarassed smile :-) ...
but, might be good to think through / experiment a bit ... -s.
On Mon, Aug 10, 2009 at 10:07 AM, Thomas E Enebo wrote:
> On Mon, Aug 10, 2009 at 10:04 AM, Thomas E Enebo
> wrote:
> > Actually I was interested in trie's
On Mon, Aug 10, 2009 at 10:04 AM, Thomas E Enebo wrote:
> Actually I was interested in trie's because Clojure implements their
> main map data structure as an immutable trie. The best part is when
> Clojure adds a new element to a trie it creates a new root node (with
> some additional children no
Actually I was interested in trie's because Clojure implements their
main map data structure as an immutable trie. The best part is when
Clojure adds a new element to a trie it creates a new root node (with
some additional children nodes) and then returns the new trie (old
root may still be retain
Just a quick note so that I don't forget it.
Not sure how method lookup is implemented, but it occured to me that a
simple optimization might speedup lookup. This is not a big deal when
inline caching is implemented, but nevertheless something worth considering.
i.e. given a call "o.foo(args)",
10 matches
Mail list logo
