Prev: Problem with MFC on Vista
Next: communication between C# dll and C++ dll ???
From: Tom Serface on 6 May 2008 01:36
Yeah, obviously you can replace the sort routine with anything that works
for your data. This is a simple way to get started and a really easy one to
implement even with weird lists of objects. You're right. If you had 200K
records it could take a few seconds, but for 100K it is not too bad on
today's machine and if everything is in memory.

Tom

"Joseph M. Newcomer" <newcomer(a)flounder.com> wrote in message
news:pjjv14528scnr2kn6i8v0fmm5dpdtbej5i(a)4ax.com...
> Looks like n**2 bubble sort. Works OK for small n, but for large n, it is
> a killer. I
> tend to just use qsort because it is n*log(n)
>
> I once had an app which required sorting a doubly-linked list. The
> problem was that old
> data files were unsorted. So what I did was for any version of the file <
> k (the version
> k was the one that now required the list be maintained in ascending order,
> for realtime
> performance), I would run across the list once; if it was in order, I left
> it alone.
>
> If it was not in order, I allocated a vector of count-of-list-elements
> pointers, put a
> pointer to every list element in it, qsorted the array, then ran through
> the array,
> linking up the elements in sorted order. This whole operation took under
> 5 seconds on an
> 80286 (read: small memory). The problem was that for very large arrays,
> we discovered in
> beta testing, when I did the malloc(n * sizeof(void *)), I got back NULL
> because there
> wasn't enough space to allocate the side vector. In that case, I popped
> up a status
> display saying "Updating older format file to new format, please be
> patient, this may take
> several minutes" and proceeded to do a bubble sort, which could take up to
> three minutes.
> Of course, once we wrote the file back out in the new format, we knew it
> was in order and
> didn't have to go through this again.
>
> But it really pointed out how n**2 and n*log2(n) differ in performance.
> joe

From: Giovanni Dicanio on 6 May 2008 05:25

"Tom Serface" <tom.nospam(a)camaswood.com> ha scritto nel messaggio
news:EE4BFD17-0635-434D-BDE3-6AF0603E1E05(a)microsoft.com...

> bool CDialogWithList::CompareAndSwapString1(int pos, bool bAscending)
> {
> CMyObjectInfo *temp;
> int posFirst = pos;
> int posNext = pos + 1;
>
> if(!bAscending) {
> if (((CMyObjectInfo *)GetAt(posFirst))->m_csString1 <
> ((CMyObjectInfo *)GetAt(posNext))->m_csString1) {
> temp = (CMyObjectInfo *)GetAt(posFirst);
> SetAt(posFirst, GetAt(posNext));
> SetAt(posNext, temp);
> return TRUE;
[...]

Thanks for sharing your code, Tom.

Just a little note: I think there is a simple typo here:

I believe that Tom meant returning 'BOOL' type in his code (instead of
'bool'), in fact he returns 'TRUE' and 'FALSE' values.
(If the return type is 'bool', I think we should return 'true' and 'false'.)

G


From: Giovanni Dicanio on 6 May 2008 05:32

"Tom Serface" <tom.nospam(a)camaswood.com> ha scritto nel messaggio
news:AFD785C0-EB1B-467F-9F08-268A820C4C8F(a)microsoft.com...

> Yeah, obviously you can replace the sort routine with anything that works
> for your data.

If we store data in STL containers like std::vector, we can use the
std::sort algorithm (ready "off the shelf", is that the right expression? :)

std::sort algorithm has O(N * log(N)) sort complexity.

std::sort
http://msdn.microsoft.com/en-us/library/ecdecxh1(VS.80).aspx

However, as you wrote, I think that on modern hardware the difference is on
big amounts of data (several hundreds thousands).

G


From: Tom Serface on 6 May 2008 10:03
You're right. I always get those mixed up. I was just putting in an
example. Or course, in this case it will convert it for me so it would
still work OK.

Tom

"Giovanni Dicanio" <giovanni.dicanio(a)invalid.com> wrote in message
news:uynLJt1rIHA.524(a)TK2MSFTNGP05.phx.gbl...
>
> "Tom Serface" <tom.nospam(a)camaswood.com> ha scritto nel messaggio
> news:EE4BFD17-0635-434D-BDE3-6AF0603E1E05(a)microsoft.com...
>
>> bool CDialogWithList::CompareAndSwapString1(int pos, bool bAscending)
>> {
>> CMyObjectInfo *temp;
>> int posFirst = pos;
>> int posNext = pos + 1;
>>
>> if(!bAscending) {
>> if (((CMyObjectInfo *)GetAt(posFirst))->m_csString1 <
>> ((CMyObjectInfo *)GetAt(posNext))->m_csString1) {
>> temp = (CMyObjectInfo *)GetAt(posFirst);
>> SetAt(posFirst, GetAt(posNext));
>> SetAt(posNext, temp);
>> return TRUE;
> [...]
>
> Thanks for sharing your code, Tom.
>
> Just a little note: I think there is a simple typo here:
>
> I believe that Tom meant returning 'BOOL' type in his code (instead of
> 'bool'), in fact he returns 'TRUE' and 'FALSE' values.
> (If the return type is 'bool', I think we should return 'true' and
> 'false'.)
>
> G
>
>

From: Tom Serface on 6 May 2008 10:06
Yeah, that would work. Fortunately we're just shuffling pointers so it's
pretty quick regardless.

"off the shelf" "out of the box" means the same thing... of course you'd
have to write some code still since you'll want to be able to sort by any
column or even multiple columns perhaps.

Tom

"Giovanni Dicanio" <giovanni.dicanio(a)invalid.com> wrote in message
news:Oo0otw1rIHA.2520(a)TK2MSFTNGP02.phx.gbl...
>
> "Tom Serface" <tom.nospam(a)camaswood.com> ha scritto nel messaggio
> news:AFD785C0-EB1B-467F-9F08-268A820C4C8F(a)microsoft.com...
>
>> Yeah, obviously you can replace the sort routine with anything that works
>> for your data.
>
> If we store data in STL containers like std::vector, we can use the
> std::sort algorithm (ready "off the shelf", is that the right expression?
> :)
>
> std::sort algorithm has O(N * log(N)) sort complexity.
>
> std::sort
> http://msdn.microsoft.com/en-us/library/ecdecxh1(VS.80).aspx
>
> However, as you wrote, I think that on modern hardware the difference is
> on big amounts of data (several hundreds thousands).
>
> G
>
>

First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: Problem with MFC on Vista
Next: communication between C# dll and C++ dll ???