Regarding the recent Phobos improvements that introduce a Timsort:
http://forum.dlang.org/thread/50c8a4e67f79_3fdd19b7ae8146...@sh3.rs.github.com.mail
I have found a blog post that compares the performance of
Timsort, Smoothsort, and std::stable_sort:
http://www.altdevblogaday.com/2012/06/15/
On Monday, 17 December 2012 at 15:28:36 UTC, bearophile wrote:
Regarding the recent Phobos improvements that introduce a
Timsort:
http://forum.dlang.org/thread/50c8a4e67f79_3fdd19b7ae8146...@sh3.rs.github.com.mail
I have found a blog post that compares the performance of
Timsort, Smoothsort,
On Tuesday, 18 December 2012 at 06:52:27 UTC, Xinok wrote:
On another note, I highly doubt that std::sort uses a "median
of medians" algorithm, which would add much overhead and
essentially double the number of comparisons required with
little to no benefit. More likely, it simply chooses the p
On 12/18/2012 07:52 AM, Xinok wrote:
While Smoothsort may be mathematically sound, it simply doesn't translate well
to computer hardware. It's a variant of heap sort which requires a great deal of
random access, whereas Timsort is a variant of merge sort which is largely
sequential and benefits f
Joseph Rushton Wakeling:
... but I would guess that given the O(1) memory requirements
it probably scales much better to sorting really, really large
data, no?
Why?
Bye,
bearophile
On 12/18/2012 04:30 PM, bearophile wrote:
Why?
Because if you have to allocate O(n) memory for another algorithm, that might
either give you a memory hit that you can't take (less likely these days, to be
fair), or simply take a large amount of time to allocate that degrades the
performance.
On 12/18/12 5:50 AM, Peter Alexander wrote:
On Tuesday, 18 December 2012 at 06:52:27 UTC, Xinok wrote:
On another note, I highly doubt that std::sort uses a "median of
medians" algorithm, which would add much overhead and essentially
double the number of comparisons required with little to no be
On Tuesday, 18 December 2012 at 15:27:07 UTC, Joseph Rushton
Wakeling wrote:
On 12/18/2012 07:52 AM, Xinok wrote:
While Smoothsort may be mathematically sound, it simply
doesn't translate well
to computer hardware. It's a variant of heap sort which
requires a great deal of
random access, wherea
On Tuesday, 18 December 2012 at 15:55:17 UTC, Andrei Alexandrescu
wrote:
Another approach I wanted to try was to choose the median of K
with K increasing with the size of the array. This is because a
good pivot is more important for large arrays than for small
arrays. As such, a possibility wou
On 12/18/12 8:42 PM, Xinok wrote:
On Tuesday, 18 December 2012 at 15:55:17 UTC, Andrei Alexandrescu wrote:
Another approach I wanted to try was to choose the median of K with K
increasing with the size of the array. This is because a good pivot is
more important for large arrays than for small a
Andrei Alexandrescu:
A very efficient sort for various small fixed sizes is a great
complement for quicksort.
Do you mean to use it when the input is very short, or when the
QuickSort recursion has produced a very small subarray? In the
first case it's useful, but in the second case I've see
On Wednesday, 19 December 2012 at 02:00:05 UTC, Andrei
Alexandrescu wrote:
On 12/18/12 8:42 PM, Xinok wrote:
On Tuesday, 18 December 2012 at 15:55:17 UTC, Andrei
Alexandrescu wrote:
Another approach I wanted to try was to choose the median of
K with K
increasing with the size of the array. This
On Wednesday, 19 December 2012 at 02:00:05 UTC, Andrei
Alexandrescu wrote:
You don't need to choose a median - just sort the data (thereby
making progress toward the end goal) and choose the middle
element.
I don't think it would work well in practice, but I'll put
something together to see i
On Tuesday, 18 December 2012 at 15:41:28 UTC, Joseph Rushton
Wakeling wrote:
On 12/18/2012 04:30 PM, bearophile wrote:
Why?
Because if you have to allocate O(n) memory for another
algorithm, that might either give you a memory hit that you
can't take (less likely these days, to be fair), or
On 12/18/12 10:35 PM, ixid wrote:
A while ago in another thread about sorting I believe you mentioned the
possibility of having templated sorting networks for small numbers of
items, did that idea come to anything?
Not that I know of.
Andrei
On 12/18/12 9:21 PM, bearophile wrote:
Andrei Alexandrescu:
A very efficient sort for various small fixed sizes is a great
complement for quicksort.
Do you mean to use it when the input is very short, or when the
QuickSort recursion has produced a very small subarray?
The latter.
In the f
On 12/18/12 11:37 PM, Xinok wrote:
On Wednesday, 19 December 2012 at 02:00:05 UTC, Andrei Alexandrescu wrote:
You don't need to choose a median - just sort the data (thereby making
progress toward the end goal) and choose the middle element.
I don't think it would work well in practice, but I'
On 12/19/2012 06:00 AM, deadalnix wrote:
Unless you have the data somehow presorted, or you get them one by one, other
sort are faster.
I was probably imprecise with my use of the word "scales". Obviously other
algorithms have superior O() for the general case, but if memory use also scales
On Wed, Dec 19, 2012 at 6:47 AM, Andrei Alexandrescu <
seewebsiteforem...@erdani.org> wrote:
> On 12/18/12 10:35 PM, ixid wrote:
>
>> A while ago in another thread about sorting I believe you mentioned the
>> possibility of having templated sorting networks for small numbers of
>> items, did that
On Wednesday, 19 December 2012 at 05:48:04 UTC, Andrei
Alexandrescu wrote:
On 12/18/12 11:37 PM, Xinok wrote:
On Wednesday, 19 December 2012 at 02:00:05 UTC, Andrei
Alexandrescu wrote:
You don't need to choose a median - just sort the data
(thereby making
progress toward the end goal) and choo
20 matches
Mail list logo
