Redundant If Else
Hello,
In this tutorial, I am going to highlight a tiny but important detail about using redundant IF ELSE control. Using unnecessary if else controls would probably affect performance of the program. We are going to write two versions of binary search. Even for a small data size, there is a considerable amount of difference between performances.
You can find many resources on the internet about binary search.
You can check the following video. Binary search just works with ordered lists.
Version1:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
int binsearch(int x, int v[], int n) { int high, low, mid; low = 0; high = n - 1; while (low <= high) { mid = (low + high) / 2; if (x < v[mid]) high = mid - 1; else if (x > v[mid]) low = mid + 1; else return mid; } return -1; } |
Version2(The difference from version1 is removing else part in while loop. Move mid = (low + high) / 2 operation to the end of while loop. Put one extra mid = (low + high) / 2 statement before while loop.)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
int binsearch_anil(int x, int v[], int n) { int high, low, mid; low = 0; high = n - 1; mid = (low + high) / 2; while (v[mid] != x && low <= high) { if (x < v[mid]) high = mid - 1; else low = mid + 1; mid = (low + high) / 2; } if (v[mid] == x) return mid; else return -1; } |
main.c (Finding 768463 between 0..2000000)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include <stdio.h> #include <time.h> #define MAX_SIZE 2000000 void fillarray(int v[]); int binsearch(int x, int v[], int n); int binsearch_anil(int x, int v[], int n); int main() { int c; clock_t begin, end; double time_spent; int v[MAX_SIZE]; int pos; int x = 768453; fillarray(v); while ((c=getchar()) != EOF) { begin = clock(); printf("binsearch(x, v, MAX_SIZE)=%d\n", binsearch(x, v, MAX_SIZE)); end = clock(); time_spent = (double)(end - begin) / CLOCKS_PER_SEC; printf("Time Spent:%f\n", time_spent); begin = clock(); printf("binsearch_anil(x, v, MAX_SIZE)=%d\n", binsearch_anil(x, v, MAX_SIZE)); end = clock(); time_spent = (double)(end - begin) / CLOCKS_PER_SEC; printf("Time Spent:%f\n", time_spent); } return 0; } void fillarray(int v[]) { int i; for (i = 0; i < MAX_SIZE -1; i++) { v[i] = i; } } int binsearch(int x, int v[], int n) { int high, low, mid; low = 0; high = n - 1; while (low <= high) { mid = (low + high) / 2; if (x < v[mid]) high = mid - 1; else if (x > v[mid]) low = mid + 1; else return mid; } return -1; } int binsearch_anil(int x, int v[], int n) { int high, low, mid; low = 0; high = n - 1; mid = (low + high) / 2; while (v[mid] != x && low <= high) { if (x < v[mid]) high = mid - 1; else low = mid + 1; mid = (low + high) / 2; } if (v[mid] == x) return mid; else return -1; } |
Compile with GCC and run:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
gcc main.c -o main ./main binsearch(x, v, MAX_SIZE)=768453 Time Spent:0.000086 binsearch_anil(x, v, MAX_SIZE)=768453 Time Spent:0.000002 binsearch(x, v, MAX_SIZE)=768453 Time Spent:0.000052 binsearch_anil(x, v, MAX_SIZE)=768453 Time Spent:0.000001 |
Source: Second Edition The C Programming Language (ANSI C version) by Brian W. Kernighan, Dennis M. Ritchie (Ex: Cp 3: P:1)