Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.arch.embedded > #18693 > unrolled thread
| Started by | Nobody <nobody@nowhere.invalid> |
|---|---|
| First post | 2014-10-17 00:00 +0100 |
| Last post | 2014-10-22 19:06 +0200 |
| Articles | 12 on this page of 112 — 24 participants |
Back to article view | Back to comp.arch.embedded
validity of ... reasons for preferring C over C++ Nobody <nobody@nowhere.invalid> - 2014-10-17 00:00 +0100
Re: validity of ... reasons for preferring C over C++ Wouter van Ooijen <wouter@voti.nl> - 2014-10-17 07:38 +0200
Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-17 09:27 +0200
Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-17 09:29 +0100
Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-17 11:19 +0200
Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-17 02:35 -0700
Re: validity of ... reasons for preferring C over C++ Arlet Ottens <usenet+5@c-scape.nl> - 2014-10-17 11:43 +0200
Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-17 12:12 +0100
Re: validity of ... reasons for preferring C over C++ Arlet Ottens <usenet+5@c-scape.nl> - 2014-10-17 13:25 +0200
Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-17 12:40 +0100
Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-17 20:12 +0300
Re: validity of ... reasons for preferring C over C++ Rob Gaddi <rgaddi@technologyhighland.invalid> - 2014-10-17 10:18 -0700
Re: validity of ... reasons for preferring C over C++ upsidedown@downunder.com - 2014-10-17 21:53 +0300
Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-17 22:59 +0300
Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-17 13:23 -0700
Re: validity of ... reasons for preferring C over C++ Jacob Sparre Andersen <jacob@jacob-sparre.dk> - 2014-10-18 17:46 +0200
Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-18 11:45 -0700
Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-19 01:51 +0300
Re: validity of ... reasons for preferring C over C++ Jacob Sparre Andersen <jacob@jacob-sparre.dk> - 2014-10-19 12:43 +0200
Re: validity of ... reasons for preferring C over C++ Jacob Sparre Andersen <jacob@jacob-sparre.dk> - 2014-10-18 17:44 +0200
Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-17 12:44 +0200
Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-17 12:13 +0100
Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-17 20:15 +0300
Re: validity of ... reasons for preferring C over C++ Arlet Ottens <usenet+5@c-scape.nl> - 2014-10-17 19:18 +0200
Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-17 23:03 +0200
Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-17 14:11 -0700
Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-18 20:14 +0200
Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-18 22:15 +0100
Re: validity of ... reasons for preferring C over C++ glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-10-18 23:07 +0000
Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-19 00:36 +0100
Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-19 10:55 +0300
Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-19 09:33 +0100
Re: validity of ... reasons for preferring C over C++ "Boudewijn Dijkstra" <sp4mtr4p.boudewijn@indes.com> - 2014-10-20 15:04 +0200
Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-19 13:32 +0200
Re: validity of ... reasons for preferring C over C++ Wouter van Ooijen <wouter@voti.nl> - 2014-10-17 23:44 +0200
Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-18 20:10 +0200
Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-18 23:38 +0300
Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-18 22:21 +0100
Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-19 10:43 +0300
Re: validity of ... reasons for preferring C over C++ Simon Clubley <clubley@remove_me.eisner.decus.org-Earth.UFP> - 2014-10-19 09:38 +0000
Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-19 14:07 +0200
Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-19 19:47 -0700
Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-20 06:55 +0300
Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-19 21:02 -0700
Re: validity of ... reasons for preferring C over C++ britt.snodgrass@gmail.com - 2014-10-20 04:02 -0700
Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-20 18:51 +0300
C and Ada, was: Re: validity of ... reasons for preferring C over C++ Simon Clubley <clubley@remove_me.eisner.decus.org-Earth.UFP> - 2014-10-21 00:30 +0000
Re: C and Ada, was: Re: validity of ... reasons for preferring C over C++ Les Cargill <lcargill99@comcast.com> - 2014-10-20 20:49 -0500
Re: C and Ada, was: Re: validity of ... reasons for preferring C over C++ Jacob Sparre Andersen <jacob@jacob-sparre.dk> - 2014-10-21 09:11 +0200
Re: C and Ada, was: Re: validity of ... reasons for preferring C over C++ Les Cargill <lcargill99@comcast.com> - 2014-10-21 08:34 -0500
Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-19 21:23 +0300
Re: validity of ... reasons for preferring C over C++ Nobody <nobody@nowhere.invalid> - 2014-10-20 03:39 +0100
Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-17 12:07 +0100
Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-17 12:06 +0100
Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-17 14:12 +0200
Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-17 13:16 +0100
Re: validity of ... reasons for preferring C over C++ Stef <stef33d@yahooI-N-V-A-L-I-D.com.invalid> - 2014-10-17 14:13 +0200
Re: validity of ... reasons for preferring C over C++ Arlet Ottens <usenet+5@c-scape.nl> - 2014-10-17 14:35 +0200
Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-17 13:59 +0100
Re: validity of ... reasons for preferring C over C++ Wouter van Ooijen <wouter@voti.nl> - 2014-10-17 17:06 +0200
Re: validity of ... reasons for preferring C over C++ upsidedown@downunder.com - 2014-10-17 19:41 +0300
Re: validity of ... reasons for preferring C over C++ Clifford Heath <no.spam@please.net> - 2014-10-18 10:14 +1100
Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-18 00:36 +0100
Re: validity of ... reasons for preferring C over C++ Clifford Heath <no.spam@please.net> - 2014-10-20 09:45 +1100
Re: validity of ... reasons for preferring C over C++ Niklas Holsti <niklas.holsti@tidorum.invalid> - 2014-10-18 08:52 +0300
Re: validity of ... reasons for preferring C over C++ Tom Gardner <spamjunk@blueyonder.co.uk> - 2014-10-18 09:41 +0100
Re: validity of ... reasons for preferring C over C++ Dave Nadler <drn@nadler.com> - 2014-10-20 09:46 -0700
Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-20 16:26 -0700
Re: validity of ... reasons for preferring C over C++ Dave Nadler <drn@nadler.com> - 2014-10-20 16:42 -0700
Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-20 17:24 -0700
Re: validity of ... reasons for preferring C over C++ John Devereux <john@devereux.me.uk> - 2014-10-21 19:09 +0100
Re: validity of ... reasons for preferring C over C++ Wouter van Ooijen <wouter@voti.nl> - 2014-10-24 16:38 +0200
Re: validity of ... reasons for preferring C over C++ Dave Nadler <drn@nadler.com> - 2014-10-21 15:12 -0700
Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-21 16:39 -0700
Re: validity of ... reasons for preferring C over C++ Nobody <nobody@nowhere.invalid> - 2014-10-22 01:43 +0100
Re: validity of ... reasons for preferring C over C++ Hans-Bernhard Bröker <HBBroeker@t-online.de> - 2014-10-22 20:00 +0200
Re: validity of ... reasons for preferring C over C++ Stefan Reuther <stefan.news@arcor.de> - 2014-10-22 18:49 +0200
Re: validity of ... reasons for preferring C over C++ Dave Nadler <drn@nadler.com> - 2014-10-21 15:15 -0700
Re: validity of ... reasons for preferring C over C++ Dave Nadler <drn@nadler.com> - 2014-10-22 04:45 -0700
Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-22 09:30 -0700
Re: validity of ... reasons for preferring C over C++ Dave Nadler <drn@nadler.com> - 2014-10-23 12:25 -0700
Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-23 15:17 -0700
Re: validity of ... reasons for preferring C over C++ glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-10-23 22:59 +0000
Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-23 16:02 -0700
Re: validity of ... reasons for preferring C over C++ Dave Nadler <drn@nadler.com> - 2014-10-27 08:30 -0700
Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-27 09:00 -0700
Re: validity of ... reasons for preferring C over C++ Dave Nadler <drn@nadler.com> - 2014-10-27 09:24 -0700
Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-27 09:30 -0700
Re: validity of ... reasons for preferring C over C++ glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-10-28 00:52 +0000
Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-28 08:45 +0100
Re: validity of ... reasons for preferring C over C++ Paul Rubin <no.email@nospam.invalid> - 2014-10-28 02:00 -0700
Re: validity of ... reasons for preferring C over C++ George Neuner <gneuner2@comcast.net> - 2014-10-30 11:56 -0400
Re: validity of ... reasons for preferring C over C++ upsidedown@downunder.com - 2014-10-28 19:59 +0200
Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-28 23:46 +0100
Re: validity of ... reasons for preferring C over C++ upsidedown@downunder.com - 2014-10-29 07:27 +0200
Re: validity of ... reasons for preferring C over C++ David Brown <david.brown@hesbynett.no> - 2014-10-29 10:11 +0100
Re: validity of ... reasons for preferring C over C++ Robert Wessel <robertwessel2@yahoo.com> - 2014-10-29 10:21 -0500
Re: validity of ... reasons for preferring C over C++ glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-10-29 20:15 +0000
Re: validity of ... reasons for preferring C over C++ Robert Wessel <robertwessel2@yahoo.com> - 2014-10-30 11:33 -0500
Re: validity of ... reasons for preferring C over C++ glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-10-30 19:07 +0000
Re: validity of ... reasons for preferring C over C++ Robert Wessel <robertwessel2@yahoo.com> - 2014-10-30 16:19 -0500
Re: validity of ... reasons for preferring C over C++ Nobody <nobody@nowhere.invalid> - 2014-10-31 07:32 +0000
Re: validity of ... reasons for preferring C over C++ glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-10-31 08:45 +0000
Re: validity of ... reasons for preferring C over C++ Reinhardt Behm <rbehm@hushmail.com> - 2014-10-31 18:15 +0800
Re: validity of ... reasons for preferring C over C++ glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-10-31 22:03 +0000
Re: validity of ... reasons for preferring C over C++ Robert Wessel <robertwessel2@yahoo.com> - 2014-10-31 09:53 -0500
Re: validity of ... reasons for preferring C over C++ glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-10-31 22:17 +0000
Re: validity of ... reasons for preferring C over C++ Les Cargill <lcargill99@comcast.com> - 2014-10-31 17:50 -0500
Re: validity of ... reasons for preferring C over C++ Nobody <nobody@nowhere.invalid> - 2014-10-28 04:37 +0000
Re: validity of ... reasons for preferring C over C++ Stefan Reuther <stefan.news@arcor.de> - 2014-10-21 19:12 +0200
Re: validity of ... reasons for preferring C over C++ Dave Nadler <drn@nadler.com> - 2014-10-21 15:06 -0700
Re: validity of ... reasons for preferring C over C++ Stefan Reuther <stefan.news@arcor.de> - 2014-10-22 19:06 +0200
Page 6 of 6 — ← Prev page 1 2 3 4 5 [6]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2014-10-30 16:19 -0500 |
| Message-ID | <0ga55a1qi68mc62dsm9ra98scoqk2tp50q@4ax.com> |
| In reply to | #19008 |
On Thu, 30 Oct 2014 19:07:19 +0000 (UTC), glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote: >Robert Wessel <robertwessel2@yahoo.com> wrote: > >(snip, I wrote) >>>The recent suggestions for quicksort is, when doing the recursion >>>(as previously noted, using an explicit stack, not recursive calls) >>>not to process very small partitions, but just return. Then, after >>>the quicksort part is finished, do in insertion sort on the whole >>>array. > >>>If elements are close to their final position, insertion sort >>>(with the right choices) is fast, making up for the partition >>>start overhead of quicksort. (The minimum partition size might >>>be about three.) > >> There are things to recommend either approach - insertion sorting >> small partitions, or insertion sorting the whole array at once. The >> later does reduce the startup overhead, but is much less cache >> friendly than immediately sorting the small partitions (which will >> almost always have been moved into near cache by the partitioning >> process which created them). I've not done a serious survey, but most >> recent implementations I've seen sort small partitions immediately. > >Hmm. How cache unfriendly is the part that goes back from the end >of the array? > >Seems like something that someone should study in detail, and on >a variety of processors. While the details will vary from implementations to implementation, you're basically looking at an extra trip through the cache of the entire array being sorted for the one-big-insertion-sort-at-the-end approach. Yes, hardware prefetchers should manage to deal with that, but you still have to stream the entire dataset in (and out) of cache. You avoid that by doing the "small" insertion sorts, because the partitions are in memory already, and will already needed to be written back to memory (since the partitioning will almost always have reordered the items in the partition). So you get the last phase of sorting done with no additional memory traffic. Of course that assumes the dataset is large enough to fit entirely into cache.
[toc] | [prev] | [next] | [standalone]
| From | Nobody <nobody@nowhere.invalid> |
|---|---|
| Date | 2014-10-31 07:32 +0000 |
| Message-ID | <pan.2014.10.31.07.32.14.520000@nowhere.invalid> |
| In reply to | #19003 |
On Wed, 29 Oct 2014 20:15:54 +0000, glen herrmannsfeldt wrote: > (Good quicksort doesn't use a fixed array element as the pivot for a > partition, but maybe the median of three elemennts. That pretty much > avoids the O(N**2) worst case.) Not really. It just cuts the number of steps in half: rather than the worst case consistently choosing the highest/lowest element as the partition, the worst case consistently chooses the second highest/lowest element.
[toc] | [prev] | [next] | [standalone]
| From | glen herrmannsfeldt <gah@ugcs.caltech.edu> |
|---|---|
| Date | 2014-10-31 08:45 +0000 |
| Message-ID | <m2vi72$8g3$1@speranza.aioe.org> |
| In reply to | #19010 |
Nobody <nobody@nowhere.invalid> wrote: (snip, I wrote) >> (Good quicksort doesn't use a fixed array element as the pivot for a >> partition, but maybe the median of three elemennts. That pretty much >> avoids the O(N**2) worst case.) > Not really. It just cuts the number of steps in half: rather than the > worst case consistently choosing the highest/lowest element as the > partition, the worst case consistently chooses the second highest/lowest > element. OK, if you don't like it use the random pivot selector. The problem with original quicksort wasn't that the worst case was so bad, but that it was so common. Note that the worst case for you is that all the air molecules randomly move to the side of the room you are not sitting in. Thermodynamics doesn't say that it is impossible, only that it is unlikely. As someone noted, in some cases a worst case can be supplied by a malicious user. For large N, not likely if you use a random pivot selector and the user can't guess the seed. -- glen
[toc] | [prev] | [next] | [standalone]
| From | Reinhardt Behm <rbehm@hushmail.com> |
|---|---|
| Date | 2014-10-31 18:15 +0800 |
| Message-ID | <m2vnfa$uog$1@dont-email.me> |
| In reply to | #19011 |
glen herrmannsfeldt wrote: > Nobody <nobody@nowhere.invalid> wrote: > > (snip, I wrote) >>> (Good quicksort doesn't use a fixed array element as the pivot for a >>> partition, but maybe the median of three elemennts. That pretty much >>> avoids the O(N**2) worst case.) > >> Not really. It just cuts the number of steps in half: rather than the >> worst case consistently choosing the highest/lowest element as the >> partition, the worst case consistently chooses the second highest/lowest >> element. > > OK, if you don't like it use the random pivot selector. > > The problem with original quicksort wasn't that the worst case was > so bad, but that it was so common. > > Note that the worst case for you is that all the air molecules > randomly move to the side of the room you are not sitting in. > Thermodynamics doesn't say that it is impossible, only that it > is unlikely. > > As someone noted, in some cases a worst case can be supplied > by a malicious user. For large N, not likely if you use a random > pivot selector and the user can't guess the seed. > > -- glen It is not the problem of a malicious user. In hard real time systems you just have to able to guaranty worst case behavior. Saying it is not probable is just not enough. -- Reinhardt
[toc] | [prev] | [next] | [standalone]
| From | glen herrmannsfeldt <gah@ugcs.caltech.edu> |
|---|---|
| Date | 2014-10-31 22:03 +0000 |
| Message-ID | <m310vn$31r$1@speranza.aioe.org> |
| In reply to | #19012 |
Reinhardt Behm <rbehm@hushmail.com> wrote: (snip, I wrote) >> OK, if you don't like it use the random pivot selector. >> The problem with original quicksort wasn't that the worst case was >> so bad, but that it was so common. >> Note that the worst case for you is that all the air molecules >> randomly move to the side of the room you are not sitting in. >> Thermodynamics doesn't say that it is impossible, only that it >> is unlikely. (snip) > It is not the problem of a malicious user. In hard real time > systems you just have to able to guaranty worst case behavior. > Saying it is not probable is just not enough. Do you consider the probability that your system will be hit by a large meteorite, or that a nuclear bomb will blow up nearby? (The latter more likely every day, with countries like Iran trying to build one.) If you are sorting 10 values, then you probably shouldn't use quicksort, anyway. If you are sorting a billion values, maybe unusual for embedded systems, but not impossible, and if people aren't choosing the values (that is, natural randomness instead of human randomness) there are 1000000000! possible initial permutations, reasonably equally probable. Consider that not only the worst case, by some nearby cases, so the probability of getting a bad case is only about 1 in 900000000! instead of the absolute worst 1 in 1000000000!. But as someone noted, the rules all change if someone can intentionally generate a worst case permutation. Assume open source, so that they know the actual algorithm and random number genertor in use. If they can't predict the seed, then it is up to 1 in (seed choices), which should still be pretty low, but maybe not low enough. Factorial grows darn fast, so the probabilities decrease very fast with increasing N. I have done plenty of sorts with billions of items, but even with millions, or 10s of thousands, it is plenty low enough. -- glen
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2014-10-31 09:53 -0500 |
| Message-ID | <be775ahj40nd7pnnlqredsni2jmi5rdlpg@4ax.com> |
| In reply to | #19011 |
On Fri, 31 Oct 2014 08:45:22 +0000 (UTC), glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote: >Nobody <nobody@nowhere.invalid> wrote: > >(snip, I wrote) >>> (Good quicksort doesn't use a fixed array element as the pivot for a >>> partition, but maybe the median of three elemennts. That pretty much >>> avoids the O(N**2) worst case.) > >> Not really. It just cuts the number of steps in half: rather than the >> worst case consistently choosing the highest/lowest element as the >> partition, the worst case consistently chooses the second highest/lowest >> element. > >OK, if you don't like it use the random pivot selector. > >The problem with original quicksort wasn't that the worst case was >so bad, but that it was so common. > >Note that the worst case for you is that all the air molecules >randomly move to the side of the room you are not sitting in. >Thermodynamics doesn't say that it is impossible, only that it >is unlikely. > >As someone noted, in some cases a worst case can be supplied >by a malicious user. For large N, not likely if you use a random >pivot selector and the user can't guess the seed. OTOH, a good (pseudo) random number generator is likely more work than implementing Introsort, and probably would probably add enough overhead to Quicksort that plain Heapsort would only be marginally faster, if at all. And it still doesn't *guarantee* non-quadratic behavior, even if it does make it unlikely (which is an issue in some environments). IMO, there are four sorts non-specialist programmers should know about, and be ready to use. Insertion (<10 items), Shell (<2000 items), and Heap, for things with array-like semantics. For linked-list sorts of data structures, merge sort is useful option. Quicksort *looks* simple, but has far too many pitfalls for the programmer not specifically versed in the subject. The four have few surprises, are simple to implement, and degrade reasonably gracefully when their nominal limits are (not-excessively) exceeded. Of course in most cases, you should try to use a well implemented sort library.
[toc] | [prev] | [next] | [standalone]
| From | glen herrmannsfeldt <gah@ugcs.caltech.edu> |
|---|---|
| Date | 2014-10-31 22:17 +0000 |
| Message-ID | <m311os$50r$1@speranza.aioe.org> |
| In reply to | #19013 |
Robert Wessel <robertwessel2@yahoo.com> wrote: (snip, I wrote) >>>> (Good quicksort doesn't use a fixed array element as the pivot for a >>>> partition, but maybe the median of three elemennts. That pretty much >>>> avoids the O(N**2) worst case.) >>> Not really. It just cuts the number of steps in half: rather than the >>> worst case consistently choosing the highest/lowest element as the >>> partition, the worst case consistently chooses the second highest/lowest >>> element. (I also wrote) >>OK, if you don't like it use the random pivot selector. >>The problem with original quicksort wasn't that the worst case was >>so bad, but that it was so common. (snip about a very unlikely way to die) >>As someone noted, in some cases a worst case can be supplied >>by a malicious user. For large N, not likely if you use a random >>pivot selector and the user can't guess the seed. > OTOH, a good (pseudo) random number generator is likely more work > than implementing Introsort, and probably would probably add enough > overhead to Quicksort that plain Heapsort would only be marginally > faster, if at all. I wondered a little about that. Seems to me that if you do random pivot selection for enough large partitions, maybe not all that many, and use median of three for smaller ones, you get most of the advantage. For even medium sized N, the permutations get large darn fast, so your main worry is someone intentionally supplying worst case. > And it still doesn't *guarantee* non-quadratic > behavior, even if it does make it unlikely (which is an issue in some > environments). And for some values of N. > IMO, there are four sorts non-specialist programmers should know > about, and be ready to use. Insertion (<10 items), Shell (<2000 > items), and Heap, for things with array-like semantics. For > linked-list sorts of data structures, merge sort is useful option. > Quicksort *looks* simple, but has far too many pitfalls for the > programmer not specifically versed in the subject. The four have few > surprises, are simple to implement, and degrade reasonably gracefully > when their nominal limits are (not-excessively) exceeded. When I had a CS course (large number) years ago, for one assignment we wrote insertion sort, selection sort, and bubble sort. For the next one, quicksort, heapsort, and shell sort. As was mentioned earlier, cache behavior should be considered. My first thought is that heap sort and shell sort aren't so good in cache use, but I haven't thought about it all that much. I always like the 3N+1 shell sort, should work well with interleaved memory, but maybe not with cache. > Of course in most cases, you should try to use a well > implemented sort library. -- glen
[toc] | [prev] | [next] | [standalone]
| From | Les Cargill <lcargill99@comcast.com> |
|---|---|
| Date | 2014-10-31 17:50 -0500 |
| Message-ID | <m313nb$5rj$1@dont-email.me> |
| In reply to | #19010 |
Nobody wrote: > On Wed, 29 Oct 2014 20:15:54 +0000, glen herrmannsfeldt wrote: > >> (Good quicksort doesn't use a fixed array element as the pivot for a >> partition, but maybe the median of three elemennts. That pretty much >> avoids the O(N**2) worst case.) > > Not really. It just cuts the number of steps in half: rather than the > worst case consistently choosing the highest/lowest element as the > partition, the worst case consistently chooses the second highest/lowest > element. > Sounds like a Nash equilibrium. -- Les Cargill
[toc] | [prev] | [next] | [standalone]
| From | Nobody <nobody@nowhere.invalid> |
|---|---|
| Date | 2014-10-28 04:37 +0000 |
| Message-ID | <pan.2014.10.28.04.37.28.729000@nowhere.invalid> |
| In reply to | #18923 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Stefan Reuther <stefan.news@arcor.de> |
|---|---|
| Date | 2014-10-21 19:12 +0200 |
| Message-ID | <m26b6g.3d4.1@stefan.msgid.phost.de> |
| In reply to | #18853 |
Dave Nadler wrote:
> On Wed, 15 Oct 2014 19:21:11 +0200, Wouter van Ooijen wrote:
>>PS I am (in the context of this question) NOT interested in
>>- whether a reason is valid (please start a different thread for
>>discussing this, I'll surely join in).
>
> !!! Availability of skilled C++ developers !!!
+1
What helps me most is that I am able to think like a compiler, because I
wrote half of one during university. Few people can do that (and it
isn't a skill that embedded recruiters have on their list). So while
most people can get a program correct after a while, only few can make
it efficient.
> In the embedded space, think about how many folks
> with lots of C++ on their resume could answer:
>
> 1) Give some examples where C++ can help you manage
> low-level machine access easier than raw C.
Your mileage will vary, but I found it very convenient to group things
such as "SPI driver" in classes. Just the fact that I can then use
spi.send(data);
instead of
freescale_mx35_spi_send(&spi, data);
would be a good argument for me.
> 2) In a small embedded system with no dynamic memory
> (other than the stack):
>
> 2a) What language features will you not be able to use?
This is a trick question, because if I don't have dynamic memory, I
could simply write my own allocator.
However, I will not be able to use most off-the-shelf components. If I
have a whopping 4 kilobytes of heap, I don't want a std::vector or
std::string that dutifully pre-allocates me 128 elements just to make
future appends faster.
> 2b) What special considerations will you expect when
> creating a class?
Depends on the compiler, but I would try to convince the compiler NOT to
generate exception-handling code. This could mean not using destructors,
and maybe even constructors. It still keeps language features like
templates and classes-for-encapsulation, but the experience will be very
different than for a "big" app.
> 3) Give an example where using C++ a template can generate
> more efficient code than typical C coding.
C++ templates can do compile-time polymorphy, that is, you use inline
code where you would use function pointers in C.
For a previous project, I was writing several drivers; some already
existed in a prototype version in C. Drivers needed some sort of
request/result queues. The C versions implemented these queues anew,
every damn time, probably with a lot of cut & paste involved. First
thing I did was to add a simple Queue template class and use it
everywhere. My final source code was around half the size and much more
maintainable than the C version; the object code was smaller by a few
percent, too.
Stefan
[toc] | [prev] | [next] | [standalone]
| From | Dave Nadler <drn@nadler.com> |
|---|---|
| Date | 2014-10-21 15:06 -0700 |
| Message-ID | <d33afc9e-1f68-4c26-b075-4526fbcf8257@googlegroups.com> |
| In reply to | #18865 |
On Tuesday, October 21, 2014 1:12:15 PM UTC-4, Stefan Reuther wrote: > What helps me most is that I am able to think like a compiler, because I > wrote half of one during university. Few people can do that (and it > isn't a skill that embedded recruiters have on their list). So while > most people can get a program correct after a while, only few can make > it efficient. Um, you think like half a compiler ? ;-) Really, for C++ it is necessary to understand what happens under the hood (contrary to the definition of a good tool), but how the compiler works?? > > 2) In a small embedded system with no dynamic memory > > (other than the stack): > > 2a) What language features will you not be able to use? > > This is a trick question, because if I don't have dynamic memory, I > could simply write my own allocator. No, it is not a trick question, and that is NOT the answer... > > 2b) What special considerations will you expect when > > creating a class? > > Depends on the compiler, but I would try to convince the compiler NOT to > generate exception-handling code. Why does it depend on the compiler?? > This could mean not using destructors, > and maybe even constructors. No, no, no... What else? > For a previous project, I was writing several drivers; some already > existed in a prototype version in C. Drivers needed some sort of > request/result queues. The C versions implemented these queues anew, > every damn time, probably with a lot of cut & paste involved. First > thing I did was to add a simple Queue template class and use it > everywhere. My final source code was around half the size and much more > maintainable than the C version; the object code was smaller by a few > percent, too. A good example of C++ helping! However, some would argue you should have implemented the queue code once using void* (and maybe item size), then wrapped it with inlines using specific names/types for safety. Hopefully you wrote a unit test for your template before using it! Thanks for your thoughts, Best Regards, Dave
[toc] | [prev] | [next] | [standalone]
| From | Stefan Reuther <stefan.news@arcor.de> |
|---|---|
| Date | 2014-10-22 19:06 +0200 |
| Message-ID | <m28v7r.5g.1@stefan.msgid.phost.de> |
| In reply to | #18867 |
Dave Nadler wrote:
> On Tuesday, October 21, 2014 1:12:15 PM UTC-4, Stefan Reuther wrote:
>>What helps me most is that I am able to think like a compiler, because I
>>wrote half of one during university. Few people can do that (and it
>>isn't a skill that embedded recruiters have on their list). So while
>>most people can get a program correct after a while, only few can make
>>it efficient.
>
> Um, you think like half a compiler ? ;-)
> Really, for C++ it is necessary to understand what happens
> under the hood (contrary to the definition of a good tool),
> but how the compiler works??
Things like: what information does the compiler have at this point? What
information would it need to do this transformation? What border cases
does it have to handle? This leads to consequences such that it has to
generate an exception handling frame here because it cannot prove that
this trivial function never throws, that it has to instantiate (and thus
has to see) this template here because it cannot assume anything about
it being instantiated elsewhere, or that 'std::string s = a+b+c+d;'
creates an uncomfortable number of temporaries whereas 'std::string s =
a; s += b; s += c; s += d;' does not.
Call it "what happens under the hood" or "how does the compiler think",
the idea is the same.
>>>2) In a small embedded system with no dynamic memory
>>>(other than the stack):
>>>2a) What language features will you not be able to use?
>>
>>This is a trick question, because if I don't have dynamic memory, I
>>could simply write my own allocator.
>
> No, it is not a trick question, and that is NOT the answer...
Why not? C++ at least makes it a language feature and a library feature
to make my own allocator.
But if I cannot use 'new' and 'delete' the answer simply becomes: "I
cannot use the language features 'new' and 'delete'" :-) I also cannot
use most of the STL, but that's not a core language feature.
>>>2b) What special considerations will you expect when
>>>creating a class?
>>
>>Depends on the compiler, but I would try to convince the compiler NOT to
>>generate exception-handling code.
>
> Why does it depend on the compiler??
Because on some compilers this is the matter of just flipping a switch,
so I can use my already-written classes; on others I'd have to write
special exception-less code to avoid that the compiler generates code I
do not want.
>>This could mean not using destructors,
>>and maybe even constructors.
>
> No, no, no...
> What else?
What else are you expecting? Other memory saving techniques like using
bitfields ("enum {...} foo : 8" to save 3 bytes) are not C++-specific,
and apply to C as well.
>>For a previous project, I was writing several drivers; some already
>>existed in a prototype version in C. Drivers needed some sort of
>>request/result queues. The C versions implemented these queues anew,
>>every damn time, probably with a lot of cut & paste involved. First
>>thing I did was to add a simple Queue template class and use it
>>everywhere. My final source code was around half the size and much more
>>maintainable than the C version; the object code was smaller by a few
>>percent, too.
>
> A good example of C++ helping!
> However, some would argue you should have implemented the queue code
> once using void* (and maybe item size), then wrapped it with inlines
> using specific names/types for safety.
In this particular case, the class went roughly like this:
template<typename T, size_t N> class Queue {
void post(const T& t)
{ m_elems[m_head++ % N] = t; }
T get()
{ return m_elems[m_tail++ % N]; }
T m_elems[N];
size_t m_head, m_tail;
};
(details omitted) where each function generates a few machine
instructions only. Adding a void* and a size_t would only have made
matters more complicated.
> Hopefully you wrote a unit test for your template before using it!
Well, I did that before using it in the next project, where we finally
hat infrastructure for making unit tests in the build system :)
Stefan
[toc] | [prev] | [standalone]
Page 6 of 6 — ← Prev page 1 2 3 4 5 [6]
Back to top | Article view | comp.arch.embedded
csiph-web