On 01/03/2017 03:01 AM, Nicholas Wilson wrote:
https://probablydance.com/2016/12/27/i-wrote-a-faster-sorting-algorithm/
on reddit
https://www.reddit.com/r/programming/comments/5lqgks/i_wrote_a_faster_sorting_algorithm/
In the reddit comments there's the one idea worth looking at:
https
just to show a usecase, some code, ripped out from one of my
simple engines (sorry for the mess):
import std.stdio;
enum ObjectCount = 1000;
struct RadixSorter(OT)
if (is(OT == class) && is(typeof(OT.init.sortkey) == uint) &&
is(typeof(OT.init.next) : OT))
{
private:
OT[256] heads;
On Tuesday, 3 January 2017 at 08:01:59 UTC, Nicholas Wilson wrote:
https://probablydance.com/2016/12/27/i-wrote-a-faster-sorting-algorithm/
on reddit
https://www.reddit.com/r/programming/comments/5lqgks/i_wrote_a_faster_sorting_algorithm/
ah, radix sort again, trading memory for speed
https://probablydance.com/2016/12/27/i-wrote-a-faster-sorting-algorithm/
on reddit
https://www.reddit.com/r/programming/comments/5lqgks/i_wrote_a_faster_sorting_algorithm/
Manfred Nowak wrote:
Population and sweep would each be linear in time.
The sweep is linear in time only, if the populatable points of the area
are bount by O(n), which is not neccessary the case.
Therefore, I don't see to find in the generell case a solution faster
than
O( n + k*log(
On 1/27/12 11:02 PM, H. S. Teoh wrote:
If you treat the attributes as components of an n-dimensional vector,
then you could recast the problem as the convex hull of k hypercuboids,
where each hypercuboid lies between (0,0,0,...) and (x1,x2,x3,...). The
points on the convex hull then are the
On 1/28/12 1:08 AM, Manfred Nowak wrote:
Andrei Alexandrescu wrote:
generally what one wants is a selection of best of breed stocks
that are among the top ones in a variety of categories. (Relative
importance could be assigned to each category.)
This is quite different and easier than the
Andrei Alexandrescu wrote:
[ About ranks]
Actually they need to be computed.
Then the problem is still too unclear.
I think it's possible to find cases where
rank(a, k1) + rank(a, k2) rank(b, k1) + rank(b, k2)
but
alpha * a.k1 + beta * a.k2 alpha * b.k1 + beta.k2.
Of course.
On 1/28/12 9:10 AM, Manfred Nowak wrote:
Andrei Alexandrescu wrote:
[ About ranks]
Actually they need to be computed.
Then the problem is still too unclear.
It's very simple and clear in formulation actually.
Given a range r of elements, define rank(a, p) as the position that
object a
On Sat, Jan 28, 2012 at 08:12:52AM -0600, Andrei Alexandrescu wrote:
On 1/27/12 11:02 PM, H. S. Teoh wrote:
If you treat the attributes as components of an n-dimensional vector,
then you could recast the problem as the convex hull of k hypercuboids,
where each hypercuboid lies between
Andrei Alexandrescu wrote:
we have multiple predicates, p1, p2, ..., pk. We want to sort
elements in increasing order of rank(a, p1) + ... + rank(a, pk).
Got it. Thinking ocasionally.
-manfred
On 1/28/12 10:29 AM, H. S. Teoh wrote:
Actually, the reason I chose hypercubes was because I was hoping that
the convex hull with hypercubes in the original features' space would be
equivalent (or easily massaged to be equivalent) to using simplexes in
rank space. (Although the part about the
Here's a multikey sorting problem that's bothering me; I think it's well
researched but I can't find the right keywords.
Say we have a collection of people with height and hair length
information. We want to get people who are tall and long-haired. More
precisely, we want to order people by
On 01/27/2012 08:36 PM, Andrei Alexandrescu wrote:
Here's a multikey sorting problem that's bothering me; I think it's well
researched but I can't find the right keywords.
Say we have a collection of people with height and hair length
information. We want to get people who are tall and
On 1/27/12 3:07 PM, sclytrack wrote:
On 01/27/2012 08:36 PM, Andrei Alexandrescu wrote:
Here's a multikey sorting problem that's bothering me; I think it's well
researched but I can't find the right keywords.
Say we have a collection of people with height and hair length
information. We want
On Sat, 28 Jan 2012 06:36:49 +1100, Andrei Alexandrescu
seewebsiteforem...@erdani.org wrote:
Here's a multikey sorting problem that's bothering me; I think it's well
researched but I can't find the right keywords.
Say we have a collection of people with height and hair length
On 1/27/12 5:27 PM, Derek wrote:
On Sat, 28 Jan 2012 06:36:49 +1100, Andrei Alexandrescu
seewebsiteforem...@erdani.org wrote:
Here's a multikey sorting problem that's bothering me; I think it's
well researched but I can't find the right keywords.
Say we have a collection of people with height
The brute force approach would essentially compute the two ranks and
then sort by their sum. That's three sorts and at least one temporary
I think, you are mixing two problem levels:
Level one (theory):
How are the two properties weighted against each other
and can be combined to a total
On 1/27/12 5:35 PM, Christof Schardt wrote:
The brute force approach would essentially compute the two ranks and
then sort by their sum. That's three sorts and at least one temporary
I think, you are mixing two problem levels:
Level one (theory):
How are the two properties weighted against
On Friday, 27 January 2012 at 19:36:49 UTC, Andrei Alexandrescu
wrote:
Here's a multikey sorting problem that's bothering me; I think
it's well researched but I can't find the right keywords.
Say we have a collection of people with height and hair length
information. We want to get people who
A k-d tree isn't directly applicable here - the problem is that
the input data isn't normalized, so you can't just drop people
into a 2d grid consisting of one axis being height, and the other
axis being hair length. You need to 'normalize' the heights and
lengths into ranks first, *then*
On Fri, 27 Jan 2012 16:45:41 -0600, Andrei Alexandrescu
seewebsiteforem...@erdani.org wrote:
On 1/27/12 5:35 PM, Christof Schardt wrote:
The brute force approach would essentially compute the two ranks and
then sort by their sum. That's three sorts and at least one temporary
I think, you are
Andrei Alexandrescu wrote:
That's three sorts and at least one temporary array.
If a temporary array is allowed, the ranks and the sum of the ranks
might be computed by a diogonal sweep over the area defined by the two
dimensions and populated by the elements.
Population and sweep would each
On Friday, 27 January 2012 at 19:36:49 UTC, Andrei Alexandrescu
wrote:
The brute force approach would essentially compute the two
ranks and then sort by their sum. That's three sorts and at
least one temporary array. But I think things can be done
considerably better. Any ideas?
Can you
On 1/27/12 8:26 PM, Manfred Nowak wrote:
Andrei Alexandrescu wrote:
That's three sorts and at least one temporary array.
If a temporary array is allowed, the ranks and the sum of the ranks
might be computed by a diogonal sweep over the area defined by the two
dimensions and populated by the
On 1/27/12 8:33 PM, Peter Alexander wrote:
On Friday, 27 January 2012 at 19:36:49 UTC, Andrei Alexandrescu wrote:
The brute force approach would essentially compute the two ranks and
then sort by their sum. That's three sorts and at least one temporary
array. But I think things can be done
Andrei Alexandrescu wrote:
generally what one wants is a selection of best of breed stocks
that are among the top ones in a variety of categories. (Relative
importance could be assigned to each category.)
This is quite different and easier than the problem initially stated,
because ranks
Andrei Alexandrescu wrote:
Andrei Alexandrescu wrote:
generally what one wants is a selection of best of breed stocks
that are among the top ones in a variety of categories. (Relative
importance could be assigned to each category.)
This is quite different and easier than the problem
On Fri, Jan 27, 2012 at 09:22:26PM -0500, Andrei Alexandrescu wrote:
[...]
I wasn't thinking necessarily of the standard library, but it is
something that is often needed even if not perceived as such. For
example, the stock screeners offered by financial sites are crappy -
they allow you to
Andrei Alexandrescu wrote:
generally what one wants is a selection of best of breed stocks
that are among the top ones in a variety of categories. (Relative
importance could be assigned to each category.)
This is quite different and easier than the problem initially
stated, because ranks
On 10/8/2011 11:11 AM, Xinok wrote:
On 10/7/2011 12:42 PM, Xinok wrote:
Hi, it's been years since I've posted here. I just wanted to share
something I worked on, a new sorting algorithm. It's a variant of merge
sort, but much more memory efficient with only a small loss in
performance. The most
On 10/07/11 23:00, Xinok wrote:
Thanks, I'll look into it when I have a little more time.
Looking forward to it.
If my algorithm were to be implemented in Phobos, the template arguments
for std.algorithm.sort would need to be modified. For my algorithm to be
stable, it requires defining two
On 10/08/11 10:01, Xinok wrote:
On 10/8/2011 9:15 AM, Andrei Alexandrescu wrote:
On 10/07/11 23:00, Xinok wrote:
Thanks, I'll look into it when I have a little more time.
Looking forward to it.
If my algorithm were to be implemented in Phobos, the template arguments
for std.algorithm.sort
On 10/7/2011 12:42 PM, Xinok wrote:
Hi, it's been years since I've posted here. I just wanted to share
something I worked on, a new sorting algorithm. It's a variant of merge
sort, but much more memory efficient with only a small loss in
performance. The most similar algorithm I know
On 10/8/2011 11:04 AM, Andrei Alexandrescu wrote:
On 10/08/11 10:01, Xinok wrote:
On 10/8/2011 9:15 AM, Andrei Alexandrescu wrote:
On 10/07/11 23:00, Xinok wrote:
Thanks, I'll look into it when I have a little more time.
Looking forward to it.
If my algorithm were to be implemented in
On 10/8/11 10:36 AM, Xinok wrote:
On 10/8/2011 11:04 AM, Andrei Alexandrescu wrote:
On 10/08/11 10:01, Xinok wrote:
On 10/8/2011 9:15 AM, Andrei Alexandrescu wrote:
On 10/07/11 23:00, Xinok wrote:
Thanks, I'll look into it when I have a little more time.
Looking forward to it.
If my
On 10/8/11 10:11 AM, Xinok wrote:
On 10/7/2011 12:42 PM, Xinok wrote:
Hi, it's been years since I've posted here. I just wanted to share
something I worked on, a new sorting algorithm. It's a variant of merge
sort, but much more memory efficient with only a small loss in
performance. The most
On 10/8/2011 9:15 AM, Andrei Alexandrescu wrote:
On 10/07/11 23:00, Xinok wrote:
Thanks, I'll look into it when I have a little more time.
Looking forward to it.
If my algorithm were to be implemented in Phobos, the template arguments
for std.algorithm.sort would need to be modified. For my
On 10/8/2011 12:47 PM, Andrei Alexandrescu wrote:
Nice writeup, but I found it quite difficult to get into. What would
help is anchoring it with already known stuff (if it's not, the reader
must assume it's unrelated, which makes things difficult). So it would
be great if you compared and
On 10/8/11 12:30 PM, Xinok wrote:
On 10/8/2011 12:47 PM, Andrei Alexandrescu wrote:
Nice writeup, but I found it quite difficult to get into. What would
help is anchoring it with already known stuff (if it's not, the reader
must assume it's unrelated, which makes things difficult). So it would
On 10/8/2011 11:56 AM, Andrei Alexandrescu wrote:
I think I'm missing something. Again: if you have then =, ,
and = are zero cost.
What is more expensive is deciding a == b. You need to do it by saying
!(a b) !(b a). That's a cost worth paying because the second
expression is more general -
it'd be nice if there were some convenience templates somewhere for
converting a lt function to le,gt,ge, etc
On 10/08/2011 10:04 AM, Andrei Alexandrescu wrote:
I don't understand. Say all you have is . Then you can do everything:
a = b is !(b a)
a b is b a
On 10/8/2011 1:56 PM, Andrei Alexandrescu wrote:
On 10/8/11 12:30 PM, Xinok wrote:
I didn't mean for this text to be anything official. I just felt it was
important to provide an explanation of my algorithm so others could
better understand my algorithm and it's implications. That's all.
Hi, it's been years since I've posted here. I just wanted to share
something I worked on, a new sorting algorithm. It's a variant of merge
sort, but much more memory efficient with only a small loss in
performance. The most similar algorithm I know of is Timsort.
I had need for a stable
On 10/7/11 11:42 AM, Xinok wrote:
Hi, it's been years since I've posted here. I just wanted to share
something I worked on, a new sorting algorithm. It's a variant of merge
sort, but much more memory efficient with only a small loss in
performance. The most similar algorithm I know of is Timsort
On 10/7/2011 1:03 PM, Andrei Alexandrescu wrote:
On 10/7/11 11:42 AM, Xinok wrote:
Hi, it's been years since I've posted here. I just wanted to share
something I worked on, a new sorting algorithm. It's a variant of merge
sort, but much more memory efficient with only a small loss
On 10/7/11 12:23 PM, Xinok wrote:
http://www.neowin.net/forum/blog/422/entry-3737-sort-algorithm-complete/
This is interesting. What do the numbers in the benchmark represent?
Andrei
I'll just post the code I used for benchmarking. Simply put, smaller
numbers are faster.
[snip]
Thanks. It
tinkered with timsort a bit a few months ago. comparing that to your
sort, I get numbers like
xinokSort
random: 77 ascending: 0 descending: 21
timsort
random: 354 ascending: 1 descending: 4
where each are sorting a 500k element array of int, times are msecs,
compilation flags were -O
On 10/07/2011 01:20 PM, Andrei Alexandrescu wrote:
Also, which version of D are you using? I'm seeing that
std.algorithm.sort (introSort) performs quite badly; for example, it's
twice as slow on shuffled data against quickSort, and it also deals
badly with already sorted data. Generally it
On 10/7/2011 2:20 PM, Andrei Alexandrescu wrote:
On 10/7/11 12:23 PM, Xinok wrote:
http://www.neowin.net/forum/blog/422/entry-3737-sort-algorithm-complete/
This is interesting. What do the numbers in the benchmark represent?
Andrei
I'll just post the code I used for benchmarking. Simply
On 10/07/11 13:36, Ellery Newcomer wrote:
On 10/07/2011 01:20 PM, Andrei Alexandrescu wrote:
Also, which version of D are you using? I'm seeing that
std.algorithm.sort (introSort) performs quite badly; for example, it's
twice as slow on shuffled data against quickSort, and it also deals
badly
On 10/07/11 13:50, Xinok wrote:
On 10/7/2011 2:20 PM, Andrei Alexandrescu wrote:
On 10/7/11 12:23 PM, Xinok wrote:
http://www.neowin.net/forum/blog/422/entry-3737-sort-algorithm-complete/
This is interesting. What do the numbers in the benchmark represent?
Andrei
I'll just post the code
On 10/7/2011 2:27 PM, Ellery Newcomer wrote:
tinkered with timsort a bit a few months ago. comparing that to your
sort, I get numbers like
xinokSort
random: 77 ascending: 0 descending: 21
timsort
random: 354 ascending: 1 descending: 4
where each are sorting a 500k element array of
On 10/7/2011 5:08 PM, Andrei Alexandrescu wrote:
On 10/07/11 13:50, Xinok wrote:
On 10/7/2011 2:20 PM, Andrei Alexandrescu wrote:
On 10/7/11 12:23 PM, Xinok wrote:
http://www.neowin.net/forum/blog/422/entry-3737-sort-algorithm-complete/
This is interesting. What do the numbers in the
54 matches
Mail list logo
