Время сортировки,таймер, С++ Опции

[Rocket]

Вот программа, задача которой сортировать массив тремя способами(метод пузырька, вставки, переборки), при этом каждый метод сортировки прогоняется 100 раз, засекается время и считается среднее время.

#include<iostream>
#include<conio.h>
#include<windows.h>

using namespace std;

void BS(int a[], long size)
 {
  long i,j;
  int x;
 
 for(i=0;i<size;i++)				
  {		   
	for(j=size-1;j >i;j--)		   
	{   
	  if (a[j-1]>a[j])
	 {
	  x=a[j-1];
	  a[j-1]=a[j]; 
	  a[j]=x;
	 }
	}
	 
  }
 }
 

void IS(int a[], long size)
{
  int x;
  long i, j;

  for (i=0;i<size;i++)			   
   { 
	x=a[i];
		
	for (j=i-1;j>=0&&a[j]>x;j--)
	  a[j+1]=a[j];												 
	a[j+1]=x;
	
	
  }
}

void CS(int a[], long size)
{
  long i,j,k; 
  int x;
	 
  for(i=0;i<size;i++)
   {  
	k=i;
	x=a[i];

	for( j=i+1;j<size;j++)		 
	  if (a[j]<x) 
	  {
		k=j;					
		x=a[j];		  
	  }

	a[k]=a[i];				  
	a[i]=x;  
   }
}
 
 void Message()
{
	cout<<endl;
	cout<<"Please, choose the method of sorting massive!"<<endl<<endl; 
	
	cout<<"1. BubbleSort "<<endl;
	cout<<" 2. ChoiceSort "<<endl;
	cout<<"  3. InsertSort "<<endl<<endl;;
	cout<<"Enter 'ESC' for Exit!"<<endl<<endl;
	 }
 
int main() {

int ch,size;

cout<<"Please, enter the size of massive to sort!"<<endl;   
cin>>size;

int *a = new int[size]; 
cout<<"Massive of rand elements:";
for(int i=0;i<size;i++)
			  {
				a[i]=rand()%100; 
			  }
			
			   for(int i=0;i<size;i++)
				{
				  cout<<a[i]<<" ";
				}
	 
		  cout << endl;

 while (ch !=27)
	   
  {  
	   Message();
	   ch = getch();
	 
		 switch(ch)
		 
  {	case 49:
	   
	  {		 float time=GetTickCount();
	  
				for(int j=0; j<100; j++) 
				BS(a, size); 
				
				time=GetTickCount()-time; 
				
				cout<<"Using BubbleSort: ";
				for(int i=0; i<size;i++)
				 {
				   cout<<a[i]<<" ";
				 }
	   
		  cout<<endl;
		  cout<<"time = "<<time/100<<endl;

	   }
	   
		 break;
		 
	   case 50:
			
			{	float time=GetTickCount();
			
				 for(int j=0; j<100; j++) 
				 CS(a, size); 
				 
				 time=GetTickCount()-time; 
				 
				 cout<<"Using ChoiceSort: ";
				 for(int i=0; i<size;i++)
				 {
				   cout<<a[i]<<" ";
				 }
	   
		  cout<<endl;
		  cout<<"time = "<<time/100<<endl;

	   }
			
		 break;
		 
	   case 51:
			
			{  float time=GetTickCount();
					  
			   for(int j=0; j<100; j++)	  
			   IS(a, size); 
			   
			   time=GetTickCount()-time; 
			   
			   cout<<"Using IsertSort: ";
			   for(int i=0; i<size;i++)
				 {
				   cout<<a[i]<<" ";
				 }
	   
		  cout<<endl;
		  cout<<"time = "<<time/100<<endl;
   
	   }
			
		 break;
	  }
	  }
	  delete a;
	  }

Столкнулся с тем, что при размерах массивов достаточно маленьких( ну там 10, 100) переменная time выдает 0, это в принципе понятно-метод быстро справляется со своей задачей, но всё-таки как сделать, чтоб выводилось хоть какое-нибудь значение time, даже на маленьких размерах массивов.

Сообщение отредактировано: volvo - 5.04.2010 13:04

[volvo]

Ну, это смотря, какой компилятор... У меня на GCC отработало вот такое:

static inline long long get_time(void)
{
        long long l;
        asm volatile(   "rdtsc\n\t"
                : "=A" (l)
        );
        return l;
}

...
  long long time = get_time();
  // здесь сама сортировка ...
  time = get_time() - time;

Если у тебя VC, то достаточно:

unsigned __int64 get_time()
{
    __asm rdtsc;
}

  __int64 time = get_time();
  // здесь сама сортировка ...
  time = get_time() - time;

Сообщение отредактировано: volvo - 13.09.2008 22:30

[Rocket]

Ну, это смотря, какой компилятор...

У меня Dev-C++ 4.9.9.2

[volvo]

Dev-C++ это IDE... Компилятор в ней какой? Насколько я помню, там был тоже GCC...

[andriano]

Путей два:
1. Увеличить количество повторений цикла, чтобы получить большее время работы.
2. Измерять время более точным таймером.
Первый вариант выглядит предпочтительнее, т.к. обеспечивает более высокую точность.
По поводу второго: если это Windows, попытайся использовать QueryPerformanceFrequency/QueryPerformanceCounter.