On 08/13/2019 10:33 AM, Mirjam Akkersdijk wrote:
> On Tuesday, 13 August 2019 at 14:04:45 UTC, Sebastiaan Koppe wrote:
>> Convert the nodes into an D array, sort the array with nodes.sort!"a.x
>> < b.x" and then iterate the array and repair the next/prev pointers.
If possible, I would go further and ditch the linked list altogether:
Just append the nodes to an array and then sort the array. It has been
shown in research, conference presentations, and in personal code to be
the fasted option is most (or all) cases.
> doesn't the nature of the dynamic array slow it down a bit?
Default bounds checking is going to cost a tiny bit, which you can turn
off after development with a compiler flag. (I still wouldn't.)
The only other option that would be faster is an array that's sitting on
the stack, created with alloca. But it's only for cases where the thread
will not run out of stack space and the result of the array is not going
to be used.
> can't I define an array of fixed size, which is dependent on the input
> of the function?
arr.length = number_of_elements;
All elements will be initialized to the element's default value, which
happens to be null for pointers. (If we are back to linked list Node
pointers.)
However, I wouldn't bother with setting length either as the cost of
automatic array resizing is amortized, meaning that it won't hurt the
O(1) algorithmic complexity in the general case. In the GC case that D
uses, it will be even better: because if the GC knowns that the
neighboring memory block is free, it will just add that to the dynamic
array's capacity without moving elements to the new location.
Summary: Ditch the linked list and put the elements into an array. :)
Ali
