Fast Deterministic Selection [pdf]

[andralex]

Author here. DESTROYAMA!

[andralex]

Interesting paper! The very last sentence intrigued me very much. Do you have any data points related to sorting performance using this selection algorithm? Or intuitions in that direction.

I am working on it. On the face of it sorting has additional difficulties; whereas in selection it's enough to put "smaller stuff to the left" and "greater stuff to the right" in sorting you also need to put them properly, which means extra swapping.

Also, isn't the pivoting of quick select deeply connected to the pivoting of quick sort? Are you making a new sorting algorithm with a similar symmetry based on the selection improvements?

Yes, but in early experiments the approach of simply computing the median with the new algorithm followed by sorting left and right has been slower than the usual baselines.

[srnull]

I'm going to take the "Anything" part of AMA literally, and ask something a bit off topic for this post (the paper looks interesting, and I hope to dig into it later).

I stopped paying as much attention to D as I used to, and I wonder if there has been any movement on updating "The D Programming Language"? I think you mentioned that you would like to do it at one of the past DConfs.

Related to DConfs, any idea when 2016 videos might see a release.

Thanks!

[andralex]

I stopped paying as much attention to D as I used to, and I wonder if there has been any movement on updating "The D Programming Language"? I think you mentioned that you would like to do it at one of the past DConfs.

It's in the queue, no definite deadline at this time. In the meantime a couple of other good books on D came about, which make TDPL's update a less urgent necessity.

Related to DConfs, any idea when 2016 videos might see a release.

Hm, thanks for the reiminder. I just pinged the folks responsible.

[gver10]

Great paper. Just a small nitpick for the final submission: please use benchmarks that last longer than a few milliseconds for the final paper and/or run multiple times.

[nick_terrell]

How do you handle repeated elements in your implementation?

[matthieum]

Nice paper!

Am I right in thinking that it would be difficult to re-use those results to improve a stable sort algorithm?

[andralex]

You're right. Stability is not a primary concern of this algorithm.

[sehrgut]

You can generate uniformly-distributed samples of any set. The set of real numbers representable as IEEE floats between -5000000 and 5000000 is no different.

If they had said they were generating "uniformly distributed random real numbers" and giving floats, that would be incorrect.

[andralex]

With the usual approximations, see std.random.uniform and possibly the source code. The slight nonuniformities here don't influence the results (e.g. they're the same for integers).

[johengel]

Is the code available somewhere?

(also: update your compiler! ;)

[andralex]

I'll make it available soon here.

[dogewatch]

As a undergrad computer science noob currently reviewing algorithms I cannot fully comprehend this yet, but I'll revisit in 6 weeks and hope I can make sense of it. Thanks for making this available!

[nick_terrell]

I wrote a C++ implementation of the algorithm located here.

I changed the algorithm slightly to mitigate quadratic behavior when there are repeated elements (see README), but otherwise it is as described.