Efficiently-Searching-In-Memory-Sorted-Arrays
Efficiently Searching In-Memory Sorted Arrays:Revenge of the Interpolation Search? (by UWHustle)
Efficiently-Searching-In-Memory-
By UWHustle
| Efficiently-Searching-In-Memory-Sorted-Arrays | Efficiently-Searching-In-Memory- | |
|---|---|---|
| 1 | 1 | |
| 26 | - | |
| - | - | |
| 10.0 | - | |
| almost 3 years ago | - | |
| C++ | ||
| BSD 2-clause "Simplified" License | - |
The number of mentions indicates the total number of mentions that we've tracked plus the number of user suggested alternatives.
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
Efficiently-Searching-In-Memory-Sorted-Arrays
Posts with mentions or reviews of Efficiently-Searching-In-Memory-Sorted-Arrays.
We have used some of these posts to build our list of alternatives
and similar projects. The last one was on 2023-06-03.
-
Efficiently Searching In-Memory Sorted Arrays: Revenge of Interpolation Search? [pdf]
Big fan on your presentation on binary search that amortised multiple concurrent searches. I did several variations on binary search and always compared against the best one. [0] From what I remember, some variations were compiled to a branchless implementation and some were compiled to implementations that used a branch. I had many passes of analysis by pasting into godbolt with identical compilers and flags. Power of 2 binary search did better on small arrays iirc, but are the first to hit conflict misses. For larger arrays, I believe the branchy search algorithms start to do better since half their branches get predicted correctly.
I haven't looked at ITP, and other than being cautious about the cost I've seen of unrelated hybrid algorithms, I would need a substantial amount of time to analyze it enough to comment further. I'm on the BQN discord if you wanted a different form of communication.
[0] https://github.com/UWHustle/Efficiently-Searching-In-Memory-...
Efficiently-Searching-In-Memory-
Posts with mentions or reviews of Efficiently-Searching-In-Memory-.
We have used some of these posts to build our list of alternatives
and similar projects. The last one was on 2023-06-03.
-
Efficiently Searching In-Memory Sorted Arrays: Revenge of Interpolation Search? [pdf]
Big fan on your presentation on binary search that amortised multiple concurrent searches. I did several variations on binary search and always compared against the best one. [0] From what I remember, some variations were compiled to a branchless implementation and some were compiled to implementations that used a branch. I had many passes of analysis by pasting into godbolt with identical compilers and flags. Power of 2 binary search did better on small arrays iirc, but are the first to hit conflict misses. For larger arrays, I believe the branchy search algorithms start to do better since half their branches get predicted correctly.
I haven't looked at ITP, and other than being cautious about the cost I've seen of unrelated hybrid algorithms, I would need a substantial amount of time to analyze it enough to comment further. I'm on the BQN discord if you wanted a different form of communication.
[0] https://github.com/UWHustle/Efficiently-Searching-In-Memory-...