From cde6f699cd4b76b3b193a8d5bd39242261196fbd Mon Sep 17 00:00:00 2001 From: Marshall Lochbaum Date: Sun, 13 Feb 2022 11:28:04 -0500 Subject: Comments on interpolation search --- implementation/primitive/sort.md | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'implementation') diff --git a/implementation/primitive/sort.md b/implementation/primitive/sort.md index 36b9c916..beb99a58 100644 --- a/implementation/primitive/sort.md +++ b/implementation/primitive/sort.md @@ -100,3 +100,9 @@ It's cheap and sometimes worthwhile to trim `𝕨` down to the range of `𝕩`. If `𝕩` is small-range, then a lookup table method is possible. Check the length of `𝕨` because if it's too large then this method is slowerβ€”binary search doesn't have to hit every element! The approach is simply to create a table of the number of elements in `𝕨` with each value, then take a prefix sum. In BQN, ``π•©βŠ+`(1+βŒˆΒ΄π•©)↑/⁼𝕨``, assuming a minimum of 0. [Partitioning](#partitioning) allows one pivot `t` from `𝕨` to be compared with all of `𝕩` at once. Although the comparison `t≀𝕩` can be vectorized, the overhead of partitioning still makes this method a little slower per-comparison than sequential binary search *when* `𝕨` *fits in L1 cache*. For larger `𝕨` (and randomly positioned `𝕩`) cache churn is a huge cost and partitioning can be many times faster. It should be performed recursively, switching to sequential binary search when `𝕨` is small enough. Unlike quicksort there is no difficulty in pivot selection: always take it from the middle of `𝕨` as in a normal binary search. However, there is a potential issue with memory. If `𝕩` is unbalanced with respect to `𝕨`, then the larger part can be nearly the whole length of `𝕩` (if it's all of `𝕩` partitioning isn't actually needed and it doesn't need to be saved). This can require close to `2⋆⁼≠𝕨` saved partitions of length `≠𝕩`, while the expected use would be a total length `≠𝕩`. + +#### Interpolation search? + +Binary search is the optimal approach for truly unknown data. However, if the searched array has an approximately uniform distribution, giving an approximately linear relationship between index and value, [interpolation search](https://en.wikipedia.org/wiki/Interpolation_search) uses asymptotically fewer comparisons. Because of the high overhead of index computation (a division!!), it could only ever be useful for large `𝕨`, and `𝕩` small enough that partitioning isn't viable. + +Interpolation is generally held to be counterproductive because of how badly it fails for non-uniform data. But the continuous-domain equivalent, bracketed root-finding, is better studied, with hybrid approaches developed to fix this. The recently published [ITP method](https://en.wikipedia.org/wiki/ITP_Method) (2020) gets the advantages of interpolation with the same maximum number of comparisons as binary search, plus a configurable constant (even if set to 0, it can take advantage of the gap between the length and the next power of 2, but 1 is a better setting). And once the search range is small enough that memory access stops being very expensive, it should switch to binary search and avoid the division. -- cgit v1.2.3