How should I sort a doubly linked list the D way?
acehreli at yahoo.com
Wed Aug 14 10:13:28 UTC 2019
On 08/13/2019 03:12 PM, Mirjam Akkersdijk wrote:
> For the application I am writing, it makes very much sense to use a DLL.
Yes, Dynamically Linked Libraries can be useful. Oh wait... You mean
Doubly-Linked List. :o)
> I tried setting the length first and iterating through it with `nodes[i]
> = ...`
As Mike Parker said, it should be .reserve.
> and the implementation did not run noticeably faster (10 trials),
That's the most important part: You profiled and it was the same.
(Although, profiling is tricky business as well; it can be difficult to
measure the operation that you are interested in.)
The performance will depend on many factors:
* First, if there aren't many number of nodes it shouldn't matter.
(That's why I would choose the simpler arrays.)
* Doubly-linked list nodes will have two extra pointers per element. As
a general rule, larger the data slower the data structure.
* Pointer chasing through 'next' pointers will make the program jump
around in memory. This will be slower compared to consecutive elements
that arrays provide. But if processing the elements cause pointer
chasing anyway, then it shouldn't matter much. Another topic to read and
watch is "data oriented programming". This talk by Mike Acton is eye
* Is data appended and removed throughout the life of the program or are
the nodes set once in the beginning and then only used?
* Are elements accessed randomly or always in sequence. (If the latter,
modern CPUs promise that arrays will be better.)
More information about the Digitalmars-d-learn