facebook like button

23 November, 2011

Get the execution time of a C program

The need:
     Need is same as previous program which gives you precision of nanoseconds but that program would work only on linux. This program will work on windows also but will give you precision of milli seconds only.  All you need to do is to place your test program code (the code whose execution time is to be measured) in between the comments which indicate the start and end of the program.
The code:
----------------------------------------------------------
/*This program should work on both windows and linux*/
#include<time.h> 
#include<stdio.h>
#include<stdlib.h> 
#define START if ( (start_time = clock()) == -1) {printf("Could not call clock");exit(1);} 
#define STOP if ( (stop_time = clock()) == -1) {printf("Could call clock");exit(1);} 
#define PRINT_TIME_DIFF printf( "Your program took %.3f seconds.\n", ((double)stop_time-start_time)/CLOCKS_PER_SEC); 
    
int main()
{ 
    clock_t start_time, stop_time;
    int i=0; 
    START
    //test program code begins
    
    //test program code ends 
    STOP 
    PRINT_TIME_DIFF
    return 0; 
} 
----------------------------------------------------------
Approach:
   The approach is simple. There is a built-in function clock() in <time.h> header file. In this program I have use macros to differentiate between your test code and the statement which would be used to print the time and other things. I thought this would simplify the look of the program a little bit.
Remarks:
1. This program should work on both windows and linux.
2. This program will give accuracy of (1/1000)th part of a second.

22 November, 2011

Getting running time of a C program

The need:
     Need is obvious.Whenever you are curious to find running time of a program or you are asked to do so, you can use this program. All you need to do is to place your program code(the code between the brackets of main() function ) in between the comments which indicate the start and end of the program.
The code:
----------------------------------------------------------
/*This program is intended to work on linux*/
#include <stdio.h> 
#include <time.h> 
void print_time_diff(struct timespec begin,struct timespec end);
int main ( void )
{
    struct timespec start, end;
    gettimeofday(&start, NULL);
    //program code begins
    //program code ends
    gettimeofday(&end, NULL);
    print_time_diff(start,end);
    return 0;
}

void print_time_diff(struct timespec begin,struct timespec end)
{
    unsigned int sec,nanosec;
    if (end.tv_nsec<begin.tv_nsec) {
        sec = end.tv_sec-begin.tv_sec-1;
        nanosec = 1000000000+end.tv_nsec-begin.tv_nsec;
    } else {
        sec = end.tv_sec-begin.tv_sec;
        nanosec = end.tv_nsec-begin.tv_nsec;
    }
    printf("your program took %d seconds and %u nanoseconds to run.\n",sec,nanosec);
} 
----------------------------------------------------------
Approach:
   The approach is simple. There is a built-in structure timespec in <time.h> header file of linux.The built-in definition of structure is:
struct timespec
  {
    __time_t tv_sec;        /* Seconds.  */
    long int tv_nsec;        /* Nanoseconds.  */
  };
The program declares 2 struct variables start and end. built-in function gettimeofday() fills the struct variable passed to it with suitable values at that particular instance. This implies that start gets the value of time when your program (code to be measured) is just about to start and end gets the value of time as soon as your program finishes.
print_time_diff() is user defined function which prints the difference of the two times passed to it as arguments.
Remarks:
1. This program should not work on windows and operating systems other than linux.
2. The program which would work on windows will be posted shortly.

Heap sort in C

The need:
   Heap sort is a better than bubble, selection and insertion algorithm for sorting. To show how heap can be useful in real life implementation.
The code:
-----------------------------------------------------------
/*this program is an array implementation of heap*/ 
#include<stdio.h> 
#include<string.h> 
#include<stdlib.h> 

void print_array(int a[],int array_size); 
void heap_sort(int a[],int array_size); 
void heapify(int a[],int count); 
void adjust_down(int a[],int start, int end); 

main() 
{ 
    int i,arr[50],size=0; 
    arr[0]=0; 
    printf("how many elements do you want to enter\n");
    scanf("%d",&size); 
    if(size<1)
    {
        printf("You did not enter a valid count of elements.\n");
        printf("Rerun the program and try again\n");
        exit(0);
    }
    printf("enter array\n"); 
    for(i=1;i<=size;i++) 
        scanf("%d",&arr[i]);
    printf("the array before heap sort.\n"); 
    print_array(arr,size); 
    heap_sort(arr,size);
    printf("the array after heap sort.\n"); 
    print_array(arr,size);    
} 

void heap_sort(int a[],int array_size)
{
    int i,j,heap_end,temp;
    heap_end=array_size;
    heapify(a,array_size);
    while(heap_end>2)
    {
        temp=a[1];
        a[1]=a[heap_end];
        a[heap_end]=temp;
        heap_end--;
        adjust_down(a, 1, heap_end);
    }
}

void heapify(int a[],int count) 
{ 
    int start;
    start = count/2 + 1;
    while(start>0)
    {
        adjust_down(a, start, count);
        start--;
    } 
} 

void adjust_down(int a[],int start, int end)
{
    int root = start,temp,bigger_child;
    while(2*root <= end)
    {
        if(2*root+1 > end)
        {
            if(a[2*root]<a[root])
            {
                temp=a[root];
                a[root]=a[2*root];
                a[2*root]=temp;
            }
            root=2*root;
        }
        else
        {
            bigger_child = (a[2*root]>a[2*root+1])? 2*root : 2*root+1;
            if(a[root]<a[bigger_child])
            {
                temp=a[root];
                a[root]=a[bigger_child];
                a[bigger_child]=temp;
            }
            root=bigger_child;
        }
    }
}

void print_array(int x[],int size) 
{ 
    int i; 
    for(i=0;i<size;i++) 
        printf("%d\t",x[i+1]); 
    putchar('\n'); 
} 
-----------------------------------------------------------

The approach:
   The approach is simple. This program uses a max heap to sort the numbers in ascending order. You know that in a max heap root is largest element. This program works on the below logic:
1. first take an array from user. Notice that I have saved the elements from index one leaving index 0 empty. See remark1 below.
2. make that array to satisfy max heap property(max - heapify array).
3. Now swap last element of heap with the root. So that the biggest element comes last.
4. Now leave the last element and assume rest array as heap.
5. Adjust the new heap so satisfy max heap property.
6. Repeat step 3-5 till only root is left as rest part of heap.
7. You will be getting an increasingly sorted array.
you can refer to wikipedia for more theory and graphics about heap sort.

Remark:
1. This is the convention I follow when I implement heap on an array because this gets you left and right children as 2*current_node, and (2*current_node + 1). You can use other convention of starting with index 0. In that case left and right children will be evaluated (2*current_node+1), and (2*current_node + 2) which seems a little bigger expressions to me :P

Concept of Heap in C

Heap is a concept which can be implemented on trees, priority queues and arrays. When we plot a heap on paper, we draw it as binary tree. We also analyse a heap as a binary tree. There are 2 types of heaps:
1. min heap: parent node is always less than both children.
2. max heap: parent node is always greater than both children.
In both the cases equality is permitted. No other property is required for a heap. We do not care about any other thing like which child is greater.

Heap can be utilized in
1. heapsort
2. a priority queue can be implemented with a heap
3. auto balancing binary tree

For general purposes this much on heap is enough. For more you can study in details on wikipedia.