Re: How should I sort a doubly linked list the D way?

2019-08-14 Thread Patrick Schluter via Digitalmars-d-learn
On Tuesday, 13 August 2019 at 18:28:35 UTC, Ali Çehreli wrote: 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

Re: How should I sort a doubly linked list the D way?

2019-08-14 Thread Ali Çehreli via Digitalmars-d-learn
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]

Re: How should I sort a doubly linked list the D way?

2019-08-13 Thread Mike Parker via Digitalmars-d-learn
On Tuesday, 13 August 2019 at 22:12:23 UTC, Mirjam Akkersdijk wrote: Though, it left me with some semi-offtopic questions unanswered: (1) Ali, do you mean that from an optimization viewpoint, it's better to keep appending like `nodes ~= ...` instead of setting the length first? I would like

Re: How should I sort a doubly linked list the D way?

2019-08-13 Thread Mirjam Akkersdijk via Digitalmars-d-learn
On Tuesday, 13 August 2019 at 21:11:41 UTC, H. S. Teoh wrote: A contiguous allocator doesn't help after the list has undergone a large number of insertions/deletions, because of fragmentation. Fragmentation should not be an issue, I insist on keep using a DLL for the base structure in my

Re: How should I sort a doubly linked list the D way?

2019-08-13 Thread Mirjam Akkersdijk via Digitalmars-d-learn
On Tuesday, 13 August 2019 at 18:28:35 UTC, Ali Çehreli wrote: > 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

Re: How should I sort a doubly linked list the D way?

2019-08-13 Thread H. S. Teoh via Digitalmars-d-learn
On Tue, Aug 13, 2019 at 08:42:37PM +, Max Haughton via Digitalmars-d-learn wrote: > On Tuesday, 13 August 2019 at 18:54:58 UTC, H. S. Teoh wrote: [...] > > These days, with CPU multi-level caches and memory access > > predictors, in-place arrays are often the best option for > > performance,

Re: How should I sort a doubly linked list the D way?

2019-08-13 Thread Max Haughton via Digitalmars-d-learn
On Tuesday, 13 August 2019 at 18:54:58 UTC, H. S. Teoh wrote: On Tue, Aug 13, 2019 at 11:28:35AM -0700, Ali Çehreli via Digitalmars-d-learn wrote: [...] Summary: Ditch the linked list and put the elements into an array. :) [...] +1. The linked list may have been faster 20 years ago, before

Re: How should I sort a doubly linked list the D way?

2019-08-13 Thread Sebastiaan Koppe via Digitalmars-d-learn
On Tuesday, 13 August 2019 at 18:28:35 UTC, Ali Çehreli 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,

Re: How should I sort a doubly linked list the D way?

2019-08-13 Thread H. S. Teoh via Digitalmars-d-learn
On Tue, Aug 13, 2019 at 11:28:35AM -0700, Ali Çehreli via Digitalmars-d-learn wrote: [...] > Summary: Ditch the linked list and put the elements into an array. :) [...] +1. The linked list may have been faster 20 years ago, before the advent of modern CPUs with caching hierarchies and memory

Re: How should I sort a doubly linked list the D way?

2019-08-13 Thread Ali Çehreli via Digitalmars-d-learn
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

Re: How should I sort a doubly linked list the D way?

2019-08-13 Thread H. S. Teoh via Digitalmars-d-learn
On Tue, Aug 13, 2019 at 12:12:28PM -0600, Jonathan M Davis via Digitalmars-d-learn wrote: > On Tuesday, August 13, 2019 11:33:10 AM MDT Mirjam Akkersdijk via > Digitalmars-d-learn wrote: [...] > > Thank you, this is what I eventually chose to do. It's also fairly > > fast, though doesn't the

Re: How should I sort a doubly linked list the D way?

2019-08-13 Thread Johannes Loher via Digitalmars-d-learn
Am 13.08.19 um 11:48 schrieb Mirjam Akkersdijk: > Hello there, > If I had a DLL, how would I sort it judging by the node contents, the D > way? > > In C if I were to sort a piece of malloc'd memory pointing to node > pointers, I would write my compare function and let qsort sort it out. > In D, I

Re: How should I sort a doubly linked list the D way?

2019-08-13 Thread Jonathan M Davis via Digitalmars-d-learn
On Tuesday, August 13, 2019 11:33:10 AM MDT Mirjam Akkersdijk via Digitalmars-d-learn wrote: > On Tuesday, 13 August 2019 at 14:04:45 UTC, Sebastiaan Koppe > > wrote: > > On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk > > > > wrote: > >> and I would like to sort based on Node.t,

Re: How should I sort a doubly linked list the D way?

2019-08-13 Thread Mirjam Akkersdijk via Digitalmars-d-learn
On Tuesday, 13 August 2019 at 14:04:45 UTC, Sebastiaan Koppe wrote: On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk wrote: and I would like to sort based on Node.t, how should I tackle it, preferably without resorting to C libraries? Convert the nodes into an D array, sort the

Re: How should I sort a doubly linked list the D way?

2019-08-13 Thread Mirjam Akkersdijk via Digitalmars-d-learn
On Tuesday, 13 August 2019 at 12:34:46 UTC, bachmeier wrote: I'm confused by this statement. Are you referring to the qsort in C's stdlib? I had never heard of using that to sort a linked list, so I searched, and it is not possible. Ah yes, maybe I should have elaborated. In C, you can just

Re: How should I sort a doubly linked list the D way?

2019-08-13 Thread Sebastiaan Koppe via Digitalmars-d-learn
On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk wrote: and I would like to sort based on Node.t, how should I tackle it, preferably without resorting to C libraries? Convert the nodes into an D array, sort the array with nodes.sort!"a.x < b.x" and then iterate the array and

Re: How should I sort a doubly linked list the D way?

2019-08-13 Thread bachmeier via Digitalmars-d-learn
On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk wrote: I would write my compare function and let qsort sort it out. I'm confused by this statement. Are you referring to the qsort in C's stdlib? I had never heard of using that to sort a linked list, so I searched, and it is

Re: How should I sort a doubly linked list the D way?

2019-08-13 Thread ikod via Digitalmars-d-learn
On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk wrote: Hello there, If I had a DLL, how would I sort it judging by the node contents, the D way? In C if I were to sort a piece of malloc'd memory pointing to node pointers, I would write my compare function and let qsort sort it

Re: How should I sort a doubly linked list the D way?

2019-08-13 Thread Jonathan M Davis via Digitalmars-d-learn
On Tuesday, August 13, 2019 3:48:52 AM MDT Mirjam Akkersdijk via Digitalmars-d-learn wrote: > Hello there, > If I had a DLL, how would I sort it judging by the node contents, > the D way? > > In C if I were to sort a piece of malloc'd memory pointing to > node pointers, I would write my compare

Re: How should I sort a doubly linked list the D way?

2019-08-13 Thread Daniel Kozak via Digitalmars-d-learn
You can make an array from it On Tue, Aug 13, 2019 at 12:05 PM Mirjam Akkersdijk via Digitalmars-d-learn wrote: > > On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk > wrote: > > Hello there, > > If I had a DLL, how would I sort it judging by the node > > contents, the D way? > > > >

Re: How should I sort a doubly linked list the D way?

2019-08-13 Thread Mirjam Akkersdijk via Digitalmars-d-learn
On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk wrote: Hello there, If I had a DLL, how would I sort it judging by the node contents, the D way? [...] Node.t Node.x, my bad

How should I sort a doubly linked list the D way?

2019-08-13 Thread Mirjam Akkersdijk via Digitalmars-d-learn
Hello there, If I had a DLL, how would I sort it judging by the node contents, the D way? In C if I were to sort a piece of malloc'd memory pointing to node pointers, I would write my compare function and let qsort sort it out. In D, I tried to use std.algorithm's sort functionality to no