sibsutis/1Y-2H/dsa/lab1/main.c

#include "head.h"

int main(int argc,char **argv) {
    srand(rdtsc());
    
    if(argc>1){
        switch(argv[1][0]){
        case '1':
            run_exp1();
            break;
        case '2':
            run_exp2();
            break;
        case '3':
            {
                if(!(argv[1][1]>='a'&&argv[1][1]<='z')) return 0;
            int key = 1,n = 100;
            printf("Write key:");
            scanf("%d",&key);
            while(getchar()>'\n');
            printf("Write n:");
            scanf("%d",&n);
            while(getchar()>'\n');
            int *arr = (int*)malloc(sizeof(int) * n);
            fill_rand(arr, n);
            arr[get_rand(0,n)] = key;
            merge_sort(arr, n);
            for(int i = 0; i<n;i++)printf("%d ",arr[i]);
            switch(argv[1][1]){
                case 'l':
                    printf("\nэлемент N%d\n",linear_Search(arr, n, key));
                    break;
                case 'b':
                    printf("\nэлемент N%d\n",binary_Search(arr, n, key));
                    break;
                case 'e':
                    merge_sort(arr, n);
                    printf("\nэлемент N%d\n",exponential_Search(arr, n, key));
                    break;
                default:
                    break;
            }
            free(arr);
        default:
            return 0;
            }
        }
    }
    else{
        run_exp1();
        run_exp2();
    }
    return 0;
}


void run_exp1() {
    FILE *f = fopen("table1.dat", "w");
    if (!f) return;

    int start = 5000, end = 5000000, step = 5000;
    fprintf(f, "# N Lin Bin Exp\n");

    for (int n = start; n <= end; n += step) {
        if(n==step*40+step){
            step=250000;
            n=250000;
            fprintf(f,"\n");
        }

        int *arr = (int*)malloc(sizeof(int) * n);
        fill_rand(arr, n);

        unsigned long long tLinTotal = 0;
        for (int i = 0; i < AVG_TIME_LOOPS; i++) {
            int key = get_rand(0, AVG_RAND_MAX);
            unsigned long long t = rdtsc();
            linear_Search(arr, n, key);
            tLinTotal += (rdtsc() - t);
        }
        double tLinRes = (double)tLinTotal / AVG_TIME_LOOPS;

        merge_sort(arr, n);

        unsigned long long tBinTotal = 0;
        for (int i = 0; i < AVG_TIME_LOOPS; i++) {
            int key = get_rand(0, AVG_RAND_MAX);
            unsigned long long t = rdtsc();
            binary_Search(arr, n, key);
            tBinTotal += (rdtsc() - t);
        }
        double tBinRes = (double)tBinTotal / AVG_TIME_LOOPS;

        unsigned long long tExpTotal = 0;
        for (int i = 0; i < AVG_TIME_LOOPS; i++) {
            int key = get_rand(0, AVG_RAND_MAX);
            unsigned long long t = rdtsc();
            exponential_Search(arr, n, key);
            tExpTotal += (rdtsc() - t);
        }
        double tExpRes = (double)tExpTotal / AVG_TIME_LOOPS;

        fprintf(f, "%d %.4f %.4f %.4f\n", n, tLinRes, tBinRes, tExpRes);
        printf("Progress Table 1: %d/%d\r", n, end);
        fflush(stdout);
        free(arr);
    }
    fclose(f);
    printf("\nTable 1 done.\n");
}

void run_exp2() {
    FILE *f = fopen("table2.dat", "w");
    if (!f) return;

    for(int n = MILLION; n <= MILLION*5;n*=5){
        int *arr = (int*)malloc(sizeof(int) * n);
        fill_rand(arr,n);
        fprintf(f, "# N K Lin Bin Bin+Sort Sort \n");
        
        unsigned long long t = rdtsc();
        merge_sort(arr,n);
        double tSortRes = rdtsc() - t;

        int modif = (n == MILLION) ? 1:2;
        for(int k = 50*modif;k<=500*modif;k+=50*modif){    
            int kmax = (n == MILLION) ? 500 : 1000;
            
            unsigned long long tLinTotal = 0;
            for(int i = 0;i<=k;i++){
                for (int j = 0; j < AVG_TIME_LOOPS; j++) {
                    int key = get_rand(0, AVG_RAND_MAX);
                    unsigned long long t = rdtsc();
                    linear_Search(arr, n, key);
                    tLinTotal += (rdtsc() - t);
                }
            }
            double tLinRes = (double)tLinTotal / AVG_TIME_LOOPS;

            unsigned long long tBinTotal = 0;
            for(int i = 0;i<=k;i++){
                for (int j = 0; j < AVG_TIME_LOOPS; j++) {
                    int key = get_rand(0, AVG_RAND_MAX);
                    unsigned long long t = rdtsc();
                    binary_Search(arr, n, key);
                    tBinTotal += (rdtsc() - t);
                }
            }
            double tBinRes = (double)tBinTotal / AVG_TIME_LOOPS;
            fprintf(f, "%d %d %.3f %.3f %.3f %.2f\n", n/1000, k*modif, tLinRes, tBinRes, tBinRes+tSortRes,tSortRes);
            
            printf("Progress Table 2: %d/%d\r", k, kmax);
            fflush(stdout);
        }
        
        free(arr);
    }//CloseFor
    fclose(f);
    printf("\nTable 2 done.\n");
}

int get_rand(int min, int max) {
     return (double)rand() / (RAND_MAX + 1.0) * (max - min) + min;
}

void fill_rand(int *arr, int n) {
    for (int i = 0; i < n; i++) arr[i] = get_rand(0, AVG_RAND_MAX);
}

unsigned long long rdtsc() {
    unsigned int lo, hi;
    __asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi));
    return ((unsigned long long)hi << 32) | lo;
}