Geek asks and answers

More twiddling bits: Effective implementation of binary search on a fixed-size array

Once again I have a problem for which I would like to shave the nanoseconds. I have a small, persistent array, and I would like to find it to find out if a given number is a member *.

Input : 64-bit number n.

Conclusion : True if n is in the array, false if n is not.

What are some good methods to quickly search for binary searches, given the possibility of optimization for specific elements and their distribution.

Features

I have an array with 136 members (although see below: there is some flexibility) to search. Members are not evenly distributed over a range: they are grouped in the direction of the beginning and end of the range. Input numbers can be considered selected with uniform probability. It may be worth taking advantage of this irregularity.

Here is an example of a distribution image for an array of 136 elements. Please note that only 12 out of 136 elements are between 1% and 99% of the range; the balance is less than 1% or more than 99%.

http://math.crg4.com/distribution.png

I assume that a misprediction of the industry will be the biggest cost of any implementation. I would be happy if I were acquitted.

Notes

* . , , : , 10-40 , () 136 . , , . , , . , , . , , <= 135 <= 66 ( , ).

, . ( ...!) .

0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, 9320093220751060618, 9999984858389672876, 10259680355300795461, 10358875208395550958, 10396764270768694864, 10411236604793371085, 10416764544494255842, 10418876029572233892, 10419682545105283285, 10419990606626453414, 10420108275656914408, 10420153221227127261, 10420170388907304826, 10420176946377624668, 10420179451108406629, 10420180407830432670, 10420180773265728832, 10420180912849591277, 10420180966165882450, 10420180986530893524, 10420180994309635573, 10420180997280850646, 10420180998415753816, 10420180998849248253, 10420180999014828394, 10420180999078074380, 10420180999102232197, 10420180999111459662, 10420180999114984240, 10420180999116330509, 10420180999116844738, 10420180999117041156, 10420180999117116181, 10420180999117144838, 10420180999117155784, 10420180999117159965, 10420180999117161562, 10420180999117162172, 10420180999117162405, 10420180999117162494, 10420180999117162528, 10420180999117162541, 10420180999117162546, 10420180999117162548

Phenom II x4, .

+3
7

256 8 64- . 8 . .

, , ( ), . , 256 ( ), 0. 2 3 , ( , ). , , , , , , , . , , .

, 4 . " ", " 4 ". , 16 - , . , . , - . , C, . switch , , - .

, , .

, , , , . , - , , , 50% . , (, ). , , , , , , , , . / , , , .

+2

, hash . , -, .

: ...

64- , . , a) , 1 , , b) - .

-, . :

  • -, , .
  • () .
  • , .

, :

  • .
  • .
  • , .

- , :

  • , .
  • -, .
  • , , 64- , . , 3 : , .
+3

, , /-, , :

bool b = false;
b |= (n == x[i]);
b |= (n == x[i+1]);
// ... etc. ...

, , , 136 . , , , , , 4 n , .

+3

log_2 (n) . ( ? ? ?). .

( , ), " ?". , 3 * log_2 (n) 2 * log_2 (n). . (, , ). , , .

, .

, , .

+1

. , , - , .

, . : , , , , 0,01 , 0,99 , 49/50-, 2 .

  • 0,01-0,99 ( 0... 1, , 64- )

  • 0.0-0.01 0.99-1.0 , .

, ? . , 0.0-0.01 , 0.99-1.0 ; , , , , , , ( 0.0-0.01, ).

: jumptable 3 , , , - .

0

136 , 128- .

, 256 , f (x), , 256 .

f (x) , " " , , , .

0

() .

, :

if the value is greater than or equal to 2^63
    linear search from middle to end
otherwise (if the value is less than 2^63)
    linear search from middle to beginning (must go in reverse direction)

, :

int in_set(unsigned long long value)
{
    const unsigned long long max_bit_mask = (1 << 63);

    if(value & max_bit_mask) //if max bit is set, use linear search from middle (50% probability)
    {
        unsigned long long *ullp = data + 91; //WARNING: ullp should point to data + 92 on first dereference due to prefix increment
        while(*++ullp < value); //FIXME: array must be capped with ULLONG_MAX on the right
        return *ullp == value; //&& ullp != right_sentinel
    }

    //otherwise use reverse linear search from middle

    unsigned long long *ullp = data + 92; //WARNING: ullp should point to data + 91 on first dereference due to prefix decrement
    while(*--ullp > value); //WARNING: array must be capped with zero on the left
    return *ullp == value; //&& ullp != left_sentinel
}

O (1) (O (k) , k - ).

Steve Jessop , , 8- , , O (1) .

const int lookup_table[256] = {/*...*/};

unsigned long long *ullp = data + lookup[value >> 56];

//if, while, and returns as before

, , ( 0 ULLONG_MAX). , ULLONG_MAX , , . .

edit: O (1) , 40% (1/phi ^ 2), n/phi ^ (n + 1) n >= 1, 1/(phi-1) ^ 2 ( ~ 2.6)

edit2: this code should have a much smaller deviation from false prediction than a binary search, and should be faster on average if the queries have a "uniform integer distribution".

0
source

More articles:


All Articles