Last active
August 29, 2015 14:20
-
-
Save pkhuong/10e19a6d3b1a06961dca to your computer and use it in GitHub Desktop.
Array searches: Morin's code is probably representative of what most people use in industry... i.e., not that good :x
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// b-tree | |
// Before | |
template<unsigned B, typename T, typename I> | |
I btree_array<B, T,I>::search(const T &x) { | |
I j = n; | |
I i = 0; | |
while (i < n) { | |
I lo = i; | |
I hi = std::min(i+B, n); | |
while (lo < hi) { | |
I m = (lo + hi) / 2; | |
if (x < a[m]) { | |
hi = m; | |
j = hi; | |
} else if (x > a[m]) { | |
lo = m+1; | |
} else { | |
return m; | |
} | |
} | |
i = child((unsigned)(hi-i), i); | |
} | |
return j; | |
} | |
// After (hack because clang will unroll but not cmov, and g++ won't unroll) | |
template<unsigned int B, typename T> | |
static const T *inner_search(const T *base, const T x) | |
{ | |
if (B <= 1) { | |
return base; | |
} | |
const unsigned int half = B / 2; | |
const T *current = &base[half]; | |
return inner_search<B - half, T>((*current < x) ? current : base, x); | |
} | |
template<unsigned B, typename T, typename I, bool early_termination> | |
__attribute__((noinline)) | |
I btree_array<B, T, I, early_termination>::search(const T x) { | |
I j = n; | |
I i = 0; | |
while (i < n) { | |
/* Last (partial block). */ | |
if (__builtin_expect(i + B >= n, 0)) { | |
const T *base = &a[i]; | |
I m = n - i; | |
while (m > 1) { | |
I half = m / 2; | |
const T *current = &base[half]; | |
base = (*current < x) ? current : base; | |
m -= half; | |
} | |
I ret = (*base < x) + base - a; | |
return (ret == n) ? j : ret; | |
} | |
const T *base = &a[i]; | |
const T *pred = inner_search<B, T>(base, x); | |
unsigned int nth = (*pred < x) + pred - base; | |
{ | |
/* nth == B iff x > all values in block. */ | |
const T current = base[nth % B]; | |
I next = i + nth; | |
if (early_termination && current == x) { | |
return next; | |
} | |
j = (current >= x) ? next : j; | |
} | |
i = child(nth, i); | |
} | |
return j; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Eytzinger (breadth-first) | |
// Before | |
template<typename T, typename I> | |
I eytzinger_array<T,I>::search(const T &x) { | |
I j = n; | |
I i = 0; | |
for (int d = 0; i < n; d++) { | |
if (x < a[i]) { | |
j = i; | |
i = 2*i + 1; | |
} else if (x > a[i]) { | |
i = 2*i + 2; | |
} else { | |
return i; | |
} | |
} | |
return j; | |
} | |
// After | |
template<typename T, typename I, bool early_termination> | |
__attribute__((noinline)) | |
I eytzinger_array<T,I,early_termination>::search(const T x) { | |
I j = n; | |
I i = 0; | |
while (i < n) { | |
const T current = a[i]; | |
if (early_termination && current == x) { | |
return i; | |
} | |
j = (x <= current) ? i : j; | |
i = (2 * i + 1) + (x > current); | |
} | |
return j; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Sorted array. | |
//Before: | |
template<typename T, typename I> | |
I sorted_array<T,I>::search(const T &x) { | |
I lo = 0; | |
I hi = n; | |
while (lo < hi) { | |
I m = (lo + hi) / 2; | |
if (x < a[m]) { | |
hi = m; | |
} else if (x > a[m]) { | |
lo = m+1; | |
} else { | |
return m; | |
} | |
} | |
return hi; | |
} | |
//After: (That's a non-standard binary search, I should write about it) | |
template<typename T, typename I, bool early_termination> | |
__attribute__((noinline)) | |
I sorted_array<T,I,early_termination>::search(const T x) { | |
const T *base = a; | |
I n = this->n; | |
while (n > 1) { | |
I half = n / 2; | |
const T *ptr = &base[half]; | |
const T current = *ptr; | |
if (early_termination && current == x) { | |
return ptr - a; | |
} | |
base = (current < x) ? ptr : base; | |
n -= half; | |
} | |
return (*base < x) + base - a; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// van Emde Boas | |
// before | |
template<typename T, typename I> | |
I veb_array<T,I>::search(const T &x) { | |
I rtl[MAX_H+1]; | |
I j = n; | |
I i = 0; | |
I p = 0; | |
for (int d = 0; i < n; d++) { | |
rtl[d] = i; | |
if (x < a[i]) { | |
p <<= 1; | |
j = i; | |
} else if (x > a[i]) { | |
p = (p << 1) + 1; | |
} else { | |
return i; | |
} | |
i = rtl[d-s[d].h0] + s[d].m0 + (p&s[d].m0)*(s[d].m1); | |
} | |
return j; | |
} | |
// after | |
template<typename T, typename I, bool early_termination> | |
__attribute__((noinline)) | |
I veb_array<T,I,early_termination>::search(const T &x) { | |
I rtl[MAX_H+1]; | |
I j = n; | |
I i = 0; | |
I p = 0; | |
for (int d = 0; i < n; d++) { | |
const I h0 = h0s[d]; | |
const I h1_1 = h1_1s[d]; | |
const I m0 = ((I)2 << h0) - 1; | |
const T current = a[i]; | |
rtl[d] = i; | |
if (early_termination && current == x) { | |
return i; | |
} | |
j = (x <= current) ? i : j; | |
p = (p << 1) + (x > current); | |
I mask = p & m0; | |
i = rtl[d - h0] + m0 + (mask << h1_1) - mask; | |
} | |
return j; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment