我的关于性能测试的想法
先定义一个基类Action，定义比较，移动的方法，同时有记录的变量。
[CODE]template <class T>
class Action
{
public:
pair<int,int> result;
Action() { result.first = 0; result.second = 0; }
bool lessthan(T &a, T &b)
{
result.first++;
return a < b;
}
void move(T &dest, T &source)
{
dest = source;
result.second++;
}
void Swap(T &a, T &b)
{
swap(a, b);
result.second += 3;
}
};[/CODE]
然后每种排序定义为一个由Action派生的类型，其中的比较，移动用基类的方法，如
[CODE]template <class T>
class InsertionSort : public Action<T>
{
void insertionsort(T *begin, T *end)
{
T *p, *q;
T tmp;
for(p=begin+1; p!=end; p++)
{
move(tmp, *p); //--
for(q=p; q!=begin && lessthan(tmp, *(q-1)); q--) //--
move(*q, *(q-1)); //--
move(*q, tmp); //--
}
}
public:
pair<int,int> operator()(T *begin, T *end)
{
Action<T>::result.first = 0;
Action<T>::result.second = 0;
insertionsort(begin, end);
return Action<T>::result;
}
};[/CODE]
[CODE]template <class T>
class HeapSort : public Action<T>
{
void movedown(T *data, int first, int last)
{
int largest = 2*first + 1;
while(largest <= last)
{
if( largest<last && lessthan(data[largest],data[largest+1]) ) //--
largest++;
if( lessthan(data[first], data[largest]) ) //--
{
Swap(data[first], data[largest]); //--
first = largest;
largest = largest*2 + 1;
}
else
break;
}
}
void heapsort(T *begin, T *end)
{
int size = end - begin;
for(int i=size/2-1; i>=0; i--)
movedown(begin, i, size-1);
for(int j=size-1; j>0; j--)
{
Swap(*begin, *(begin+j)); //--
movedown(begin, 0, j-1);
}
}
public:
pair<int,int> operator()(T *begin, T *end)
{
Action<T>::result.first = 0;
Action<T>::result.second = 0;
heapsort(begin, end);
return Action<T>::result;
}
};[/CODE]
我又加了一个函数，这个也许没有必要。
[CODE]template <class T, class U>
pair<int,int> Test(T *begin, T *end, U func)
{
return func(begin, end);
}[/CODE]
测试的主函数，
[CODE]int main()
{
const int N = 1000;
int ar[N], br[N];
for(int i=0; i<N; i++)
ar[i] = br[i] = Random::get().random();
for(int i=0; i<N; i++)
cout<<ar[i]<<' ';
cout<<endl;
pair<int, int> performance = Test(ar, ar+N, HeapSort<int>());
for(int i=0; i<N; i++)
cout<<ar[i]<<' ';
cout<<endl;
cout<<"\nheapsort\ncompare "<<performance.first<<"\nmove "<<performance.second<<endl;
performance = Test(br, br+N, InsertionSort<int>());
for(int i=0; i<N; i++)
cout<<ar[i]<<' ';
cout<<endl;
cout<<"\ninsertionsort\ncompare "<<performance.first<<"\nmove "<<performance.second<<endl;
cin.get();
return 0;
}[/CODE]
在 dev cpp编译通过，vc6不知道怎么样。
程序代码：
我应该没有改变你的意思吧~！