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 --- docs/implementation/primitive/sort.html | 3 +++ 1 file changed, 3 insertions(+) (limited to 'docs/implementation') diff --git a/docs/implementation/primitive/sort.html b/docs/implementation/primitive/sort.html index 8e69a9ea..12160286 100644 --- a/docs/implementation/primitive/sort.html +++ b/docs/implementation/primitive/sort.html @@ -58,3 +58,6 @@

It's cheap and sometimes worthwhile to trim 𝕨 down to the range of 𝕩. After finding the range of 𝕩, binary cut 𝕨 to a smaller list that contains the range. Stop when the middle element fits inside the range, and search each half of 𝕨 for the appropriate endpoint of the range.

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 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 ≠𝕩.

+ +

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 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 (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