Dave Nadler <drn@nadler.com> writes:> Why would I do that, when heapsort requires NO additional memory??It's more implementation effort (if you write it yourself) to code a completely different algorithm than tweak something already in the library, it may burn more code space in the device if something else in the system uses qsort, and heapsort is generally slower. Do you want to control the hardware, or do you want it to control you?
validity of ... reasons for preferring C over C++
Started by ●October 16, 2014
Reply by ●October 27, 20142014-10-27
Reply by ●October 27, 20142014-10-27
Dave Nadler <drn@nadler.com> wrote:> On Monday, October 27, 2014 12:00:47 PM UTC-4, Paul Rubin wrote: >> Dave Nadler <drn@nadler.com> writes: >> > Um, in this case N was ~900. Stack space is especially constrained >> > in segmented architectures; in this case the data to be sorted >> > was "far".>> Well if you use an explicit stack rather than recursion, you could put >> it in far memory as well.> Why would I do that, when heapsort requires NO additional memory??There are no sorting algorithm that require no additional memory. Maybe O(1) memory with a small coefficient. (On register machines, count the registers, too.) In some cases, code space and data space are separate, and you might save data space at the expense of code space. If you do the recursion in the right order, and use an explicit (array in memory) stack, instead of recursive calls, quicksort uses O(log N) for the stack. For embedded sized N's, that should be pretty small. Next, compare code space to other algorithms, and see which one is less overall. (As above, except when code and data are separate, where the tradeoff might be different.) -- glen
Reply by ●October 28, 20142014-10-28
On Thu, 23 Oct 2014 12:25:38 -0700, Dave Nadler wrote:> Even at O(log N), qsort chews up a lot of stack space for non-trivial N. > heapsort is more appropriate in a resource-constrained environment...Particularly if the constrained resource is time. Quicksort is O(n^2) in the worst case, while heapsort is still O(n.log(n)). This has resulted in a number of C and C++ standard libraries using introsort, which initially uses quicksort but switches to heapsort if the size of the largest partition doesn't decay quickly enough.
Reply by ●October 28, 20142014-10-28
On 24/10/14 00:17, Paul Rubin wrote:> Dave Nadler <drn@nadler.com> writes: >> Even at O(log N), qsort chews up a lot of stack space for non-trivial N. >> heapsort is more appropriate in a resource-constrained environment... > > In an environment so resource-constrained that log N is consequential, > you aren't going to fit a non-trivial N anyway. So you may as well use > quicksort. ;-). >In a resource-constrained system you are often very interested in the runtime performance. In particular, the worst-case performance is usually the most important - you have to be sure the operation finishes within a given time. Quicksort is useless in such cases - it has an average of time of O(n.log(n)), but a worst-case runtime of O(n�). This means your system can easily work fine in all your tests, but fail with an unlucky choice of data, unless you design it with far more processor resources than you generally need. Heapsort is much more stable and predictable at O(n.log(n)). Even though it takes longer on average than quicksort, its stability makes it a good choice for embedded, resource-constrained and real-time systems.
Reply by ●October 28, 20142014-10-28
David Brown <david.brown@hesbynett.no> writes:> Heapsort is much more stable and predictable at O(n.log(n)). Even > though it takes longer on average than quicksort, its stability makes it > a good choice for embedded, resource-constrained and real-time systems.The C library sorting routine is called qsort because it historically used an algorithm called "quicker sort", but these days the algorithm is no longer specified and I don't know what any particular implementation uses. Maybe heapsort for all I know. The C++ std::sort routine before C++11 was specified to use O(n log n) comparisonson average, but since C++11 it's specified to have O(n log n) comparisons without "average", i.e. presumably worst case, per http://en.cppreference.com/w/cpp/algorithm/sort . I just noticed this and it might be interesting to look at some of the committee minutes regarding this change.
Reply by ●October 28, 20142014-10-28
On Tue, 28 Oct 2014 08:45:08 +0100, David Brown <david.brown@hesbynett.no> wrote:>On 24/10/14 00:17, Paul Rubin wrote: >> Dave Nadler <drn@nadler.com> writes: >>> Even at O(log N), qsort chews up a lot of stack space for non-trivial N. >>> heapsort is more appropriate in a resource-constrained environment... >> >> In an environment so resource-constrained that log N is consequential, >> you aren't going to fit a non-trivial N anyway. So you may as well use >> quicksort. ;-). >> > >In a resource-constrained system you are often very interested in the >runtime performance.Really ? If you have only a few hundred or thousand bytes of RAM/core even primitive sorting methods, like bubble sort or insertion sort are quite adequate even with a processor with 1 us cycle time. Except for extremely low power applications, I would not bother with more advanced sort algorithm.
Reply by ●October 28, 20142014-10-28
On 28/10/14 18:59, upsidedown@downunder.com wrote:> On Tue, 28 Oct 2014 08:45:08 +0100, David Brown > <david.brown@hesbynett.no> wrote: > >> On 24/10/14 00:17, Paul Rubin wrote: >>> Dave Nadler <drn@nadler.com> writes: >>>> Even at O(log N), qsort chews up a lot of stack space for non-trivial N. >>>> heapsort is more appropriate in a resource-constrained environment... >>> >>> In an environment so resource-constrained that log N is consequential, >>> you aren't going to fit a non-trivial N anyway. So you may as well use >>> quicksort. ;-). >>> >> >> In a resource-constrained system you are often very interested in the >> runtime performance. > > Really ? > > If you have only a few hundred or thousand bytes of RAM/core even > primitive sorting methods, like bubble sort or insertion sort are > quite adequate even with a processor with 1 us cycle time. Except for > extremely low power applications, I would not bother with more > advanced sort algorithm. >You snipped the most important part "In particular, the worst-case performance is usually the most important - you have to be sure the operation finishes within a given time." Sometimes a simple sort /is/ the best choice. I said runtime performance is important - but that is very different from saying you want as fast performance as possible. Real-time systems are about doing the job within the required time, not about doing it quickly.
Reply by ●October 29, 20142014-10-29
On Tue, 28 Oct 2014 23:46:41 +0100, David Brown <david.brown@hesbynett.no> wrote:>On 28/10/14 18:59, upsidedown@downunder.com wrote: >> On Tue, 28 Oct 2014 08:45:08 +0100, David Brown >> <david.brown@hesbynett.no> wrote: >> >>> On 24/10/14 00:17, Paul Rubin wrote: >>>> Dave Nadler <drn@nadler.com> writes: >>>>> Even at O(log N), qsort chews up a lot of stack space for non-trivial N. >>>>> heapsort is more appropriate in a resource-constrained environment... >>>> >>>> In an environment so resource-constrained that log N is consequential, >>>> you aren't going to fit a non-trivial N anyway. So you may as well use >>>> quicksort. ;-). >>>> >>> >>> In a resource-constrained system you are often very interested in the >>> runtime performance. >> >> Really ? >> >> If you have only a few hundred or thousand bytes of RAM/core even >> primitive sorting methods, like bubble sort or insertion sort are >> quite adequate even with a processor with 1 us cycle time. Except for >> extremely low power applications, I would not bother with more >> advanced sort algorithm. >> > >You snipped the most important part "In particular, the worst-case >performance is usually the most important - you have to be sure the >operation finishes within a given time." > >Sometimes a simple sort /is/ the best choice. I said runtime >performance is important - but that is very different from saying you >want as fast performance as possible. Real-time systems are about doing >the job within the required time, not about doing it quickly.My point was that with small data sets, even the worst case performance is very sufficient.
Reply by ●October 29, 20142014-10-29
On 29/10/14 06:27, upsidedown@downunder.com wrote:> On Tue, 28 Oct 2014 23:46:41 +0100, David Brown > <david.brown@hesbynett.no> wrote: > >> On 28/10/14 18:59, upsidedown@downunder.com wrote: >>> On Tue, 28 Oct 2014 08:45:08 +0100, David Brown >>> <david.brown@hesbynett.no> wrote: >>> >>>> On 24/10/14 00:17, Paul Rubin wrote: >>>>> Dave Nadler <drn@nadler.com> writes: >>>>>> Even at O(log N), qsort chews up a lot of stack space for non-trivial N. >>>>>> heapsort is more appropriate in a resource-constrained environment... >>>>> >>>>> In an environment so resource-constrained that log N is consequential, >>>>> you aren't going to fit a non-trivial N anyway. So you may as well use >>>>> quicksort. ;-). >>>>> >>>> >>>> In a resource-constrained system you are often very interested in the >>>> runtime performance. >>> >>> Really ? >>> >>> If you have only a few hundred or thousand bytes of RAM/core even >>> primitive sorting methods, like bubble sort or insertion sort are >>> quite adequate even with a processor with 1 us cycle time. Except for >>> extremely low power applications, I would not bother with more >>> advanced sort algorithm. >>> >> >> You snipped the most important part "In particular, the worst-case >> performance is usually the most important - you have to be sure the >> operation finishes within a given time." >> >> Sometimes a simple sort /is/ the best choice. I said runtime >> performance is important - but that is very different from saying you >> want as fast performance as possible. Real-time systems are about doing >> the job within the required time, not about doing it quickly. > > My point was that with small data sets, even the worst case > performance is very sufficient. >Yes, absolutely. But you had taken half my comment and questioned its validity, so I felt I had to explain things a little more clearly.
Reply by ●October 29, 20142014-10-29
On Tue, 28 Oct 2014 19:59:05 +0200, upsidedown@downunder.com wrote:>On Tue, 28 Oct 2014 08:45:08 +0100, David Brown ><david.brown@hesbynett.no> wrote: > >>On 24/10/14 00:17, Paul Rubin wrote: >>> Dave Nadler <drn@nadler.com> writes: >>>> Even at O(log N), qsort chews up a lot of stack space for non-trivial N. >>>> heapsort is more appropriate in a resource-constrained environment... >>> >>> In an environment so resource-constrained that log N is consequential, >>> you aren't going to fit a non-trivial N anyway. So you may as well use >>> quicksort. ;-). >>> >> >>In a resource-constrained system you are often very interested in the >>runtime performance. > >Really ? > >If you have only a few hundred or thousand bytes of RAM/core even >primitive sorting methods, like bubble sort or insertion sort are >quite adequate even with a processor with 1 us cycle time. Except for >extremely low power applications, I would not bother with more >advanced sort algorithm.Something like Shell sort is only slightly more complex than insertion sort, but has significantly better performance, even for a few as ten elements. If you know you'll never have more than about a dozen items, go ahead and use insertion sort, but the boundary where switching to a slightly more sophisticated scheme (particularly Shell sort), is pretty low. And Shell sort is perfectly reasonably to use up to a few thousand elements (beyond which you should likely be heading for Heapsort).
