Re:Binary Search: A new implementation that is up to 25% faster
by peter_d_sherman on Monday July 20, 2020 @02:52AM
(#23895311)
Also, before I forget, if let's say english words were being stored, you could have an array of 1..26 pointers (representing letters 'A'..'Z') where each pointer points to one of 26 other similar arrays, representing the second character, etc. This pattern could repeat in memory. Would it be time/space efficient? Depends on the data. Also, this could be combined with the above. Maybe the first few letters of words are stored this way, and the rest are ordered such that a binary search can be performed, as above. Again, depends on data, storage, and speed requirements. Sure, you could use one or more hashing techniques, but then what's the speed/memory penalty, and what's the penalty for collisions? So, there are a lot of considerations to be made when selecting a technique for storing/searching data... there is no one-size fits all technique, as I said above, there's always a better way to do things...
[ Parent
| on HN ]
Re:Binary Search: A new implementation that is up to 25% faster
by rurban on Monday July 20, 2020 @12:59PM
(#23899705)
You search the strings wordwide then, by 8 not by 1. You just need to represent the strings little or big endian, and construct the nested switches offline. About 20x faster than linear search via memcmp. http://blogs.perl.org/users/rurban/2014/08/perfect-hashes-an...
Re:Binary Search: A new implementation that is up to 25% faster
by secondcoming on Monday July 20, 2020 @03:55AM
(#23895669)
I think you're describing a very inefficient trie