Witam, napisalem sobie heapsorta, ale on dziala strasznie wolno, kilka, kilkanascie razy wolniej od qsorta i std::sorta. Szukam przyczyny juz ze 2 godz, i nic nie moge wymyslic...
Moze wam cos wpadnie w oko, przez to moze byc:
lwisinsk_heapsort.h:
using namespace std;
template<class RandomAccessIterator, class P>
void fix_heap(RandomAccessIterator First, int parent, int heapsize, P Comp)
{
int left_son = 2 * parent + 1,
right_son = 2 * parent + 2,
max;
if((left_son <= heapsize) && (Comp(*(First+parent),*(First+left_son))))
max = left_son;
else
max = parent;
if((right_son <= heapsize) && (Comp(*(First+max),*(First+right_son))))
max = right_son;
if(max != parent) {
typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
value_type tmp=*(First+parent);
*(First+parent) = *(First+max);
*(First+max) = tmp;
fix_heap(First, max, heapsize,Comp);
}
}
template<class RandomAccessIterator, class P>
void make_heap(RandomAccessIterator First,int heapsize, P Comp)
{
for(int i = (heapsize/2) - 1; i >= 0; i--)
fix_heap(First, i, heapsize,Comp);
}
template<class RandomAccessIterator, class P>
void lwisinsk_heapsort(RandomAccessIterator First, RandomAccessIterator Last, P Comp)
{
int heapsize=Last-First-1;
typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
value_type tmp;
make_heap(First, heapsize, Comp);
while(heapsize >= 1) {
tmp=*(First);
*(First) = *(First+heapsize);
*(First+heapsize) = tmp;
fix_heap(First, 0, --heapsize, Comp);
}
}
main.cpp:
#include<iostream>
#include <vector>
#include <algorithm>
#include "lwisinsk_heapsort.h"
#include <stdlib.h>
#include <sys/time.h>
#include <sys/resource.h>
#include<unistd.h>
// Konwersja czasu
inline long long time_rusage(struct rusage tp) // w mikrosekundach
{
long long lo = ((long long)(tp.ru_utime.tv_sec)*1000000 + tp.ru_utime.tv_usec);
return lo;
}
using namespace std;
class porownaj
{
public:
int operator()(const int p, int q) const
{
return p < q;
}
};
class comp
{
public:
int operator()(const string p, string q) const
{
return p < q;
}
};
int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
template<class RandomAccessIterator, class P>
void my_qsort(RandomAccessIterator First, RandomAccessIterator Last, P Comp)
{
typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
qsort(&*(First),Last-First,sizeof(value_type),Comp);
}
void drukuj(int*arr,int size)
{
for(int i=0;i<size;i++)
cout<<arr[i]<<",";
cout<<endl;
}
void drukuj(string*arr,int size)
{
for(int i=0;i<size;i++)
cout<<arr[i]<<",";
cout<<endl;
}
void clear(int *arr, int size)
{
for (int i=size;i>=0;i--)
arr[i]=0;
}
void losuj(int *arr, int size,int modulo)
{
for (int i=0;i<size;i++)
arr[i]=rand()%modulo;
}
void losuj(vector<int>*v, int size,int modulo)
{
for (int i=0;i<size;i++)
v->push_back(rand()%modulo);
}
int main()
{
struct rusage usage1, usage2;
clock_t start, finish;
double duration;
srand(time(0));
int arr[30],rozmiar;
losuj(arr,30,30);
cout<<"Rozlosowana tablica:"<<endl;
drukuj(arr,30);
cout<<"Sortowanie 30 elementowej tablicy losowych liczb:"<<endl;
lwisinsk_heapsort(arr,arr+30,porownaj());
drukuj(arr,30);
cout<<"Porownanie heapsorta, std:sorta i qsorta: dla tablicy losowych liczb:"<<endl;
vector<int> v1,v2;
rozmiar=500000;
for(int i=0; i<10; i++)
{
cout<<"Porównuje dla tablicy "<<rozmiar<<" losowych liczb"<<endl;
v1.erase(v1.begin(), v1.end());
losuj(&v1,rozmiar,2000);
v2=v1;
getrusage(RUSAGE_SELF, &usage1);
lwisinsk_heapsort(v2.begin(),v2.end(),porownaj());
getrusage(RUSAGE_SELF, &usage2);
cout<<"heapsort:"<<(1e-6)*(time_rusage(usage2)- time_rusage(usage1))<<endl;
v2=v1;
getrusage(RUSAGE_SELF, &usage1);
make_heap(v2.begin(),v2.end(),porownaj());
sort_heap(v2.begin(),v2.end(),porownaj());
getrusage(RUSAGE_SELF, &usage2);
cout<<"stl_heap_sort:"<<(1e-6)*(time_rusage(usage2)- time_rusage(usage1))<<endl;
v2=v1;
getrusage(RUSAGE_SELF, &usage1);
sort(v2.begin(),v2.end(),porownaj());
getrusage(RUSAGE_SELF, &usage2);
cout<<"std::sort:"<<(1e-6)*(time_rusage(usage2)- time_rusage(usage1))<<endl;
v2=v1;
getrusage(RUSAGE_SELF, &usage1);
my_qsort(v2.begin(),v2.end(),compare);
getrusage(RUSAGE_SELF, &usage2);
cout<<"qsort:"<<(1e-6)*(time_rusage(usage2)- time_rusage(usage1))<<endl;
rozmiar+=500000;
}
return 0;
}
oto wyniki dzialania:
Rozlosowana tablica:
29,23,2,23,2,7,11,17,11,15,15,2,4,16,10,19,8,18,12,13,29,13,28,9,9,15,28,19,11,3,
Sortowanie 30 elementowej tablicy losowych liczb:
2,2,2,3,4,7,8,9,9,10,11,11,11,12,13,13,15,15,15,16,17,18,19,19,23,23,28,28,29,29,
Porownanie heapsorta, std:sorta i qsorta: dla tablicy losowych liczb:
Porównuje dla tablicy 500000 losowych liczb
heapsort:1.43
stl_heap_sort:0.23
std::sort:0.09
qsort:0.19
Porównuje dla tablicy 1000000 losowych liczb
heapsort:3.14
stl_heap_sort:0.53
std::sort:0.19
qsort:0.39
Porównuje dla tablicy 1500000 losowych liczb
heapsort:4.97
stl_heap_sort:0.78
std::sort:0.29
qsort:0.59
Porównuje dla tablicy 2000000 losowych liczb
heapsort:6.72
stl_heap_sort:1.04
std::sort:0.44
qsort:0.8
Porównuje dla tablicy 2500000 losowych liczb
heapsort:8.69
stl_heap_sort:1.56
std::sort:0.57
qsort:1.03
Porównuje dla tablicy 3000000 losowych liczb
heapsort:11.09
stl_heap_sort:2.06
std::sort:0.66
qsort:1.22
Porównuje dla tablicy 3500000 losowych liczb
heapsort:13.52
stl_heap_sort:2.8
std::sort:0.85
qsort:1.5
Porównuje dla tablicy 4000000 losowych liczb
heapsort:15.61
stl_heap_sort:3.52
std::sort:0.95
qsort:1.69
Porównuje dla tablicy 4500000 losowych liczb
heapsort:18.06
stl_heap_sort:4.2
std::sort:1.14
qsort:1.91
Porównuje dla tablicy 5000000 losowych liczb
heapsort:20.83
stl_heap_sort:5.17
std::sort:1.31
qsort:2.15
Jak widac sortuje dobrze, ale zaje***cie wolno...