diff options
Diffstat (limited to 'implementation')
| -rw-r--r-- | implementation/primitive/sort.md | 6 |
1 files changed, 6 insertions, 0 deletions
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. |