1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
include Search_intf
open! Import
module Make
(Entry : ENTRY)
(Array : ARRAY with type elt = Entry.t)
(Metric : METRIC with module Entry := Entry) :
S with module Entry := Entry and module Array := Array = struct
module Value = Entry.Value
module Key = struct
include Entry.Key
let ( = ) a b = compare a b = 0
end
module Metric = struct
include Metric
let ( < ) a b = compare a b < 0
let ( = ) a b = compare a b = 0
let ( > ) a b = compare a b > 0
end
let look_around array key key_metric index =
let rec search (op : int63 -> int63) curr =
let i = op curr in
if i < Int63.zero || i >= Array.length array then raise Not_found
else
let e = array.(i) in
let e_metric = Metric.of_entry e in
if not Metric.(key_metric = e_metric) then raise Not_found
else if Key.equal (Entry.to_key e) key then Entry.to_value e
else (search [@tailcall]) op i
in
try search Int63.pred index
with Not_found -> (search [@tailcall]) Int63.succ index
(** Improves over binary search in cases where the values in some array are
uniformly distributed according to some metric (such as a hash). *)
let interpolation_search array key ~low ~high =
let key_metric = Metric.of_key key in
let rec search low high lowest_entry highest_entry =
if high < low then raise Not_found
else (
Array.pre_fetch array ~low ~high;
let lowest_entry = Lazy.force lowest_entry in
if high = low then
if Key.(key = Entry.to_key lowest_entry) then
Entry.to_value lowest_entry
else raise Not_found
else
let lowest_metric = Metric.of_entry lowest_entry in
if Metric.(lowest_metric > key_metric) then raise Not_found
else
let highest_entry = Lazy.force highest_entry in
let highest_metric = Metric.of_entry highest_entry in
if Metric.(highest_metric < key_metric) then raise Not_found
else
let next_index =
Metric.linear_interpolate ~low:(low, lowest_metric)
~high:(high, highest_metric) key_metric
in
let e = array.(next_index) in
let e_metric = Metric.of_entry e in
if Metric.(key_metric = e_metric) then
if Key.(key = Entry.to_key e) then Entry.to_value e
else look_around array key key_metric next_index
else if Metric.(key_metric > e_metric) then
(search [@tailcall])
Int63.(succ next_index)
high
(lazy array.(Int63.(succ next_index)))
(Lazy.from_val highest_entry)
else
(search [@tailcall]) low (Int63.pred next_index)
(Lazy.from_val lowest_entry)
(lazy array.(Int63.(pred next_index))))
in
if high < Int63.zero then raise Not_found
else (search [@tailcall]) low high (lazy array.(low)) (lazy array.(high))
end