11 Replies - 752 Views - Last Post: 01 May 2017 - 04:46 PM

#1 general656  Icon User is offline

  • D.I.C Regular

Reputation: 12
  • View blog
  • Posts: 286
  • Joined: 25-March 15

Binary Interpolation Search ... but why?

Posted 29 April 2017 - 07:32 AM

I tested out Binary Interpolation Search and compared the results to Binary Search.
The results ... were dramatic. :tun tun tun:

For a size of 1 BILLION :dollars:

Posted Image

I tested the two algorithms. I can tell that Binary Interpolation Search had even worse results than linear for some damn reason. Here are the codes just for the record:

Linear Search:

int linearSearch (int *list, int l, int r, int key) {
	int found = 0, i = l;
	while (!found && i < r) {
		if (list[i] == key) return i;
		++i;
	}
	return -1;
}


Binary Search:

int binarySearch(int *list, int l, int r, int key) {
   if (r >= l)
   {
        int mid = l + (r - l)/2;
 
        // If the element is present at the middle itself
        if (list[mid] == key)  return mid;
 
        // If element is smaller than mid, then it can only be present
        // in left subarray
        if (list[mid] > key) return binarySearch(list, l, mid-1, key);
 
        // Else the element can only be present in right subarray
        return binarySearch(list, mid+1, r, key);
   }
 
   // We reach here when element is not present in array
   return -1;
}



Binary Interpolation Search:
(which code or even name I couldn't find ANYWHERE on google, its like no one uses this algorithm)

int bisSearch (int *arr, int l, int r, int key)  {
	int left 	= l;
	int right 	= r;

	int size = right - left;
	int next = (int) (size * ((key - arr[left])/(arr[right] - arr[left]))) + 1;

	while (key != arr[next]) {
		int i = 0;
		size = right - left;
		if (size <= 3)
			return linearSearch (arr, l, r, key);
		if (key >= arr[next]) {
			while (key > arr[next + i*((int) sqrt(size)) - 1]) {
				++i;
			}
			right = next + (int) (i*sqrt(size));
			left  = next + (int) ((i-1)*sqrt(size));
		}
		else if (key < arr[next]) {
			while (key < arr[next -i* ((int) sqrt(size)) + 1]) {
				++i;
			}
			right = next - (int) ((i-1)*sqrt(size));
			left  = next - (int) (i*sqrt(size));
		}
		next = (int) (left + ((right - left +1)*(key - arr[left])/(arr[right] - arr[left]))) - 1;
		
	}
	if (key = arr[next]) 
			return next;
		else return -1;
}


Last time, I tested it out with INT_MAX.
Binary Interpolation did around 2sec to find the given key, Linear Searching around 0.08sec but oh Binary Search ... did 0.000003secs.

So... what the heck? Why this "Interpolation" with the "loglogN" bigO has so bad timings every time I run it?

I run it with random numbers in the list (which were sorted) it got horrible results. I run it with close together numbers (like you can see in the main below, as the number is the same with its index), again horrible results.

Where is the "loglogN"? Why does BinarySearch with "logN" minumum runs so much significantly better than Binary InterpolationSearch?

PS.
My main just for the record ... :
#define SUPERBIGLENGTH INT_MAX
int main () {
	srand(time(NULL));
	clock_t begin, end;

	int *arr = (int*) malloc (SUPERBIGLENGTH * sizeof(int));
	for (int i = 0; i < SUPERBIGLENGTH; i++) {
		arr[i] = i;
	}

	double avgtime = 0;
	for (int i=0; i<10; i++) {
		int ind = rand() % SUPERBIGLENGTH;
		int key = arr[SUPERBIGLENGTH/1000];

		begin = clock();
		int index = linearSearch (arr, 0, SUPERBIGLENGTH-1, key);
		end   = clock();

		double totalTime = (double) (end - begin) / CLOCKS_PER_SEC;	
		printf ("$%fs\n", totalTime);
		avgtime += totalTime;
	}
	avgtime /= 10;
	
	printf("TOTAL TIIIIIIIME: %fs\n", avgtime);

	return 0;
}

This post has been edited by general656: 29 April 2017 - 07:40 AM


Is This A Good Question/Topic? 0
  • +

Replies To: Binary Interpolation Search ... but why?

#2 modi123_1  Icon User is offline

  • Suitor #2
  • member icon



Reputation: 13383
  • View blog
  • Posts: 53,409
  • Joined: 12-June 08

Re: Binary Interpolation Search ... but why?

Posted 29 April 2017 - 09:42 AM

Do you just mean 'Interpolation search'?
Was This Post Helpful? 0
  • +
  • -

#3 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5822
  • View blog
  • Posts: 19,818
  • Joined: 05-May 12

Re: Binary Interpolation Search ... but why?

Posted 29 April 2017 - 10:49 AM

Are you timing the byld with full optimizations? Did you make sure to commute sqrt(size) only once each time size changes?
Was This Post Helpful? 0
  • +
  • -

#4 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5822
  • View blog
  • Posts: 19,818
  • Joined: 05-May 12

Re: Binary Interpolation Search ... but why?

Posted 29 April 2017 - 12:45 PM

Also consider that after sqrt(), division and multiplication operations are also expensive.
Was This Post Helpful? 0
  • +
  • -

#5 general656  Icon User is offline

  • D.I.C Regular

Reputation: 12
  • View blog
  • Posts: 286
  • Joined: 25-March 15

Re: Binary Interpolation Search ... but why?

Posted 29 April 2017 - 12:52 PM

View Postmodi123_1, on 29 April 2017 - 09:42 AM, said:

Do you just mean 'Interpolation search'?

No, but I'm not surprised that you didn't know it. Oh my god. It's like no one knows this algorithm. I've searched on Google everywhere and no implementation was found. But some people know about it.

Since recently, I didn't even know "Interpolation Search", not only Binary Interpolation Search.
Our professor taught us about it.

Binary Interpolation Search is a combination of Interpolation Search With Binary Searching technique.
Basically ... what it is is a "Dynamic Interpolation Search" with a dynamic "mid" variable, that instead of doing a fixed step, it adjusts statistically.

But I don't see the point. Obviously, since no one knows it, no one uses it as well and as much as I saw the damn timings are shitty. It's not good to use.

View PostSkydiver, on 29 April 2017 - 10:49 AM, said:

Are you timing the byld with full optimizations? Did you make sure to commute sqrt(size) only once each time size changes?

Heyyyyyy ... I can't understand what you're saying :)
But all the code is above anyways you can answer it yourself :) Thank you by the way :D
Was This Post Helpful? 0
  • +
  • -

#6 modi123_1  Icon User is offline

  • Suitor #2
  • member icon



Reputation: 13383
  • View blog
  • Posts: 53,409
  • Joined: 12-June 08

Re: Binary Interpolation Search ... but why?

Posted 29 April 2017 - 01:08 PM

Quote

Oh my god. It's like no one knows this algorithm.

Obscure, unused, or oddly named algorithms are indeed obscure, unused, and odd.
Was This Post Helpful? 0
  • +
  • -

#7 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5822
  • View blog
  • Posts: 19,818
  • Joined: 05-May 12

Re: Binary Interpolation Search ... but why?

Posted 29 April 2017 - 01:11 PM

Sorry. Trying to type on a phone. When you compiled (e.g built) your code, did you compile with -O3 if gcc is your compiler, or -Ox if MSVC is your compiler?

Did you manually optimize the code to compute sqrt(size) only once near the beginning of the other while loop?

When I get home I will likely try some profiling runs against fully optimized builds.
Was This Post Helpful? 0
  • +
  • -

#8 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5822
  • View blog
  • Posts: 19,818
  • Joined: 05-May 12

Re: Binary Interpolation Search ... but why?

Posted 29 April 2017 - 01:42 PM

View Postgeneral656, on 29 April 2017 - 10:32 AM, said:

Where is the "loglogN"? Why does BinarySearch with "logN" minumum runs so much significantly better than Binary InterpolationSearch?


Apparently, you need a special data structure according to Wikipedia. A vanilla array ain't gonna cut it:

Quote

Using big-O notation, the performance of the interpolation algorithm on a data set of size n is O(n); however under the assumption of a uniform distribution of the data on the linear scale used for interpolation, the performance can be shown to be O(log log n). However, Dynamic Interpolation Search is possible in o(log log n) time using a novel data structure.

Was This Post Helpful? 1
  • +
  • -

#9 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5822
  • View blog
  • Posts: 19,818
  • Joined: 05-May 12

Re: Binary Interpolation Search ... but why?

Posted 29 April 2017 - 03:11 PM

Interestingly, that same quote predicts O(log log n) for evenly distributed keys, which is the case for your data set for that main(), that you showed above.

Looking at that code for biSearch(), the bug looks to be that you are doing integer division instead of floating point division on line 6. Due to that bug, you are essentially doing a linear probe from the beginning of the search segment until you find a segment that may contain the target value, and then you do the same operation with that new segment.

As an aside, if you change the tail recursion of your normal binary search to iteration the same way your binary interpolation search does iterations, the normal binary search will be even faster.
Was This Post Helpful? 0
  • +
  • -

#10 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5822
  • View blog
  • Posts: 19,818
  • Joined: 05-May 12

Re: Binary Interpolation Search ... but why?

Posted 01 May 2017 - 07:23 AM

I still haven't gotten around to doing some profiling runs, but looking around on line for various implementations of "binary interpolation search", I don't see the characteristic of your implementation where it does multiple probes trying to find a sqrt(size) sized segment that the value maybe in. All the implementations I've seen simply interpolate an index based on the value, check for a match, and if not, go use either the low half or high half as a result of the interpolation. Additionally, I haven't seen the switch over to using linear search at the point when the segment size goes below a particular threshold (except for various things talking about how to optimize searching).
Was This Post Helpful? 1
  • +
  • -

#11 general656  Icon User is offline

  • D.I.C Regular

Reputation: 12
  • View blog
  • Posts: 286
  • Joined: 25-March 15

Re: Binary Interpolation Search ... but why?

Posted 01 May 2017 - 11:52 AM

View PostSkydiver, on 01 May 2017 - 07:23 AM, said:

All the implementations I've seen [..]

Wait, you found a site with an implementation of Binary Interpolation Search?
Was This Post Helpful? 0
  • +
  • -

#12 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5822
  • View blog
  • Posts: 19,818
  • Joined: 05-May 12

Re: Binary Interpolation Search ... but why?

Posted 01 May 2017 - 04:46 PM

Data Structure - Interpolation Search

Computer Algorithms: Interpolation Search

Beating Binary Search: The Interpolation Search

Interpolation Search: A search algorithm better than Binary Search
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1