I've not tried the 4.0 compiler, not tested on linux. I doubt the results would be any different based on the OS though. I'll look into their 4.0 version.
Which test did you do? There are three macro to switch on various tests including all integers are the same, descending and ascending too. The default is random ordering so this is probably the test you ran? How do they perform with the other tests? Also, there are several different macros for fine tuning the introsort. They control when insertion sort is used and when to switch to heapsort. Probably, for the random test, heapsort is never invoked at all but based on the machine, the setting for when the partition is small enough to switch to insertion sort might need adjusting. But I'll take a look at their implementation. And I think using a forced inline might help too. Right now it is just inline and not __inline__ so I don't know if 4.0 is actually inlining the functions either. But thanks for the heads up and I will look into their implementation. - Michael Mayur wrote: > Hi Mike, > > I tried your code. Looks good. But you know what, on my system here are the > results that I got: > > -------------------------------------------------------------- > Ternary IntroSort vs. STL sort test app. > Comparing sorts using 5242880 integers. > -------------------------------------------------------------- > > Sorting with STL > Elapsed time to sort: 750.00 seconds > Sort verified. > > Sorting with Ternary IntroSort > Elapsed time to sort: 870.00 seconds > Sort verified. > > ------------------------------- > All tasks completed. > > [EMAIL PROTECTED] ~]$ ./a.out > -------------------------------------------------------------- > Ternary IntroSort vs. STL sort test app. > Comparing sorts using 5242880 integers. > -------------------------------------------------------------- > > Sorting with STL > Elapsed time to sort: 760.00 seconds > Sort verified. > > > Sorting with Ternary IntroSort > Elapsed time to sort: 890.00 seconds > Sort verified. > > ------------------------------- > All tasks completed. > > Your program was compiled using G++-4.0 with an -O3 optimization (includes > inline functions, cross-jumping, function alignment, etc.) on a Linux > machine. The results are as shown above. In all the executions, not one time > did your sort out-perform STL's sort algorithm. Can you explain? > > sincerely, > mayur > > > > On 2/25/06, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: > > > > > > Hi Mike, > > Your code is very interesting! > > > > Have you tried the Anderson method? > > > > "Sorting In Linear Time?" by A. Andersson, T. Hagerup, S. Nilsson, and > > R. Raman (Proceedings of the 27th Annual ACM Symposium on the Theory of > > > > Computing, 1995 > > > > I want to know who is the winner. Andersson claims O(N*loglogN) running > > time. > > > > Weng > > > > > > > > > > ------=_Part_21319_15990259.1140851769513 > Content-Type: text/html; charset=ISO-8859-1 > Content-Transfer-Encoding: quoted-printable > X-Google-AttachSize: 2110 > > Hi Mike,<br> > <br> > I tried your code. Looks good. But you know what, on my system here are the > results that I got:<br> > <br> > --------------------------------------------------------------<br> > Ternary IntroSort vs. STL sort test app.<br> > Comparing sorts using 5242880 integers.<br> > --------------------------------------------------------------<br> > <br> > Sorting with STL<br> > Elapsed time to sort: 750.00 seconds<br> > Sort verified.<br> > <br> > Sorting with Ternary IntroSort<br> > Elapsed time to sort: 870.00 seconds<br> > Sort verified.<br> > <br> > -------------------------------<br> > All tasks completed.<br> > <br> > [EMAIL PROTECTED] ~]$ ./a.out <br> > --------------------------------------------------------------<br> > Ternary IntroSort vs. STL sort test app.<br> > Comparing sorts using 5242880 integers.<br> > --------------------------------------------------------------<br> > <br> > Sorting with STL<br> > Elapsed time to sort: 760.00 seconds<br> > Sort verified.<br> > <br> > <br> > Sorting with Ternary IntroSort<br> > Elapsed time to sort: 890.00 seconds<br> > Sort verified.<br> > <br> > -------------------------------<br> > All tasks completed.<br> > <br> > Your program was compiled using G++-4.0 with an -O3 optimization > (includes inline functions, cross-jumping, function alignment, etc.) on > a Linux machine. The results are as shown above. In all the executions, > not one time did your sort out-perform STL's sort algorithm. Can > you explain?<br> > <br> > sincerely,<br> > mayur<br> > <br> > <br><br><div><span class="gmail_quote">On 2/25/06, <b > class="gmail_sendername"><a href="mailto:[EMAIL PROTECTED]">[EMAIL > PROTECTED]</a></b> <<a href="mailto:[EMAIL PROTECTED]">[EMAIL > PROTECTED]</a>> wrote:</span><blockquote class="gmail_quote" > style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; > padding-left: 1ex;"> > <br>Hi Mike,<br>Your code is very interesting!<br><br>Have you tried the > Anderson method?<br><br>"Sorting In Linear Time?" by A. Andersson, > T. Hagerup, S. Nilsson, and<br>R. Raman (Proceedings of the 27th Annual ACM > Symposium on the Theory of > <br><br></blockquote></div><br> > > ------=_Part_21319_15990259.1140851769513-- --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
