Nice example, and very nicely explained. I'd be keen to discuss this though... While for your example I can see it working well, finding everything with a common prefix is nice but it's not really faster than a hash for a single item lookup right?
This isn't an O(1) like a hash -> you have to do an O(1) for every character in the string on the lookup in the worst case (finding a complete match). Whereas a hash is doing an O(1) once. Sure to create the hash you have to touch a character in the string, but this is a mathematical operation not a table lookup. In your example you are using hashes at every character position anyway because that's how property lookups work. So I guess we could argue that both are O(N) where N is the length of the string. Locality of reference though, memory accesses etc, and for a single item lookup the hash is going to win by a significant margin.
In this you can see that there is also an effect of the number of items increasing the search time of the Trie (and not impacting the POJO hash lookup). Is this an implementation detail or something i'm not getting in the algorithm? I'm keen to get the best version of this for a project of mine. At present I'm finding an index in a sorted list using a binary search and gallop. Trie looks like it could be better than that, but not sure due to the number of hashed deferences at each letter - feels like it might be length of string dependent.
Thanks for your comment! After reading it, I believe I was misunderstood because I did not explain it correctly.
I’ll try to improve the implementation of this code and see the effect when the number of items is increasing, but, as I said, my code was just a simple example of trie structure. And it is necessary to consider that the native associative array/hash of the javascript will have better results because already have a nice well-optimized implementation. That said, the array will be more faster than most general purposes.
I agree with you when you said that the trie isn't an O(1) as a hash-table... But the trie can perform better in some complex problems, such as a search engine or autocomplete feature comparing with the hash table structure. Because we have to consider an imperfect associative array and it's almost impossible to create a uniform random distribution to avoid conflicts that lead to handling collisions by separate chaining or linear/double/Quadratic Proibing, the time to calculate the hash table, memory accesses...
I did't understand the problem in your project, but if you want, you can describe more and I can try to help you :)
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Nice example, and very nicely explained. I'd be keen to discuss this though... While for your example I can see it working well, finding everything with a common prefix is nice but it's not really faster than a hash for a single item lookup right?
This isn't an O(1) like a hash -> you have to do an O(1) for every character in the string on the lookup in the worst case (finding a complete match). Whereas a hash is doing an O(1) once. Sure to create the hash you have to touch a character in the string, but this is a mathematical operation not a table lookup. In your example you are using hashes at every character position anyway because that's how property lookups work. So I guess we could argue that both are O(N) where N is the length of the string. Locality of reference though, memory accesses etc, and for a single item lookup the hash is going to win by a significant margin.
In this you can see that there is also an effect of the number of items increasing the search time of the Trie (and not impacting the POJO hash lookup). Is this an implementation detail or something i'm not getting in the algorithm? I'm keen to get the best version of this for a project of mine. At present I'm finding an index in a sorted list using a binary search and gallop. Trie looks like it could be better than that, but not sure due to the number of hashed deferences at each letter - feels like it might be length of string dependent.
Thanks for your comment! After reading it, I believe I was misunderstood because I did not explain it correctly.
I’ll try to improve the implementation of this code and see the effect when the number of items is increasing, but, as I said, my code was just a simple example of trie structure. And it is necessary to consider that the native associative array/hash of the javascript will have better results because already have a nice well-optimized implementation. That said, the array will be more faster than most general purposes.
I agree with you when you said that the trie isn't an O(1) as a hash-table... But the trie can perform better in some complex problems, such as a search engine or autocomplete feature comparing with the hash table structure. Because we have to consider an imperfect associative array and it's almost impossible to create a uniform random distribution to avoid conflicts that lead to handling collisions by separate chaining or linear/double/Quadratic Proibing, the time to calculate the hash table, memory accesses...
I did't understand the problem in your project, but if you want, you can describe more and I can try to help you :)