Gereksiz IF & ELSE Kullanımı
Merhaba,
Bu yazıda basit ama bir o kadar da önemli ancak gözden kaçabilecek bir detaydan bahsetmek istiyorum. Neredeyse bütün programlama dillerinin temel taşı olan IF mekanizmasını, özellikle döngüler içinde fazladan gereksiz yere kullanmanın, performansı olumsuz yönde etkilediğini göstermek istiyorum.
İki adet binary search yapan fonksiyon yazacağız. Versyonlar arasında oluşan zaman farkı çok büyük olmayan veri setinde bile kayda değer performans kaybı doğurabiliyor.
İnternette binary search alogritmasına dair çeşitli kaynaklar bulabilirsiniz.
Aşağıdaki videoda güzel bir anlatım mevcut. Dikkat edilmesi gereken en önemli nokta arama yapılacak listenin sıralı bir liste olması gerekliliğidir.
Versyon1:
|
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; } |
Versyon2 (Versyon1 den farklı olarak döngü içerisindeki bir adet koşul çıkarılmıştır ve while kontrolüne eklenmiştir. Listeyi yarıya indirmek için yapılan bölme işlemi while öncesinde ve while içinde en son işlem olarak iki defa yapılmıştır.)
|
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 (0..2000000 sayıları arasında 768463 sayısını binary search arama)
|
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; } |
GCC ile derlemek için:
|
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 |
Kaynak:
Second Edition The C Programming Language (ANSI C version) by Brian W. Kernighan, Dennis M. Ritchie (Ex: Cp 3: P:1)