predictivesearch source code

1 /** Preditive Search
2  *
3  * A search algorithm based on Binary search which tries to reduce the number of memory accesses.
4  * If, on top of knowing that the input is sorted, we assume that it is distributed uniformally,
5  * we can then use the first and last object in the range to try and predict where the item we
6  * are looking for would be. This means that we would be doing less memory accesses.
7  *
8  * The formula for the prediction is `indexOf(min) + (needle - min)/(max - min) * (indexOf(max) - indexOf(min))`
9  */
10 module predictivesearch;
11 
12 import std.traits;
13 import std.conv;
14 import std.typecons;
15 
16 /// find needle in haystack using predictive search
17 Nullable!size_t find(R, T)(R haystack, T needle)
18 if(is(ReturnType!((R r, T t, size_t index) => r[index] == t) : bool) &&
19    is(ReturnType!((R r, T t) => r[0] < t) : bool) &&
20    is(ReturnType!((R r, T t) => r[0] > t) : bool) &&
21    is(ReturnType!((R r) => r.length) : size_t) &&
22    is(ReturnType!((R r, size_t i1, size_t i2) =>
23       cast(size_t)(i2 + (r[0] - r[1]).to!double / (r[2] - r[1]).to!double * (i1 - i2))) : size_t))
24 {
25    alias n_size_t = Nullable!size_t;
26 
27    if(haystack.length == 0) return n_size_t.init;
28    auto min = haystack[0];
29    size_t minIndex = 0;
30    if(needle == min) return n_size_t(minIndex);
31    if(min > needle) return n_size_t.init;
32    
33    auto max = haystack[haystack.length - 1]; // using length rather than $ to make the interface less restrictive
34 
35    size_t maxIndex = haystack.length - 1;
36 
37    if(needle == max) return n_size_t(maxIndex);
38    if(max < needle) return n_size_t.init;
39 
40    while(max != min)
41    {
42       size_t prediction = cast(size_t)
43          (minIndex + (needle - min).to!double / (max - min).to!double * (maxIndex - minIndex));
44       // max and min should already have been tested at this point,
45       // if predition truncated down to one of them, simply move them in by one.
46       if(prediction == minIndex)
47       {
48          minIndex++;
49          min = haystack[minIndex];
50          continue;
51       }
52       if(prediction == maxIndex) // should only happen if max < 0
53       {
54          maxIndex--;
55          max = haystack[maxIndex];
56          continue;
57       }
58 
59       auto actual = haystack[prediction];
60       if(actual == needle) return n_size_t(prediction);
61       if(actual < needle)
62       {
63          min = actual;
64          minIndex = prediction;
65          continue;
66       }
67       max = actual;
68       maxIndex = prediction;
69    }
70    return n_size_t.init;
71 }
72 
73 ///
74 unittest
75 {
76    auto array = [1, 2, 3, 4];
77    auto res = find(array, 1);
78    assert(!res.isNull);
79    assert(res.get == 0);
80    res = find(array, 4UL);
81    assert(!res.isNull);
82    assert(res.get == 3);
83    assert(find(array, 5).isNull);
84 }
85 
86 ///
87 unittest
88 {
89    auto array = [4, 5, 41, 44, 45, 48, 60, 72, 76,
90                   93, 102, 130, 132, 155, 174, 213, 230,
91                   247, 258, 266, 266, 272, 282, 304, 315,
92                   325, 334, 344, 350, 357, 369, 372, 376,
93                   382, 386, 426, 429, 454, 466, 472, 476,
94                   477, 478, 484, 508, 529, 539, 551, 571,
95                   574, 575, 581, 596, 619, 624, 629, 634,
96                   638, 653, 679, 680, 684, 684, 688, 698,
97                   729, 731, 746, 761, 762, 769, 779, 791,
98                   800, 806, 808, 818, 824, 828, 831, 833,
99                   835, 846, 857, 864, 867, 873, 885, 898,
100                   900, 918, 926, 936, 938, 941, 960, 977,
101                   981, 986, 989];
102    auto res = find(array, 155);
103    assert(!res.isNull);
104    assert(res.get == 13);
105    assert(find(array, 819).isNull);
106 }