Thread: Help to break a loop with time out

Hi everyone ! It will be quite long so I will be direct.
I aim to execute a series of time tests on several sorting algorithms for some project to compare them.
For each sort (bubble sort, insertion sort etc...), I have to run the algorithm for different sizes among : 100, 500, 5000, 10000, 50000, 100000, 200000, 300000, 400000 & 500000 elements and for each size, I have to execute the code on 20 different arrays which should be filled randomly.


Let have the bubble sort algorithm, I post here the program which, taken an array in disorder, make all the correct operations to return it in ascending order :

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 500000


typedef int ARRAY[MAX];


void swap(ARRAY A, int val1, int val2){ 
    int value = A[val1];
    A[val1] = A[val2];
    A[val2] = value;
}


void bubble_sort(TABLEAU T, int n){ /*
You should note that the function is taking n in argument so that, taken an array of 500000 elements, it sorts only on the n first elements
*/
    int i, j;
    for(i = n; i > 0; i--)
        for(j = 0; j < i; j++)
                if (A[j] > A[j+1])
                    swap(A, j, j+1);
}

Eventualy we would have to display the array in question like this but it is not very important here :

Code:

void display(ARRAY A, int n){/*
Again it only displays the same n first demanded values of the array
that are actually sorted
*/ 
    int i;
    for(i = 0; i < n; i++)
        printf("%d ", A[i]);
}

I should precise some additional things :


We evaluate a series of tests like this : for each among the 20 arrays to be run, we take the time of execution of the calling of the bubble sort function. We sum up all of these times then we divide by the number of the arrays treated (optimally 20). It gives for each size of array the average time of execution of a sort.


for each series of test of a same size of array, if the time to execute the series is beyond 5mn, I have to stop the series and go for the next size series. For example, with a series of 20 arrays of 50,000 elements, if the sorting of the third ones arrays makes time go over 5mn, I stop and the average time for this series will be : Time elapsed / 3, then I switch to the series of arrays of 100,000 elements.




So I wrote the lines & the main function below to automate the tests :

Code:

void(*pbubble_sort)(ARRAY, int);


int sizes[10] = {100, 500, 5000, 10000, 50000, 100000, 200000, 300000, 400000, 500000};


int main(void){


    pbubble_sort = &buble_sort;
    ARRAY A;
    int i, j, k, nb_array;
    float timer;
    clock_t start, end;


    for(i = 0; i < 10; i++){
        timer = 0.0;
        nb_array = 0;
        for(j = 0; j < 20; j++){
            srand(time(0));     /*
                                   Initialize the random numbers generator
                                     */
            for(k = 0; k < sizes[i]; k++)
                A[k] = (unsigned int)rand();
            
            start = clock();
            (*pbubble_sort)(A, sizes[i]);
            end = clock();    /*
                    Here I take the time of the calling of the function
                              */


            float t = (end - start) * 1.0 / CLOCKS_PER_SEC;
            if (timer + t > 5.0*60.0){ 
                printf("\nNon finished session\n"); /*
                                                               Here I indicate whether a  series of test is finished or not compared with the time of 5 mns.
                                                               */
                break;  /*then I go out of the loop*/
            }
            else {
                timer += t;    
                nb_arrays += 1;
            }
        }
        float average_time = timer / nb_arrays;
        printf("\n Size %d : Average = %f\n", sizes[i], average_time);
    }
}

It actually works pretty well, but as you know, the bubble sort is the slowest of all the sorting algorithms, so I must wait for nearly half an hour to end the program. From the size of 200,000 elements, as it longs more than 5mn to execute one sorting of one array, none of the 20 arrays can be sorted in time, so the average time is equal to infinite value, which is theorically correct compared with the limit of 5 mns which we have set.


But the problem is that even though the program checks for the 5mn overtaking, it can only check it AFTER the calling of the function. So it isn't useful at all when I begin the series of arrays of 500,000 elements where a simple calling for an array may take huge huge time (20mn for example).
So I would force the for loop inside which assume the calculus of the time to stop automatically after 5mn, even if the calling of the function bubble_sort is still in process and has no returned (and which probably will return 20 mns later) to avoid lose time for Nothing.


So, the total time of execution would cost me 5mn (time maximum for one loop) * 10 (different sizes) to the worst, assuming that it's not the case because when 100 or 500 elements, the time of execution is ridiculously low.


I heard about this problem can be solved with Threads but I don't know how it works. If someone could have helped me on this project, I will greatly thank hiM
I assume that the biggest task for the potential helpers would be to read this post to the very end


I hope I make myself clear and I thank everyone who could help me

Why don't you check the time at the end of each outer loop of your sort?

I think Salem's suggestion is to code the bubble sort something like this:

Code:

#define MAX_TIME (5.0 * 60.0)
#define SECONDS_SINCE(t) ((double)(clock() - (t)) / CLOCKS_PER_SEC)

double bubble_sort(ARRAY A, int n, double total_time){
    int i, j;
    double seconds = 0.0;
    clock_t start = clock();
    for(i = n; i > 0; i--) {
        for(j = 0; j < i; j++)
            if (A[j] > A[j+1])
                swap(A, j, j+1);
        seconds = SECONDS_SINCE(start);
        if (total_time + seconds >= MAX_TIME)
            break;
    }
    return seconds;
}

If you want to use threads then you'll need to read up on pthreads, mutexes and condition variables, and employ the pthread_cond_timedwait function.

At least john.c knew what I meant.

As for respecting your requirements, any thread mess will blow any perceived accuracy out of the water.

Perhaps you should incorporate knowledge of your algorithms into the code.
If 100k items took 3 mins to sort, then you can predict in advance that 200k items will exceed your limit without even trying.

It's a compromise between reading too often, in which case you waste time checking the clock, or going over 5 minutes by several hours.

Does it really matter if you find you exited at say 5:22?

Originally Posted by Salem

It's a compromise between reading too often, in which case you waste time checking the clock, or going over 5 minutes by several hours.

Does it really matter if you find you exited at say 5:22?

You're right, I chose the solution given by john.c. It seems to be better. Even with 500,000 elements, it replies within nearly 15 seconds when I call the function bubble_sort like this

Code:

int main(void){
    ARRAY A;
    int r;
    srand(time(0));
    for(r = 0; r < 500000; r++)
        T[r] = (unsigned int) rand();
    bubble_sort(A, 500000, 285);
}

I know I'm feeling tired, but I don't understand why the result is 15000 and not 15, though the time has been converted in seconds a few times before ? Anyone has an explanation ?

I absolutely don't know why

How exactly are you printing the result?
You're ignoring the return result.

You're absolutely right, I dont know what I have since some days but I should get some sleep. Thank you very much, I will repost when I finish

Post your merge sort algorithm and I'll take a look at it.

BTW, you don't need to check the time every iteration of the outer loop. Every 100th iteration (maybe even every 1000th) would be good enough and still respond within a fraction of a second. That way you won't be making hundreds of thousands of calls to clock() (for no real reason).

Code:

        if (i % 100 == 0) {
            seconds = SECONDS_SINCE(start);
            if (total_time + seconds > MAX_TIME)
                break;
        }

Also, in main "nb_arrays" is basically just a copy of j, so you may as well do this:

Code:

    srand(time(0));  // this should only be called once!
    for(i = 0; i < 10; i++){
        loop_timer = 0.0;
        for(nb_arrays = 0; nb_arrays < 20; nb_arrays++){
            for(r = 0; r < sizes[i]; r++)
                A[r] = rand();
            double t = pbubble_sort(A, sizes[i], loop_timer);
            if (loop_timer + t > MAX_TIME){
                printf("\nNon terminated series, %d tests done\n",
                       nb_arrays);
                break;
            }
            loop_timer += t;
        }
        printf("\nSize of %d elements :  average %f seconds\n", sizes[i],
               loop_timer / nb_arrays);
    }

Originally Posted by ElPosto

And now, what if my algorithm is recursive ? How can I check time elapsed in the recursive function inside ?

Give me a recursive function to work with. I don't feel like whipping one up myself.