digitalmars.D - New fast sorting algorithm (O(n))
- Nicholas Wilson (3/3) Jan 03 2017 https://probablydance.com/2016/12/27/i-wrote-a-faster-sorting-algorithm/
- ketmar (7/10) Jan 03 2017 ah, radix sort again, trading memory for speed. it is fairly easy
- ketmar (133/133) Jan 03 2017 just to show a usecase, some code, ripped out from one of my
- Andrei Alexandrescu (3/6) Jan 03 2017 In the reddit comments there's the one idea worth looking at:
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/
Jan 03 2017
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. it is fairly easy to beat standard sorts this way (and it is common to see variations of radix sort in game engines -- mine using that too, it is three times faster than phobos' algo). also, the idea of in-place byte-based radix sort is hardly new too. we've used it in demos at least two decades ago.
Jan 03 2017
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; OT[256] tails; // hi, Sonic! private: OT rsort(ubyte shift) (OT head) nothrow trusted nogc { heads[] = null; tails[] = null; while (head !is null) { immutable ubyte bucket = cast(ubyte)(head.sortkey>>shift); if (heads.ptr[bucket] is null) { heads.ptr[bucket] = tails.ptr[bucket] = head; } else { tails.ptr[bucket].next = head; tails.ptr[bucket] = head; } auto next = head.next; head.next = null; head = next; } OT res, cur; foreach (OT o; heads[]) { if (o !is null && res is null) { res = cur = o; o = o.next; } while (o !is null) { cur.next = o; cur = o; o = o.next; } } assert(cur !is null); cur.next = null; return res; } public: void sort (OT[] arr) nothrow trusted nogc { OT first, cur; foreach (OT o; arr) { if (first is null) { first = cur = o; } else { cur.next = o; cur = o; } } if (first is null) return; cur.next = null; first = rsort!0(first); first = rsort!8(first); first = rsort!16(first); first = rsort!24(first); size_t idx = 0; while (first !is null) { arr.ptr[idx++] = first; first = first.next; } } } class Entity { uint sortkey; Entity next; uint data; this () { import std.random : uniform; sortkey = uniform!"[]"(0, uint.max); data = uniform!"[]"(0, uint.max); } } import std.datetime; Entity[] objarr; Entity[] origarr; Entity[] srtarr; void genObjects () { objarr.length = ObjectCount; foreach (ref o; objarr) o = new Entity(); origarr.length = objarr.length; origarr[] = objarr[]; } void xtest () { // radix objarr[] = origarr[]; RadixSorter!Entity rs; rs.sort(objarr); srtarr.length = objarr.length; srtarr[] = objarr[]; // standard objarr[] = origarr[]; import std.algorithm : sort; objarr.sort!((Entity a, Entity b) => a.sortkey < b.sortkey); // check if our two sorts are identical foreach (immutable idx; 0..objarr.length) { if (objarr[idx] !is srtarr[idx]) assert(0, "wtf?!"); } } void check () { foreach (immutable idx, const o; objarr) { if (idx != 0) { if (objarr.ptr[idx-1].sortkey > o.sortkey) assert(0, "wtf!?"); } } } void testr () { objarr[] = origarr[]; RadixSorter!Entity rs; rs.sort(objarr); check(); } void testq () { objarr[] = origarr[]; import std.algorithm : sort; objarr.sort!((Entity a, Entity b) => a.sortkey < b.sortkey); check(); } void main () { import std.conv : to; genObjects(); xtest(); auto res = benchmark!(testr, testq)(10000); foreach (immutable idx; 0..res.length) { writeln(idx, ": ", res[idx].to!Duration.total!"msecs"); } } radix sort is ~8 times faster for 1000 objects here, and ~3 times faster for 10000 objects. of course, this can be optimized further by removing some clears and so on.
Jan 03 2017
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://github.com/orlp/pdqsort -- Andrei
Jan 03 2017