Groups | Search | Server Info | Keyboard shortcuts | Login | Register
Groups > comp.lang.java.programmer > #4257
| From | Michael Wojcik <mwojcik@newsguy.com> |
|---|---|
| Newsgroups | comp.lang.java.programmer |
| Subject | Re: Did the sort do anything? |
| Date | 2011-05-18 11:14 -0400 |
| Organization | Micro Focus |
| Message-ID | <ir0oj24mcj@news5.newsguy.com> (permalink) |
| References | <eskis656eeu0of5f5do1ogdpfbdau3d06i@4ax.com> <iqbmo6$j47$1@dont-email.me> <iqkt5k$k58$1@lust.ihug.co.nz> <iqnh0d$m0m$1@news.albasani.net> <alpine.DEB.2.00.1105151117070.12373@urchin.earth.li> |
Tom Anderson wrote: > > What would shut me up would be a performance comparison of two > comparable-quality implementations of the algorithms, showing that > Timsort wipes the floor with Smoothsort. Is anyone aware of one? The usual problem with heapsort-based algorithms, besides having O(n lg n) as a lower bound, is that they have lousy locality of reference. In traditional heapsort, once the heap is built, you proceed by taking the leftmost element in the array (the root of the heap) and swapping it with the last element of the heap part of the array. If the heap size is not trivial, you're doing a load from one cache line and a store into another. Smoothsort appears to fix this problem, because it keeps the largest elements at the right end of the forest of heaps, so the move from the forest of heaps to the sorted part of the array is local. It also avoids having to re-heapify large heaps, since it always operates on the smallest heap left in the forest, and it splits large heaps as it dequeues from them. In fact, while I've never tried implementing smoothsort, much less analyzed its behavior, it looks like it has quite good locality of reference. But Timsort has great locality of reference, because it deals in runs (including reversed-order runs), and when it doesn't have a decent run at the current position, it sorts a small fragment of the array to create one. On the other hand, when sorts are used in most modern applications, they're comparing keys that are located elsewhere in memory and probably invoking a user-supplied comparison function, so locality of reference may not have much effect on performance. -- Michael Wojcik Micro Focus Rhetoric & Writing, Michigan State University
Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar
Did the sort do anything? Roedy Green <see_website@mindprod.com.invalid> - 2011-05-10 08:06 -0700
Re: Did the sort do anything? markspace <-@.> - 2011-05-10 08:48 -0700
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-14 15:33 +1200
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-14 08:56 -0400
Re: Did the sort do anything? Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-05-14 13:54 +0000
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-15 11:16 +1200
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-14 23:24 -0400
Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-15 11:20 +0100
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-15 07:00 -0400
Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-15 15:09 +0100
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-16 14:28 +1200
Re: Did the sort do anything? Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-05-15 22:38 -0400
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-16 19:11 +1200
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-16 03:47 -0400
Re: Did the sort do anything? markspace <-@.> - 2011-05-16 14:14 -0700
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-15 22:40 -0400
Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-16 21:31 +0100
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-17 09:12 +1200
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-16 17:24 -0400
Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-17 13:26 +0100
Re: Did the sort do anything? markspace <-@.> - 2011-05-15 04:56 -0700
Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-15 15:12 +0100
Re: Did the sort do anything? markspace <-@.> - 2011-05-15 07:52 -0700
Re: Did the sort do anything? Michael Wojcik <mwojcik@newsguy.com> - 2011-05-18 11:14 -0400
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-18 13:02 -0400
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-20 18:49 +1200
Re: Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-20 00:06 -0700
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-20 22:37 +1200
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-20 07:09 -0400
Re: Did the sort do anything? Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-05-10 16:11 +0000
Re: Did the sort do anything? Daniele Futtorovic <da.futt.news@laposte-dot-net.invalid> - 2011-05-10 21:26 +0200
Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-11 21:38 +0100
Re: Did the sort do anything? Daniele Futtorovic <da.futt.news@laposte-dot-net.invalid> - 2011-05-11 23:27 +0200
Re: Did the sort do anything? Roedy Green <see_website@mindprod.com.invalid> - 2011-05-13 07:40 -0700
Re: Did the sort do anything? Spock <spock@starfleet.ufp> - 2011-05-13 16:56 -0400
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-15 13:58 +1200
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-14 23:27 -0400
Re: Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-11 20:40 +0200
Re: Did the sort do anything? Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-05-12 10:40 -0400
Re: Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-13 03:50 -0700
Re: Did the sort do anything? Roedy Green <see_website@mindprod.com.invalid> - 2011-05-13 07:46 -0700
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-16 14:32 +1200
Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-15 19:50 -0700
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-16 17:57 +1200
Re: Did the sort do anything? "javax.swing.JSnarker" <gharriman@boojum.mit.edu> - 2011-05-16 03:35 -0400
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-16 03:44 -0400
Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-16 03:53 -0700
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-17 00:02 +1200
Re: Did the sort do anything? "javax.swing.JSnarker" <gharriman@boojum.mit.edu> - 2011-05-16 08:05 -0400
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-17 09:12 +1200
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-16 17:32 -0400
Re: Did the sort do anything? thoolen <thoolen@tholenbot.thorium> - 2011-05-16 18:09 -0400
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-16 10:02 -0400
Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-16 07:16 -0700
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-17 09:11 +1200
Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-16 15:00 -0700
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-16 21:08 -0400
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-17 19:11 +1200
Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-17 02:34 -0700
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-17 07:19 -0400
[OT] Naming conventions. Was: Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-17 06:52 -0700
Re: Naming conventions. Was: Re: Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-18 01:22 -0700
Re: Naming conventions. Was: Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-18 03:42 -0700
Re: Naming conventions. Was: Re: Did the sort do anything? RedGrittyBrick <RedGrittyBrick@spamweary.invalid> - 2011-05-18 11:53 +0100
Re: Naming conventions. Was: Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-18 13:07 -0400
Re: Naming conventions. Was: Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-18 10:37 -0700
Re: Naming conventions. Was: Re: Did the sort do anything? Heike Svensson <hsvensson.1093x1_q@hotmail.nospam.com.please> - 2011-05-19 01:29 -0400
Re: Naming conventions. Was: Re: Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-19 08:28 +0200
Re: Naming conventions. Was: Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-19 08:50 -0400
OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? RedGrittyBrick <RedGrittyBrick@spamweary.invalid> - 2011-05-23 10:25 +0100
Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-23 09:05 -0400
Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? RedGrittyBrick <RedGrittyBrick@spamweary.invalid> - 2011-05-23 17:17 +0100
Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-23 14:43 -0400
Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? Steve Sobol <sjsobol@JustThe.net> - 2011-05-23 08:27 -0700
Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? RedGrittyBrick <RedGrittyBrick@spamweary.invalid> - 2011-05-23 17:39 +0100
Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-23 19:16 +0200
Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-23 14:47 -0400
Re: Did the sort do anything? Boojum <boojum42@gmai1.c0m> - 2011-05-18 07:19 -0400
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-20 18:46 +1200
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-20 07:10 -0400
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-17 07:16 -0400
Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-17 06:56 -0700
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-20 18:46 +1200
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-20 07:11 -0400
Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-20 05:00 -0700
Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-20 05:20 -0700
Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-21 09:56 +1200
Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-20 18:12 -0400
Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-20 21:26 -0700
Re: Did the sort do anything? Gheerax IV <gheerax.4@gmail.invalid> - 2011-05-17 06:58 +0000
Re: Did the sort do anything? Unitary Matrix <umatrix668@gmail.com> - 2011-05-17 00:13 -0700
Re: Did the sort do anything? markspace <-@.> - 2011-05-17 07:41 -0700
Re: Did the sort do anything? Roedy Green <see_website@mindprod.com.invalid> - 2011-05-13 07:42 -0700
Re: Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-13 21:28 +0200
Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-11 21:32 +0100
csiph-web