C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Re: How does this algorithm work?          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Francis Glassborow Guest Posted: Fri Aug 15, 2003 9:14 pm    Post subject: Re: How does this algorithm work? In article <pan.2003.08.15.06.17.49.558298 (AT) gmx (DOT) net>, Dhruv <dhruvbird (AT) gmx (DOT) net> writes Quote: template <class _Tp, class _Alloc void list<_Tp, _Alloc>::sort() { // Do nothing if the list has length 0 or 1. if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) { list<_Tp, _Alloc> __carry; list<_Tp, _Alloc> __counter[64]; int __fill = 0; while (!empty()) { __carry.splice(__carry.begin(), *this, begin()); int __i = 0; while(__i < __fill && !__counter[__i].empty()) { __counter[__i].merge(__carry); __carry.swap(__counter[__i++]); } __carry.swap(__counter[__i]); if (__i == __fill) ++__fill; } for (int __i = 1; __i < __fill; ++__i) __counter[__i].merge(__counter[__i-1]); swap(__counter[__fill-1]); } } Is there any sorting algorithm like quick_sort, or merge sort, etc... that this algorthim follows, or is it some sort of hybrid? When studying this kind of implementation code: 1) Be careful over intellectual property rights, particularly when quoting such code. (I think you are in the clear this time). 2) Strip out the implementor's decoration of variable names (i.e. the leading double underscores) 3) Draw a flow chart to visualise the algorithm. -- Francis Glassborow ACCU 64 Southfield Rd Oxford OX4 1PA +44(0)1865 246490 All opinions are mine and do not represent those of any organisation [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ivan Vecerina Guest Posted: Fri Aug 15, 2003 9:18 pm    Post subject: Re: How does this algorithm work? "Dhruv" <dhruvbird (AT) gmx (DOT) net> wrote Quote: This is the sorting algorithm form libstdc++'s list class. I want to know how exactly it works. What does it do to get the list sorted. The only thing I could understand is that at the end, it merges all the sorted sub-lists into 1 list, and swaps it with the list pointed to by this. ..... Is there any sorting algorithm like quick_sort, or merge sort, etc... that this algorthim follows, or is it some sort of hybrid? To me, it looks like an derecursified MergeSort algorithm. The merge() call does the merging of two sorted subsequences. The __counter buffer is used to avoid recursion, storing intermediate lists of exponentially growing sizes. New elements that are spliced out of the original list (using the splice() call, stored into carry) are merged up the __counter buffer (don't know why it's named that way). __fill stores the maximum index that has been used so far (will be the base-2 log of list size), for the final merge loop. Regards, -- Ivan Vecerina <> http://www.post1.com/~ivec Brainbench MVP for C++ <> http://www.brainbench.com [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Robert Smith Guest Posted: Fri Aug 15, 2003 9:25 pm    Post subject: Re: How does this algorithm work? "Dhruv" <dhruvbird (AT) gmx (DOT) net> wrote Quote: template <class Tp, class Alloc void list { // Do nothing if the list has length 0 or 1. if (Mnode->Mnext != Mnode && Mnode->Mnext->Mnext != Mnode) { list<Tp, Alloc> carry; list<Tp, Alloc> counter[64]; int fill = 0; while (!empty()) { carry.splice(carry.begin(), *this, begin()); int i = 0; while(i < fill && !counter[i].empty()) { counter[i].merge(carry); carry.swap(counter[i++]); } carry.swap(counter[i]); if (i == fill) ++fill; } for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1]); swap(counter[fill-1]); } } Is there any sorting algorithm like quick_sort, or merge sort, etc... that this algorthim follows, or is it some sort of hybrid? I took the liberty of deleting all the underscores to make it more readable and analyzed it by 'running' the routine on paper. I don't know what this algorithm is called, if it has a name, but here are some hints to help you figure it out: The first time through the outer while loop [while(!empty())] we grab the first item off of our list and put it into the list counter[0]. At the end of every iteration through the outer while loop the list counter[n] will have 2^n sorted items or be empty. fill will have the number of counter lists that have been used (so we know how many to merge at the end). carry will be empty. The inner while loop [ while(i < fill && !counter[i].empty()) ] runs through the list of counter lists merging (sorting and emptying) all of them along with the latest item taken off of the original list, until it comes to the first empty counter and deposits the sorted list there. I think the inner loop would work without the (i < fill) test but it does save some calls to count[i].empty(). The carry list is a place holder for all of this work. At first sight I wondered about the fixed size array (counter[64]) but it won't overflow until you have more than 2^64 items in your list which shouldn't happen until we have >64 bit computers. IOW, as an algorithm, it is safe only if we assume a finite machine, which is true of all known implementations. The reader is encouraged to submit contrary examples. An analysis of this algorithm's performance is left as an exercise for the reader (i.e. I should get back to work.) Robert [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top John Potter Guest Posted: Sat Aug 16, 2003 3:57 pm    Post subject: Re: How does this algorithm work? On 15 Aug 2003 05:41:59 -0400, "Dhruv" <dhruvbird (AT) gmx (DOT) net> wrote: The short answer is "fine". :) Quote: This is the sorting algorithm form libstdc++'s list class. I want to know how exactly it works. What does it do to get the list sorted. The only thing I could understand is that at the end, it merges all the sorted sub-lists into 1 list, and swaps it with the list pointed to by this. [snip code] Quote: Is there any sorting algorithm like quick_sort, or merge sort, etc... that this algorthim follows, or is it some sort of hybrid? It is an iterative (not recursive) merge sort. Counter[i] will be a list of size 0 or 2^i. For seven items, the lists would be. 0 a - c - e - g 1 - ab ab - - ef ef 2 - - - abcd abcd abcd abcd The final pass puts them all together when the size is not a power of two. The depth first operation requires only one list of each size rather than n/2 lists of size 2, n/4 lists of size 4, ... which would be required if it moved up the tree breadth first. The array of lists replaces the recursive stack. John [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top John Potter Guest Posted: Sun Aug 17, 2003 1:45 am    Post subject: Re: How does this algorithm work? On 16 Aug 2003 04:14:06 -0400, "Dhruv" <dhruvbird (AT) gmx (DOT) net> wrote: Quote: This thing outperformed even quick sort for random data, so I was a bit surprised. What quicksort? If it is sort in the library, my measurements showed that it was faster to copy the list to a vector, sort the vector, and copy it back to the list than to use the list sort. This is for small easily copied data such as int or pointers. Quote: Ok, so let me see if I've got it right now. I'll just write down what I have understood: 1. fill is the log of the number of elements in the list. So, if the list contains 1024 elements, then fill == 10. At the end, it will be 11. Note the swap with fill-1. Quote: 2. So, if there are 1024 elemets, then temp[9] will contain 512 elements. temp[8] == 256 elements. temp[7] == 128 elemets. temp[6] == 64 elements. temp[5] == 32 elemets. temp[4] == 16 elements. temp[3] == 8 elemets. temp[2] == 4 elements. temp[1] == 2 elemets. temp[0] == 1 element. 3. Then, all of these are merged together, so merging is an O(N) operation, and it is performed lg (N) times, so the complexity in any case is O(Nlg(N)). Then, for adding elements, I guess then operations are 2Nlg(N), so again complexity is O(Nlg(N)), so overall complexity is O(Nlg(N)). Yes, whether your analysis is correct or not. This is always true for merge sort. A hint in the beginning would have been that list::sort is required to be stable and merge sort is the standard smart sort which is stable. Both sort (quicksort) and partial_sort (heapsort) are unstable. Quote: What would you call this algorithm? I think it is a bottom-up merge sort? Just an iterative version of merge_sort. The recursive version uses lists whose size is the same plus or minus one. This version use lists whose size is the same or very different for those items to the right of the highest power of two. Quote: Except that instead of merging equal sizes, it merges exponential sized lists, and I guess that's where it's speed lies. In that it has to do the most work only in the last merge, where half the data is merged, with the other half, which was there in the remaining array elemnts less than the current one. The surprising thing is that I haven't read of this approach (merging data sets that are double of each other instead of the same sizes) anywhere till now. Look again at your lists above. You only have 1023 elements. When the next item is added, it is merged with list0 giving 2 items. That is merged with list1 containing 2 items giving 4 items. That is merged with list2 containing 4 items. Etc. The lists are the same size until you get to the last part of a total not being a power of two. In this case, note that 10 zero sized lists are merged together and then into the list10 in the final pass. Consider 10 items merged recursively spliting in half. 0 with 1 nothing with 2 3 with 4 2 with 3-4 0-1 with 2-4 5 with 6 nothing with 7 8 with 9 7 with 8-9 5-6 with 7-9 0-4 with 5-9 Merging iteratively using powers of two. 0 with 1 2 with 3 0-1 with 2-3 4 with 5 6 with 7 4-5 with 6-7 0-3 with 4-7 8 with 9 nothing with 8-9 nothing with 8-9 1-7 with 8-9 The recursive version is not usable on list because of all of the pointer chases to find the middles. I have also found that the iterative version is slightly faster than the recursive version for vector. John [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ulrich Eckhardt Guest Posted: Sun Aug 17, 2003 11:47 am    Post subject: Re: How does this algorithm work? John Potter wrote: Quote: A hint in the beginning would have been that list::sort is required to be stable and merge sort is the standard smart sort which is stable. Both sort (quicksort) and partial_sort (heapsort) are unstable. Ulrich Eckhardt wrote: Quote: // collect the elements from the __counters // hmmm, one could as well directly merge them into *this, no ? for (int __i = 1; __i < __fill; ++__i) __counter[__i].merge(__counter[__i-1]); swap(__counter[__fill-1]); I just wonder about this (almost obvious) way to improve performance a tiny bit. Does that defeat the requirement 'stable' ? Uli -- Questions ? see C++-FAQ Lite: http://parashift.com/c++-faq-lite/ first ! [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Francis Glassborow Guest Posted: Mon Aug 18, 2003 4:47 pm    Post subject: Re: How does this algorithm work? In article <e2975357.0308171308.243c490a (AT) posting (DOT) google.com>, Siemel Naran <SiemelNaran (AT) att (DOT) net> writes Quote: Francis Glassborow <francis (AT) robinton (DOT) demon.co.uk> wrote in message When studying this kind of implementation code: 1) Be careful over intellectual property rights, particularly when quoting such code. (I think you are in the clear this time). Quotations are OK. Here is a relevant quotation from the United States copyright code. I'm sure England has a similar code. Please go and read the licence specifications at the URL I provided. My problem is not with the quoting of the code but that anyone should use it. Much worse is that having seen the code leaves you (or more likely your employer) exposed should you use that function in your code. The main saving grace is that most of the code is so poor that even an average programmer should be able to do better. In simple terms, I do not want to accidentally read code that I am forbidden to use. If the owners of the IPR can demonstrate that I have seen the code I have very little defence left. It is the considered opinion of those I have consulted that licence restrictions on the code in that book makes it one that professionals should not buy. -- Francis Glassborow ACCU 64 Southfield Rd Oxford OX4 1PA +44(0)1865 246490 All opinions are mine and do not represent those of any organisation [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ulrich Eckhardt Guest Posted: Tue Aug 19, 2003 10:41 am    Post subject: Re: How does this algorithm work? Francis Glassborow wrote: Quote: Siemel Naran <SiemelNaran (AT) att (DOT) net> wrote: Francis Glassborow <francis (AT) robinton (DOT) demon.co.uk> wrote: When studying this kind of implementation code: 1) Be careful over intellectual property rights, particularly when quoting such code. (I think you are in the clear this time). Quotations are OK. Here is a relevant quotation from the United States copyright code. I'm sure England has a similar code. Please go and read the licence specifications at the URL I provided. Maybe that's just me, but I can't find any link you posted in this thread. However: Quote: The main saving grace is that most of the code is so poor that even an average programmer should be able to do better. What is so bad about this code, apart from the fact that it (imho) lacks comments about how it works ? Ulrich Eckhardt -- Questions ? see C++-FAQ Lite: http://parashift.com/c++-faq-lite/ first ! [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Bertrand Motuelle Guest Posted: Tue Aug 19, 2003 12:37 pm    Post subject: Re: How does this algorithm work? Francis Glassborow <francis (AT) robinton (DOT) demon.co.uk> wrote Quote: In article <e2975357.0308171308.243c490a (AT) posting (DOT) google.com>, Siemel Naran <SiemelNaran (AT) att (DOT) net> writes Francis Glassborow <francis (AT) robinton (DOT) demon.co.uk> wrote in message When studying this kind of implementation code: 1) Be careful over intellectual property rights, particularly when quoting such code. (I think you are in the clear this time). Quotations are OK. Here is a relevant quotation from the United States copyright code. I'm sure England has a similar code. Please go and read the licence specifications at the URL I provided. My problem is not with the quoting of the code but that anyone should use it. Much worse is that having seen the code leaves you (or more likely your employer) exposed should you use that function in your code. The main saving grace is that most of the code is so poor that even an average programmer should be able to do better. I think this last sentence shows that you're not talking about libstdc++ but about "Numerical Recipes" which is discussed in another thread :-) Bertrand [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Francis Glassborow Guest Posted: Tue Aug 19, 2003 6:14 pm    Post subject: Re: How does this algorithm work? In article <bhsgeg$2lvho$1 (AT) ID-178288 (DOT) news.uni-berlin.de>, Ulrich Eckhardt <doomster (AT) knuut (DOT) de> writes Quote: Please go and read the licence specifications at the URL I provided. Maybe that's just me, but I can't find any link you posted in this thread. Sorry, you are right... for some reason this book was quoted twice within hours but in different newsgroups: http://www.numerical-recipes.com/com/screen-license.html Explore the rest of the site and note that the cheapest licence is $65 and if you have more than one screen a multi-screen single CPU licence is $1400. Regular Linux users have to pay $120 for a single screen licence. And Apple Mac users $130. Quote: However: The main saving grace is that most of the code is so poor that even an average programmer should be able to do better. What is so bad about this code, apart from the fact that it (imho) lacks comments about how it works ? The specifically quoted code or the source in general? Well the headers for the C++ version has a filescope using namespace std; (However they have kindly encapsulated their own material in namespace NR. Fundamentally even the C++ code seems to be reworked C code that come from machine translated Fortran. The reader has about zero chance of actually using code by typing it in because there is so much coupling between different parts. That just about means that they need to buy a licence, which costs as much or more than the book and permanently records the fact that they have the code/book which just about invalidates any defence of separate development should you write numerical code for a successful application (making it worth their lawyers going after you.). The C code is poor, the C++ code must rate as some of the worst I have ever struggled to read. As an example they have a function whose sole return is in an if-statement nested in an if-statement nested in a for(;-statement (not even the courtesy of writing while(true). Within that same outer for we find a nested if-statement with a nested for(; with a break. The descriptions of the algorithms are fine for those working in the problem domain but the source code is almost 30-years behind the current day. -- Francis Glassborow ACCU 64 Southfield Rd Oxford OX4 1PA +44(0)1865 246490 All opinions are mine and do not represent those of any organisation [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Tom Hyer Guest Posted: Thu Aug 21, 2003 4:56 pm    Post subject: Re: How does this algorithm work? Francis Glassborow <francis (AT) robinton (DOT) demon.co.uk> wrote Quote: (Discussion of "Numerical Recipes": Egregious license and descriptions of ugly code deleted) The descriptions of the algorithms are fine for those working in the problem domain but the source code is almost 30-years behind the current day. But what else is there? A couple of my previous employers were heavy users of NR, because there aren't a whole lot of alternatives when you want (say) a Runge-Kutta solver, or a singular value decomposition. You can look up the ACM algorithms (in FORTRAN, of course) or the LSODE code (in FORTRAN) or a public-domain LINPACK knockoff (one guess), or you can open NR. Tom Hyer "Just because people are dead doesn't mean they were stupid." -- Jim Reardon [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ron Guest Posted: Fri Aug 22, 2003 10:04 am    Post subject: Re: How does this algorithm work? [OT] { Warning topic drift. Back to C++ or move to an appropriate group. -mod/jep } Quote: In simple terms, I do not want to accidentally read code that I am forbidden to use. If the owners of the IPR can demonstrate that I have seen the code I have very little defence left. I agree, quite strongly, and feel that the overzealous avarice of certain copyright holders represents both a danger to individual programmers, and a general danger to the industry as a whole. I rather doubt that the assertion of such rights comports with the Constitutional basis for copyrights, which, from Art.I s.8, is: To promote the Progress of Science and useful Arts, by securing for limited Times to Authors and Inventors the exclusive Right to their respective Writings and Discoveries... ([url]http://caselaw.lp.findlaw.com/data/constitution/article01/)[/url]. Note the antecedent: copyrights exist to "promote the progress of science and useful arts". That is, the Constitution gives authors the right to exclusive ownership of their works as a *means* to promote the advancement of science, literature, etc. Exclusive ownership is *not* an end in itself. Charging exorbitant fees for the use of copyrighted material promotes the author's pocketbook at the expense of the advancement of science, etc., and thus is, I believe, an invalid use of copyrights. -- Ron [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Page 1 of 1   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.