StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POWhat is the fastest search method for a sorted array?
text
Body
copied!<p>Answering to <a href="https://stackoverflow.com/questions/4752028/whats-wrong-with-this-interpolation-search-implementation/4752042#4752042">another question</a>, I wrote the program below to compare different search methods in a sorted array. Basically I compared two implementations of Interpolation search and one of binary search. I compared performance by counting cycles spent (with the same set of data) by the different variants.</p> <p>However I'm sure there is ways to optimize these functions to make them even faster. Does anyone have any ideas on how can I make this search function faster? A solution in C or C++ is acceptable, but I need it to process an array with 100000 elements.</p> <pre><code>#include <stdlib.h> #include <stdio.h> #include <time.h> #include <stdint.h> #include <assert.h> static __inline__ unsigned long long rdtsc(void) { unsigned long long int x; __asm__ volatile (".byte 0x0f, 0x31" : "=A" (x)); return x; } int interpolationSearch(int sortedArray[], int toFind, int len) { // Returns index of toFind in sortedArray, or -1 if not found int64_t low = 0; int64_t high = len - 1; int64_t mid; int l = sortedArray[low]; int h = sortedArray[high]; while (l <= toFind && h >= toFind) { mid = low + (int64_t)((int64_t)(high - low)*(int64_t)(toFind - l))/((int64_t)(h-l)); int m = sortedArray[mid]; if (m < toFind) { l = sortedArray[low = mid + 1]; } else if (m > toFind) { h = sortedArray[high = mid - 1]; } else { return mid; } } if (sortedArray[low] == toFind) return low; else return -1; // Not found } int interpolationSearch2(int sortedArray[], int toFind, int len) { // Returns index of toFind in sortedArray, or -1 if not found int low = 0; int high = len - 1; int mid; int l = sortedArray[low]; int h = sortedArray[high]; while (l <= toFind && h >= toFind) { mid = low + ((float)(high - low)*(float)(toFind - l))/(1+(float)(h-l)); int m = sortedArray[mid]; if (m < toFind) { l = sortedArray[low = mid + 1]; } else if (m > toFind) { h = sortedArray[high = mid - 1]; } else { return mid; } } if (sortedArray[low] == toFind) return low; else return -1; // Not found } int binarySearch(int sortedArray[], int toFind, int len) { // Returns index of toFind in sortedArray, or -1 if not found int low = 0; int high = len - 1; int mid; int l = sortedArray[low]; int h = sortedArray[high]; while (l <= toFind && h >= toFind) { mid = (low + high)/2; int m = sortedArray[mid]; if (m < toFind) { l = sortedArray[low = mid + 1]; } else if (m > toFind) { h = sortedArray[high = mid - 1]; } else { return mid; } } if (sortedArray[low] == toFind) return low; else return -1; // Not found } int order(const void *p1, const void *p2) { return *(int*)p1-*(int*)p2; } int main(void) { int i = 0, j = 0, size = 100000, trials = 10000; int searched[trials]; srand(-time(0)); for (j=0; j<trials; j++) { searched[j] = rand()%size; } while (size > 10){ int arr[size]; for (i=0; i<size; i++) { arr[i] = rand()%size; } qsort(arr,size,sizeof(int),order); unsigned long long totalcycles_bs = 0; unsigned long long totalcycles_is_64 = 0; unsigned long long totalcycles_is_float = 0; unsigned long long totalcycles_new = 0; int res_bs, res_is_64, res_is_float, res_new; for (j=0; j<trials; j++) { unsigned long long tmp, cycles = rdtsc(); res_bs = binarySearch(arr,searched[j],size); tmp = rdtsc(); totalcycles_bs += tmp - cycles; cycles = tmp; res_is_64 = interpolationSearch(arr,searched[j],size); assert(res_is_64 == res_bs || arr[res_is_64] == searched[j]); tmp = rdtsc(); totalcycles_is_64 += tmp - cycles; cycles = tmp; res_is_float = interpolationSearch2(arr,searched[j],size); assert(res_is_float == res_bs || arr[res_is_float] == searched[j]); tmp = rdtsc(); totalcycles_is_float += tmp - cycles; cycles = tmp; } printf("----------------- size = %10d\n", size); printf("binary search = %10llu\n", totalcycles_bs); printf("interpolation uint64_t = %10llu\n", totalcycles_is_64); printf("interpolation float = %10llu\n", totalcycles_is_float); printf("new = %10llu\n", totalcycles_new); printf("\n"); size >>= 1; } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload