On Friday, 19 April 2013 at 22:37:45 UTC, Ivan Kazmenko wrote:
So, why isn't TimSort the default?
I would actually argue for this, not for safety (introsort is an
adequate solution) but for different reasons. Timsort is stable
and it's faster on data with low entropy, being nearly
instantane
24-Apr-2013 01:09, Ivan Kazmenko пишет:
And on Tuesday, 23 April 2013 at 01:10:26 UTC, Xinok wrote:
I filed a bug report for this issue a year ago:
http://d.puremagic.com/issues/show_bug.cgi?id=7767
I've been meaning to fix this issue myself. Time allowing, I'll do it
soon.
What I wonder now,
23-Apr-2013 05:17, Xinok пишет:
On Saturday, 20 April 2013 at 16:35:25 UTC, Dmitry Olshansky wrote:
And this all is good but TimSort allocates O(N) memory. The constant
in front of N is smallish less then 1.0 but it could cause some grief.
Worst case is O(n/2), but it starts small and doubles
On Tuesday, 23 April 2013 at 17:42:08 UTC, Xinok wrote:
Choosing a random pivot will always invoke "average"
performance where as finding the median of N elements usually
achieves better performance on sorted lists. You also have to
be careful that equal elements are distributed equally among
On Monday, 22 April 2013 at 21:34:47 UTC, Andrei Alexandrescu
wrote:
a) choose median of five
Sounds like it could decrease speed on average, and still perhaps
fail on a simple case like [0, 1, 2, 3, ..., 999, 0, 0] or
something? Didn't test it though.
b) if the array is large, sort a st
On Tuesday, 23 April 2013 at 14:12:01 UTC, bearophile wrote:
Andrei Alexandrescu:
There's not "the C++ STL sort". Any implementation is fine as
long as it has O(n log n) expected run time.
This seems to use the Introsort:
http://www.sgi.com/tech/stl/sort.html
I don't know if Xinok has tested
Andrei Alexandrescu:
There's not "the C++ STL sort". Any implementation is fine as
long as it has O(n log n) expected run time.
This seems to use the Introsort:
http://www.sgi.com/tech/stl/sort.html
I don't know if Xinok has tested a 2-pivot quicksort (called by
the usual Introsort setting).
On 4/22/13 5:52 PM, bearophile wrote:
Andrei Alexandrescu:
c) add introspection to the algorithm, i.e. if an attempt to partition
hits the worst case or near worst case, just try another pivot instead
of moving forward with the sorting stage.
Or switch to a sort that is guaranteed to have a p
On Tuesday, 23 April 2013 at 01:28:56 UTC, bearophile wrote:
Xinok:
I've been meaning to fix this issue myself. Time allowing,
I'll do it soon.
Good. And if you are willing, please also take a look at the
parallel sort problem I've raised:
http://forum.dlang.org/thread/iyunhhsbmurqyouyr...
Xinok:
I've been meaning to fix this issue myself. Time allowing, I'll
do it soon.
Good. And if you are willing, please also take a look at the
parallel sort problem I've raised:
http://forum.dlang.org/thread/iyunhhsbmurqyouyr...@forum.dlang.org
Bye,
bearophile
On Saturday, 20 April 2013 at 16:35:25 UTC, Dmitry Olshansky
wrote:
And this all is good but TimSort allocates O(N) memory. The
constant in front of N is smallish less then 1.0 but it could
cause some grief.
Worst case is O(n/2), but it starts small and doubles in size as
needed. On a partial
On Friday, 19 April 2013 at 21:03:23 UTC, Ivan Kazmenko wrote:
Hi!
Consider a sorted array. Append an element that is less than
all the previous elements. Then sort the array again by the
sort function from std.algorithm.
With n = 30_000 as in the example, this takes time of the orde
And by the way, I still suggest a dual-pivot quicksort:
http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628
Bye,
bearophile
Andrei Alexandrescu:
c) add introspection to the algorithm, i.e. if an attempt to
partition hits the worst case or near worst case, just try
another pivot instead of moving forward with the sorting stage.
Or switch to a sort that is guaranteed to have a pseudo-linear
complexity.
I am not su
On 4/19/13 6:37 PM, Ivan Kazmenko wrote:
That [SwapStrategystable] uses the TimSort that contains
the optimization you look for.
alias mySort = sort!("a < b", SwapStrategy.stable);
Thank you, these are good for now.
A seemingly easy way to provide the choice globally would be to have an
assig
20-Apr-2013 16:22, Chris Cain пишет:
On Friday, 19 April 2013 at 22:56:00 UTC, bearophile wrote:
So, why isn't TimSort the default?
Probably because someone thinks that "on average" the other sort is
faster.
In theory the other should be faster, because if you relax the
constraints of the sor
On Friday, 19 April 2013 at 22:56:00 UTC, bearophile wrote:
So, why isn't TimSort the default?
Probably because someone thinks that "on average" the other
sort is faster.
In theory the other should be faster, because if you relax the
constraints of the sort being stable I think in theory yo
Ivan Kazmenko:
A seemingly easy way to provide the choice globally would be to
have an assignable SwapStrategy.default in std.algorithm... or
would that be a bad design decision to have such a global state?
With that I think there is no way to write a pure sort. Hopefully
someday the sort()
That [SwapStrategystable] uses the TimSort that contains
the optimization you look for.
alias mySort = sort!("a < b", SwapStrategy.stable);
Thank you, these are good for now.
A seemingly easy way to provide the choice globally would be to
have an assignable SwapStrategy.default in std.algorit
20-Apr-2013 02:12, Ivan Kazmenko пишет:
With n = 30_000 as in the example, this takes time of the order of a
second on a modern computer, which is clearly O(n^2). I am using DMD
2.062.
Optimization flags if any?
Both "-O" and no-flags give quadratic behavior.
I sought after
-O -inline -re
With n = 30_000 as in the example, this takes time of the
order of a
second on a modern computer, which is clearly O(n^2). I am
using DMD
2.062.
Optimization flags if any?
Both "-O" and no-flags give quadratic behavior.
Well, if that does not convince you the time grows faster than
n-log-
20-Apr-2013 01:03, Ivan Kazmenko пишет:
With n = 30_000 as in the example, this takes time of the order of a
second on a modern computer, which is clearly O(n^2). I am using DMD
2.062.
Optimization flags if any?
--
Dmitry Olshansky
Ivan Kazmenko:
Consider a sorted array. Append an element that is less than
all the previous elements. Then sort the array again by the
sort function from std.algorithm.
If you know that, then don't do a sort. Make some free space in
the array, shift the items, sort just the first part with
Hi!
Consider a sorted array. Append an element that is less than all
the previous elements. Then sort the array again by the sort
function from std.algorithm.
An example follows:
-
import std.algorithm;
import std.datetime;
import std.range;
import std.stdio;
void main ()
{
in
24 matches
Mail list logo
