From f8775404ad29a669af3b2aac23dc5de866e4619f Mon Sep 17 00:00:00 2001 From: KunoiSayami Date: Sun, 7 Aug 2022 13:24:30 +0800 Subject: feat: Optimize binary search Signed-off-by: KunoiSayami --- expt_0802.cpp | 9 +++------ 1 file changed, 3 insertions(+), 6 deletions(-) (limited to 'expt_0802.cpp') diff --git a/expt_0802.cpp b/expt_0802.cpp index b1a906a..7d520e2 100644 --- a/expt_0802.cpp +++ b/expt_0802.cpp @@ -25,10 +25,6 @@ size_t calculate_location(size_t index) { } typedef int key_type; -int get_son_from_step(int point, bool negative) { - return negative ? point * 2 : point * 2 + 1; -} - const key_type *cudaBinarySearch(key_type *const start, const key_type *end, const key_type val) { int step_limit = (int)std::log2(LENGTH) + 1; @@ -40,7 +36,8 @@ const key_type *cudaBinarySearch(key_type *const start, const key_type *end, if (*last_known_point == val) { return last_known_point; } - son = get_son_from_step(son, (*last_known_point > val)); + // son = get_son_from_step(son, (*last_known_point > val)); + son = son * 2 + -((*last_known_point - val) >> 31); last_known_point = next_level_start + son; printf("%d\n", *last_known_point); } @@ -73,6 +70,6 @@ int main() { assert(calculate_location(i) == result[i]); } puts(""); - cudaBinarySearch(&result[0], &*result.end(), 1024); + cudaBinarySearch(&result[0], &*result.end(), 928); return 0; } -- cgit v1.3.1