0
У меня проблема с функцией часов. Есть массив, переданный функции, и мы должны измерить время, которое требуется для поиска. Я также делаю это с функциями сортировки и, похоже, работает без проблем. Прошедший массив предварительно задан.вопросов с функцией часов C
В результате результаты получают 0,0000 и -1,9500. Печать f для совпадения времени. Я повторно использую это в других функциях, поскольку программа измеряет время для 3-х видов, 2 поисковых запроса, для массивов от 10 до 20000 номеров.
// linear search from book
void linearSearch(int *list, int size, int key) // int key taken out
{
//returns the location of key in the list
// a-1 is returned if value is not found
int index, found, i;
clock_t t6 = 0;
clock_t t7 = 0;
clock_t diff =0;
double timefin;
//float diff;
index = -1;
found = FALSE;
i = 0;
t6 = clock();
while (i < size && !found)
{
if (list[i] == key)
{
found = TRUE;
index = i;
}
i++; //Move to the next item
}
t7 =clock();
diff =t7 - t6;
printf("\nt6: %f", (float)t6);
printf("\nt7: %f", (float)t7);
//diff = (((float)t7 - (float)t6)/1000000.0F);
printf("\nThe Linear search for %d took %.4f seconds",key, (float)diff);
// return(index);
}
полный код, используя GDB для компиляции и запуска на Ubuntu.
#include <stdio.h>
#include <math.h>
#include <ctype.h>
#include <stddef.h>
#include <time.h>
#include <sys/times.h>
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define randScope 20000
// random number generator
void randNum(int *num, int sizeNum, int maxRand)
{
int i;
time_t t;
srand((unsigned) time(&t));
for(i=0; i<sizeNum; i++)
num[i]= rand() % maxRand;
//return 0;
}
int randOneNum(int maxRand)
{
int num;
time_t t;
srand((unsigned) time(&t));
num= rand() % maxRand;
return num;
}
// bubble sort from book
int bubbleSort(int *num, int sizeSort)
{
int i, j, temp, moves =0;
clock_t t0 = 0;
clock_t t1 = 0;
double timefin;
clock_t diff;
// for(i =0; i < 3; i++)
// printf ("\nStart Numbers %d", num[i]);
t0 = clock();
for(i =0; i < (sizeSort -1); i++)
{
for(j =0; j < (sizeSort -1); j++)
{
if (num[j] < num [j-1])
{
temp = num[j];
num[j] = num[j-1];
num[j-1] = temp;
moves++;
}
}
}
t1 = clock();
diff = t1-t0;
printf("\nt0: %f", (float)t0);
//diff = (((float)t1 - (float)t0)/1000000.0F);
// for(i =0; i < 3; i++)
// printf ("\nSorted numbers %d", num[i]);
printf("\nThe Bubble sort for %d numbers took %.4f seconds",sizeSort, (float)diff);
return (moves);
}
// selection sort from book
int selectionSort(int *num, int sizeSort)
{
int i,j, min, minidx, temp,moves = 0;
clock_t t2 = 0;
clock_t t3 = 0;
double timefin;
clock_t diff;
// for(i =0; i < 3; i++)
// printf ("\nStart Numbers %d", num[i]);
t2 = clock();
for(i =0; i < (sizeSort -1); i++)
{
min = num[i]; /* assume minimum is first element in the sublist */
minidx=i; /*index*/
for(j=i+1; j<sizeSort; j++)
{
if (num[j] < min) /* lower value found capture it */
{
min = num[j];
minidx =j;
}
}
if (min < num[i]) /* check if we have a new min if so swap values*/
{
temp = num[i];
num[i] = min;
num[minidx] = temp;
moves++;
}
}
t3 = clock();
diff = t3-t2;
printf("\nt2: %f", (float)t2);
//diff = (((float)t3 - (float)t2)/1000000.0F);
// for(i =0; i < 3; i++)
// printf ("\nSorted numbers %d", num[i]);
printf("\nThe Selection sort for %d numbers took %.4f seconds",sizeSort, (float)diff);
return (moves);
}
//insertion sort from Rostetta code http://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort#C
static void insertion_sort(int *num, int sizeSort)
{
int i, j, value;
clock_t t4 = 0;
clock_t t5 = 0;
double timefin;
clock_t diff;
// for(i =0; i < 3; i++)
// printf ("\nStart Numbers %d", num[i]);
t4 = clock();
for (i = 1; i < sizeSort; i++) {
value = num[i];
for (j = i; j > 0 && value < num[j - 1]; j--) {
num[j] = num[j - 1];
}
num[j] = value;
}
t5 = clock();
diff = t5-t4;
printf("\nt4: %f", (float)t4);
//diff = (((float)t5 - (float)t4)/1000000.0F);
// for(i =0; i < 3; i++)
// printf ("\nSorted numbers %d", num[i]);
printf("\nThe Insertion sort for %d numbers took %.4f seconds",sizeSort, (float)diff);
}
// linear search from book
void linearSearch(int *list, int size, int key) // int key taken out
{
//returns the location of key in the list
// a-1 is returned if value is not found
int index, found, i;
clock_t t6 = 0;
clock_t t7 = 0;
clock_t diff =0;
double timefin;
//float diff;
index = -1;
found = FALSE;
i = 0;
t6 = clock();
while (i < size && !found)
{
if (list[i] == key)
{
found = TRUE;
index = i;
}
i++; //Move to the next item
}
t7 =clock();
diff =t7 - t6;
printf("\nt6: %f", (float)t6);
printf("\nt7: %f", (float)t7);
//diff = (((float)t7 - (float)t6)/1000000.0F);
printf("\nThe Linear search for %d took %.4f seconds",key, (float)diff);
// return(index);
}
// binary search from book
void binarySearch(int *list, int size, int key) // int key taken out
{
// returns the locations of key in the list if a-1 is returned the value is not found
int index, found, left,right, midpt;
clock_t t8 = 0;
clock_t t9 = 0;
clock_t start,end;
struct tms st_cpu;
struct tms end_cpu;
double timefin;
clock_t diff;
index = -1;
found = FALSE;
left = 0;
right = size-1;
t8 = clock();
while(left <= right && !found)
{
midpt = (int) ((left + right) /2);
if (key == list[midpt])
{
found = TRUE;
index = midpt;
}
else if (key > list[midpt])
left = midpt + 1;
else
right = midpt -1;
}
t9 = clock();
diff = t9-t8;
printf("\nt8: %f", (float)t8);
//diff = (((float)t9 - (float)t8)/1000000.0F);
printf("\nThe Binary search for %d took %.4f seconds",key, (float)diff);
// return index;
}
void main()
{
// insertion_sort(a, sizeof a/sizeof a[0]);
//10, 50, 100, 500, 1000, 5000, 10000, 15000, 20000
int i;
int key[9];
// Bubble Sort Arrays
int numB10[10];
int numB50[50];
int numB100[100];
int numB500[500];
int numB1000[1000];
int numB5000[5000];
int numB10000[10000];
int numB15000[15000];
int numB20000[20000];
// Selection Sort Arrays
int numS10[10];
int numS50[50];
int numS100[100];
int numS500[500];
int numS1000[1000];
int numS5000[5000];
int numS10000[10000];
int numS15000[15000];
int numS20000[20000];
// Insertion Sort Arrays
int numI10[10];
int numI50[50];
int numI100[100];
int numI500[500];
int numI1000[1000];
int numI5000[5000];
int numI10000[10000];
int numI15000[15000];
int numI20000[20000];
// initialize random array
randNum(numB10000, 10000, 20000);
// Initialize keys for search
key[0]=numB10000[randOneNum(10)];
key[1]=numB10000[randOneNum(50)];
key[2]=numB10000[randOneNum(100)];
key[3]=numB10000[randOneNum(500)];
key[4]=numB10000[randOneNum(1000)];
key[5]=numB10000[randOneNum(5000)];
key[6]=numB10000[randOneNum(10000)];
key[7]=numB10000[randOneNum(15000)];
key[8]=numB10000[randOneNum(20000)];
// Copy array to size 10 arrays
memcpy(numI10, numB10000, 10*sizeof(int));
memcpy(numS10, numB10000, 10*sizeof(int));
memcpy(numB10, numB10000, 10*sizeof(int));
// Copy array to size 50 arrays
memcpy(numI50, numB10000, 50*sizeof(int));
memcpy(numS50, numB10000, 50*sizeof(int));
memcpy(numB50, numB10000, 50*sizeof(int));
// Copy array to size 100 arrays
memcpy(numI100, numB10000, 100*sizeof(int));
memcpy(numS100, numB10000, 100*sizeof(int));
memcpy(numB100, numB10000, 100*sizeof(int));
// Copy array to size 500 arrays
memcpy(numI500, numB10000, 500*sizeof(int));
memcpy(numS500, numB10000, 500*sizeof(int));
memcpy(numB500, numB10000, 500*sizeof(int));
// Copy array to size 1000 arrays
memcpy(numI1000, numB10000, 1000*sizeof(int));
memcpy(numS1000, numB10000, 1000*sizeof(int));
memcpy(numB1000, numB10000, 1000*sizeof(int));
// Copy array to size 5000 arrays
memcpy(numI5000, numB10000, 5000*sizeof(int));
memcpy(numS5000, numB10000, 5000*sizeof(int));
memcpy(numB5000, numB10000, 5000*sizeof(int));
// Copy array to size 10000 arrays
memcpy(numI10000, numB10000, 10000*sizeof(int));
memcpy(numS10000, numB10000, 10000*sizeof(int));
memcpy(numB10000, numB10000, 10000*sizeof(int));
// Copy array to size 15000 arrays
memcpy(numI15000, numB20000, 15000*sizeof(int));
memcpy(numS15000, numB20000, 15000*sizeof(int));
memcpy(numB15000, numB20000, 15000*sizeof(int));
// Copy array to size 20000 arrays
memcpy(numI20000, numB20000, 20000*sizeof(int));
memcpy(numS20000, numB20000, 20000*sizeof(int));
//10
selectionSort(numS10, 10);
bubbleSort(numB10, 10);
insertion_sort(numI10, 10);
linearSearch(numI10, 10, key[0]);
binarySearch(numI10, 10, key[0]);
printf("\n");
//50
selectionSort(numS50, 50);
bubbleSort(numB50, 50);
insertion_sort(numI50, 50);
linearSearch(numI50, 50, key[1]);
binarySearch(numI50, 50, key[1]);
printf("\n");
//100
selectionSort(numS100, 100);
bubbleSort(numB100, 100);
insertion_sort(numI100, 100);
linearSearch(numI100, 100, key[2]);
binarySearch(numI100, 100, key[2]);
printf("\n");
//500
selectionSort(numS500, 500);
bubbleSort(numB500, 500);
insertion_sort(numI500, 500);
linearSearch(numI500, 500, key[3]);
binarySearch(numI500, 500, key[3]);
printf("\n");
//1000
selectionSort(numS1000, 1000);
bubbleSort(numB1000, 1000);
insertion_sort(numI1000, 1000);
linearSearch(numI1000, 1000, key[4]);
binarySearch(numI1000, 1000, key[4]);
printf("\n");
//5000
selectionSort(numS5000, 5000);
bubbleSort(numB5000, 5000);
insertion_sort(numI5000, 5000);
linearSearch(numI5000, 5000, key[5]);
binarySearch(numI5000, 5000, key[5]);
printf("\n");
//10000
selectionSort(numS10000, 10000);
bubbleSort(numB10000, 10000);
insertion_sort(numI10000, 10000);
linearSearch(numI10000, 10000, key[6]);
binarySearch(numI10000, 10000, key[6]);
printf("\n");
//15000
selectionSort(numS15000, 15000);
bubbleSort(numB15000, 15000);
insertion_sort(numI15000, 15000);
linearSearch(numI15000, 15000, key[7]);
binarySearch(numI15000, 15000, key[7]);
printf("\n");
//20000
selectionSort(numS20000, 20000);
bubbleSort(numB20000, 20000);
insertion_sort(numI20000, 20000);
linearSearch(numI20000, 20000, key[8]);
binarySearch(numI20000, 20000, key[8]);
}
Вот результат, который я получаю.
t2: 0.000000
The Selection sort for 10 numbers took 0.0000 seconds
t0: 0.000000
The Bubble sort for 10 numbers took 0.0000 seconds
t4: 0.000000
The Insertion sort for 10 numbers took 0.0000 seconds
t6: 0.000000
t7: 0.000000
The Linear search for 1781 took 0.0000 seconds
t8: 0.000000
The Binary search for 1781 took 0.0000 seconds
t2: 0.000000
The Selection sort for 50 numbers took 0.0000 seconds
t0: 0.000000
The Bubble sort for 50 numbers took 0.0000 seconds
t4: 0.000000
The Insertion sort for 50 numbers took 0.0000 seconds
t6: 0.000000
t7: 0.000000
The Linear search for 1744 took 0.0000 seconds
t8: 0.000000
The Binary search for 1744 took 0.0000 seconds
t2: 0.000000
The Selection sort for 100 numbers took 0.0000 seconds
t0: 0.000000
The Bubble sort for 100 numbers took 0.0000 seconds
t4: 0.000000
The Insertion sort for 100 numbers took 0.0000 seconds
t6: 0.000000
t7: 0.000000
The Linear search for 1744 took 0.0000 seconds
t8: 0.000000
The Binary search for 1744 took 0.0000 seconds
t2: 0.000000
The Selection sort for 500 numbers took 0.0000 seconds
t0: 0.000000
The Bubble sort for 500 numbers took 0.0000 seconds
t4: 0.000000
The Insertion sort for 500 numbers took 0.0000 seconds
t6: 0.000000
t7: 0.000000
The Linear search for 17032 took 0.0000 seconds
t8: 0.000000
The Binary search for 17032 took 0.0000 seconds
t2: 0.000000
The Selection sort for 1000 numbers took 10000.0000 seconds
t0: 10000.000000
The Bubble sort for 1000 numbers took 10000.0000 seconds
t4: 20000.000000
The Insertion sort for 1000 numbers took 0.0000 seconds
t6: 20000.000000
t7: 20000.000000
The Linear search for 8704 took 0.0000 seconds
t8: 20000.000000
The Binary search for 8704 took 0.0000 seconds
t2: 20000.000000
The Selection sort for 5000 numbers took 110000.0000 seconds
t0: 130000.000000
The Bubble sort for 5000 numbers took 400000.0000 seconds
t4: 530000.000000
The Insertion sort for 5000 numbers took 80000.0000 seconds
t6: 610000.000000
t7: 610000.000000
The Linear search for 17877 took 0.0000 seconds
t8: 610000.000000
The Binary search for 17877 took 0.0000 seconds
t2: 610000.000000
The Selection sort for 10000 numbers took 430000.0000 seconds
t0: 1040000.000000
The Bubble sort for 10000 numbers took 1600000.0000 seconds
t4: 2640000.000000
The Insertion sort for 10000 numbers took 330000.0000 seconds
t6: 2970000.000000
t7: 2970000.000000
The Linear search for 3961 took 0.0000 seconds
t8: 2970000.000000
The Binary search for 3961 took 0.0000 seconds
t2: 2970000.000000
The Selection sort for 15000 numbers took 970000.0000 seconds
t0: 3940000.000000
The Bubble sort for 15000 numbers took 2950000.0000 seconds
t4: 6890000.000000
The Insertion sort for 15000 numbers took 0.0000 seconds
t6: 6890000.000000
t7: 6890000.000000
The Linear search for 17877 took 0.0000 seconds
t8: 6890000.000000
The Binary search for 17877 took 0.0000 seconds
t2: 6890000.000000
The Selection sort for 20000 numbers took 1760000.0000 seconds
t0: 8650000.000000
The Bubble sort for 20000 numbers took 5790000.0000 seconds
t4: 14440000.000000
The Insertion sort for 20000 numbers took 0.0000 seconds
t6: 14440000.000000
t7: 14440000.000000
The Linear search for 1074 took 0.0000 seconds
t8: 14440000.000000
The Binary search for 1074 took 0.0000 seconds
Хорошо говорил с преподавателем, еще не проверял его, но мы полагаем, что компилятор оптимизирует код, одновременно управляя вещами и тем самым приступая к быстрым поискам и странным таймингам. Попытка сравнять этот размер с размером введенного массива пользователя и сделать по одному за списками поисков и сортировок – Wilken
Обратите внимание, что ПК быстро * очень быстро делают это, я просто выполнил линейный поиск через 100 000 int's Total time : 52uS - это 0.000052 секунды (или 0.00000000052 сек. За цикл!) На 3GHz i7 windows PC – TonyWilk