3 ms·
If the data to be binary searched is static, that is, if it doesn't change, and if it fits entirely in RAM, then what I would do is as follows: 1) Pre-compute
by peter_d_sherman 6y ago
If the data to be binary searched is static, that is, if it doesn't change, and if it fits entirely in RAM, then what I would do is as follows:
1) Pre-compute the first mid/center element, C1.
2) Move the data for this mid/center element to the first item in a new array.
3) Pre-compute the next two mid/center elements, that is, the ones between the start of the data and C1 (C2), and the one between C1 and the end of data (C3).
4) Move the data from C2 and C3 positions to the next positions in our array, the 2nd and 3rd position.
5) Keep repeating this pattern. For every iteration/split there are 2 times the amount of midpoints/data than the previous iteration. Order these linearly as the next items in our new array.
When you're done, two things will occur.
1) You will use a slightly different binary search algorithm.
That is because you no longer need to compute a mid-point at every iteration, those are now pre-computed in the ordered array.
2) Because the data is now ordered, it becomes possible to
load the tip of that data into the CPU's L1, L2, and L3 cache. If let's say your binary search takes 16 iterations to complete, then you might get a good headstart of 5-8 iterations (or more, depending on cache size and data size) of that data being in cache RAM, which will make those iterations MUCH faster.
Also, (and this is just me), but if your program has appropriate permissions to temporarily shut off interrupts (x86 cli sti -- or OS API equivalent), then this search can be that much faster (well, depends on what the overhead for cli/sti and API calls are, but test, test, test! (also, always shut off the network and other threads when you're testing, as they can skewer the results!) <g>)
https://en.wikipedia.org/wiki/Memory_hierarchy https://en.wikipedia.org/wiki/Memory_hierarchy
"Almost all programming can be viewed as an exercise in caching." --Terje Mathisen
"Assume Nothing" --Mike Abrash
Also, there is no such thing as the fastest binary search algorithm... there's always a better way to do them...
To paraphrase Bruce Lee:
"There are no mountain tops, there is only an endless series of plateaus, and you must ever seek to go beyond them..."
- dbsmith83 6y agoYou aren't really binary searching anymore. If it all fit into the RAM, you might as well just put it into a hashset.
- peter_d_sherman 6y agoYou are correct, hashes are tremendously useful for some types of data... But, hashes, while tremendously useful for some types of data, are not necessarily without problems for other data, most notably if the data has the possibility of collisions: https://en.wikipedia.org/wiki/Pigeonhole_principle https://en.wikipedia.org/wiki/Pigeonhole_principle https://en.wikipedia.org/wiki/Collision_(computer_science) https://en.wikipedia.org/wiki/Collision_(computer_science) https://danlark.org/2020/06/14/128-bit-division/ https://danlark.org/2020/06/14/128-bit-division/ >"When it comes to hashing, sometimes 64 bit is not enough, for example, because of birthday paradox — the hacker can iterate through random 2^{32} entities and it can be proven that with some constant probability they will find a collision, i.e. two different objects will have the same hash. 2^{32} is around 4 billion objects and with the current power capacity in each computer it is certainly achievable. That’s why we need sometimes to advance the bitness of hashing to at least 128 bits. Unfortunately, it comes with a cost because platforms and CPUs do not support 128 bit operations natively." So, it depends on the data, and what's being done with it, if the possibility of collisions exist, and what the implications of those possibilities are (perhaps hashes are great for speed, and harmless, if not used with respect to passwords, that is, used in some other place in software infrastructure, they might be the right choice for that place...)
- rocqua 6y agoAre binary searches that much better than hashmaps if a malicious attacker gets to interact with the system?
- smabie 6y agoHashmaps are resistant against timing attacks, while binary searches are not.
- rurban 6y agoWith possible timing attacks you usually do a full linear search, without early return. This search has always constant time, twice as slow. When the attacker gets to know the seed somehow even hashmaps can be exploited.
- longlivedeath 6y agoI think that you've invented a heap array.
- utopcell 6y agoindeed, that's how you'd embed a balanced binary search tree in an array.
- peter_d_sherman 6y agoAlso, 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...
- secondcoming 6y agoI think you're describing a very inefficient trie
- rurban 6y agoYou 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-and-faster-than-memcmp.html http://blogs.perl.org/users/rurban/2014/08/perfect-hashes-an...
- lifthrasiir 6y ago> That is because you no longer need to compute a mid-point at every iteration, those are now pre-computed in the ordered array. This is called the Eytzinger layout [1]. [1] https://arxiv.org/abs/1509.05053 https://arxiv.org/abs/1509.05053
- peter_d_sherman 6y agoDid not know that! Interesting! Upvoted!