|
Is the bottleneck the quicksort itself or the comparison or swap operations ?
If your data is already nearly sorted, quicksort will be slow(er); it will will get to a complexity of N instead ( N log N )
Slightly off-topic without knowing the details, but do you need to do a quicksort at all ? do you have that much information that you need
to sort in "real-time" ? is your data unsorted that you always need to re-sort it ?
|
|
|
|
|
Yes, the bottle-neck is qsort itself, the comparison is done for floating-point data, and swapping is just some part of qsort.
My data aren't sorted at all, almost random..and I do need to sort my data before I can process them.
Thanks,
Mohammad
And ever has it been that love knows not its own depth until the hour of separation
|
|
|
|
|
Have you looked at the code in ...\VC98\CRT\SRC\Qsort.c file for ideas?
"Normal is getting dressed in clothes that you buy for work and driving through traffic in a car that you are still paying for, in order to get to the job you need to pay for the clothes and the car and the house you leave vacant all day so you can afford to live in it." - Ellen Goodman
"To have a respect for ourselves guides our morals; to have deference for others governs our manners." - Laurence Sterne
|
|
|
|
|
Thanks for the reply.
No, I haven't.. but I will do this now..
Thanks
And ever has it been that love knows not its own depth until the hour of separation
|
|
|
|
|
Have you tried the implementation in "Fundamentals of Program Design and Data Structures with C++" by Kenneth A. Lambert and Thomas L. Naps?
(Pages 398-399)
A large number of quicksort implementations appear to swap too much. Lambert and Naps minimize the swapping in their implementation. This could be of value since, to the best of my knowledge, a memory write is more expensive than a memory read. Correct me if I'm wrong though.
|
|
|
|
|
C runtime qsort is slow?
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
[my articles]
|
|
|
|
|
Isn't it that one in the STL? yes it is slower than an ordinary qsort algorithm, this might be due to the excessive function calls that call the "compare" function. we use simple ">" and "<" operators instead of function calls
And ever has it been that love knows not its own depth until the hour of separation
|
|
|
|
|
Try using std::sort[^]. Here's an example:
#include "stdafx.h"
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
int main(int argc, char* argv[])
{
vector<int> numbers;
srand(static_cast<unsigned>(time(NULL)));
generate_n(back_inserter(numbers), 10, &rand);
cout << "Not sorted:" << endl;
copy(numbers.begin(), numbers.end(), ostream_iterator<int>(cout, "\n"));
cout << endl;
sort(numbers.begin(), numbers.end());
cout << "Sorted:" << endl;
copy(numbers.begin(), numbers.end(), ostream_iterator<int>(cout, "\n"));
cout << endl;
return 0;
}
Steve
|
|
|
|
|
I second that suggestion of using std::sort (for the second time, last time you and I together having done an argument on this topic with another CPian, if I remember). There should be no reason why one should use qsort when std::sort can be used.
Nobody can give you wiser advice than yourself. - Cicero
.·´¯`·->Rajesh<-·´¯`·.
Codeproject.com: Visual C++ MVP
|
|
|
|
|
Profile your code and find out where the bottle neck is. STL's sort should work fine.
Steve
|
|
|
|
|
Hi,
The problem I have in using STL's sorting algorithms is as follows:
1. I am not sorting integers but struct objects, but sorting depends only on a float member of the struct.
struct aaa {<br />
int a1;<br />
int a2;<br />
float a3;
};
2. Becoz of this, I have to supply a pointer to a "compare" function that compares two objects.
3. I believe that most of the time is spent during calls to the compare function, I wish I could get rid of the function-call ovrhead.
Any solution?
Thanks
And ever has it been that love knows not its own depth until the hour of separation
|
|
|
|
|
Can you show the "compare" function? You could try making it inline .
Steve
|
|
|
|
|
Yes, I already did. and I also heared that making it static helps the complier optijmize things a little bit better:
<br />
static inline int compare_edges (const void * EDGE1, const void * EDGE2)<br />
{<br />
if(((const struct EDGE*)EDGE1)->reliab > ((const struct EDGE*)(EDGE2))->reliab)<br />
return 1;<br />
else if(((const struct EDGE*)EDGE1)->reliab < ((const struct EDGE*)EDGE2)->reliab)<br />
return -1;<br />
return 0;<br />
<br />
}
And ever has it been that love knows not its own depth until the hour of separation
|
|
|
|
|
Try using a functor[^] instead. Also your "compare" function looks like it's for qsort , not std:sort .
Steve
|
|
|
|
|
Yes, I am still using qsort. I'll see what I can do with a functor.
Thanks alot
And ever has it been that love knows not its own depth until the hour of separation
|
|
|
|
|
A functor will be of no help using qsort . Use std::sort and an inline compare function. If that doesn't help you can try using a functor (again, with std::sort ).
Steve
|
|
|
|
|
Use std::sort (not qsort , it's crap) with the following definitions:
struct aaa
{
int a1;
int a2;
float a3;
};
inline bool operator<(const aaa &lhs, const aaa &rhs)
{
return lhs.a3 < rhs.a3;
}
Steve
|
|
|
|
|
Yes, thank you.. I am coding this..
I really appreciate your help
I will post results here
Thanks again
Mohammad
And ever has it been that love knows not its own depth until the hour of separation
|
|
|
|
|
I did it and yes, it worked!
this fastened sorting from about 185msec (using our qsort implementation) to 172msec using std::sort, so it wasn't a major enhancement, but I hope I can enhance things further
Thanks for all who helped me and especially <b>Stephen Hewitt </b>
Thank you all,
Mohammad
And ever has it been that love knows not its own depth until the hour of separation
|
|
|
|
|
What does the following yield:
void qsort( int a[], int lo, int hi )
{
int low = lo;
int high = hi;
int mid = a[(low + high) / 2];
do
{
while (a[low] < mid) low++;
while (a[high] > mid) high--;
if (low <= high)
{
swap(a[low], a[high]);
low++
high--
}
} while (low <= high);
if (high > lo) qsort(a, lo, high);
if (low < hi) qsort(a, low, hi);
}
"Normal is getting dressed in clothes that you buy for work and driving through traffic in a car that you are still paying for, in order to get to the job you need to pay for the clothes and the car and the house you leave vacant all day so you can afford to live in it." - Ellen Goodman
"To have a respect for ourselves guides our morals; to have deference for others governs our manners." - Laurence Sterne
|
|
|
|
|
Yes, this appears to be even a little bit faster , just a 2msec enhancement, about 2.5% enahncement..
Thanks
And ever has it been that love knows not its own depth until the hour of separation
|
|
|
|
|
Could someone explain to me how to solve this ?
I am editing CListView using modal dialog – pretty much “standard” operation. In this “main” dialog I open another dialog. In this “sub dialog” I want to change text and bacground colors of CEdit controls.
These COOLOREFs variables are initialized in the CListView.
Obviously I need the CList View data in my dialog – so I use parameterized constructor and pass my CListView “this” pointer to it.
Here is the code snippet:
m_clrText = RGB( 0, 0, 0 );
m_clrBkgnd = RGB( 255, 255, 0 );
C_Dialog_Edit_Color_Weight dlg(this);
int nRet = -1;
nRet = dlg.DoModal();
....
So far so good.
The “problem” is that I do not fully undestand the syntax of the C_Dialog_Edit_Color_Weight parametrized constructor.
Therefore I do not know how include C_Edit_ parameters to pass the correct pareameters to the C_Edit_.
C_Dialog_Edit_Color_Weight::C_Dialog_Edit_Color_Weight(C_Dialog_Block *pDialog , CWnd* pParent /*=NULL*/)
: CDialog(C_Dialog_Edit_Color_Weight::IDD, pParent)
{…
With this constructor I can only get to the C_Edit_ default constructor.
So, how do I include parametrized C_Edit_ in this C_Dialog_Edit_Color_Weight constructor ?
Thanks for reading.
Cheers
Vaclav
|
|
|
|
|
Vaclav_Sal wrote: C_Dialog_Edit_Color_Weight
Is this a class that you defined or is it a third party library class?
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
[my articles]
|
|
|
|
|
It is MFC CDialog derived class
|
|
|
|
|
I know (there's a call to base class contructor in your code) but, I ask again, is it your own defined class or is it a third party library class? I mean, can you change its code or not?
Moreover, could you please detail more what you need?
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
[my articles]
|
|
|
|