Re: custom sorting of lists ?
On 2018-10-12 21:40, Codifies wrote: a while ago I wrote a doubly linked list (in C), which has a compare callback to allow custom sorting for example int cmpNodes(cnode_t* n1, cnode_t* n2) { mapNode_t* rn1 = (mapNode_t*)(n1->data); mapNode_t* rn2 = (mapNode_t*)(n2->data); if (rn1->G + rn1->H > rn2->G + rn2->H) return 1; return 0; } would be called by clistSort(openList, cmpNodes); The list would then be ordered by G + H fields (or any other algorithm you code) I notice there is a doubly linked list in the standard library, however it doesn't seem to allow for a custom compare, I'd rather not port my old C list code, can someone please give me some clues as to how I can reorder a list with a custom comparison...? I don't think you can sort a list because sorting requires random access, which a list doesn't provide. Is there a reason you cannot use an array? -- /Jacob Carlborg
Re: custom sorting of lists ?
On Saturday, 13 October 2018 at 07:48:04 UTC, Jacob Carlborg wrote: On 2018-10-12 21:40, Codifies wrote: a while ago I wrote a doubly linked list (in C), which has a compare callback to allow custom sorting for example int cmpNodes(cnode_t* n1, cnode_t* n2) { mapNode_t* rn1 = (mapNode_t*)(n1->data); mapNode_t* rn2 = (mapNode_t*)(n2->data); if (rn1->G + rn1->H > rn2->G + rn2->H) return 1; return 0; } would be called by clistSort(openList, cmpNodes); The list would then be ordered by G + H fields (or any other algorithm you code) I notice there is a doubly linked list in the standard library, however it doesn't seem to allow for a custom compare, I'd rather not port my old C list code, can someone please give me some clues as to how I can reorder a list with a custom comparison...? I don't think you can sort a list because sorting requires random access, which a list doesn't provide. Is there a reason you cannot use an array? it to port my old C pathfinding code, at the start of the path you don't know how long it will be and it need to grow and shrink depending on the obstacles and different potential paths it finds, using a list is just easier, I've ended up porting my C doubly linked list that has its own simple bubble sort...
ported a sortable list from my old C code
https://run.dlang.io/gist/b8b03ce3246951b5356db064ab68b22e its a bit fugly at the moment and I want to use something other than a void pointer (any?) (the whole thing was very pointer centric as everything was malloc'd...) I'm not entirely sure it would benefit from turning into a class ? Does anyone has any ideas on improving this sortable list
Re: ported a sortable list from my old C code
On Saturday, 13 October 2018 at 11:11:41 UTC, Codifies wrote: https://run.dlang.io/gist/b8b03ce3246951b5356db064ab68b22e its a bit fugly at the moment and I want to use something other than a void pointer (any?) (the whole thing was very pointer centric as everything was malloc'd...) I'm not entirely sure it would benefit from turning into a class ? Does anyone has any ideas on improving this sortable list Something is wrong with the link :(
Re: ported a sortable list from my old C code
On Saturday, 13 October 2018 at 11:11:41 UTC, Codifies wrote: Does anyone has any ideas on improving this sortable list Yes. Use an array. No, really, use an array. Now, really, use an array. If reallocations while building your paths become a problem, you can write a deque (bucket array) or a dlist. But still, afterwards just convert it to array and use that.
Re: ported a sortable list from my old C code
On Saturday, 13 October 2018 at 11:28:08 UTC, Alex wrote: On Saturday, 13 October 2018 at 11:11:41 UTC, Codifies wrote: https://run.dlang.io/gist/b8b03ce3246951b5356db064ab68b22e its a bit fugly at the moment and I want to use something other than a void pointer (any?) (the whole thing was very pointer centric as everything was malloc'd...) I'm not entirely sure it would benefit from turning into a class ? Does anyone has any ideas on improving this sortable list Something is wrong with the link :( gutted anywhere else I can post it?
Re: ported a sortable list from my old C code
On Saturday, 13 October 2018 at 11:28:08 UTC, Alex wrote: Something is wrong with the link :( https://dpaste.dzfl.pl/af9e6f6ce53e
Keeping a subset of pages allocate via a single call to mmap()
If a D-program GC-allocates via `new` an array spanning multiple pages but after processing only keeps a slice to it that fits inside a single `mmape`d page will GC-collection then free the other unreferenced pages? I realize that such a feature in a GC of any language and type must rely on the OS memory manager being able to free parts of a previously allocated set of continuously positioned pages. Does this depend on whether the used page is the first, last or a page in the middle of the set of pages allocated in one call to mmap.
Re: Keeping a subset of pages allocate via a single call to mmap()
On Saturday, 13 October 2018 at 18:40:58 UTC, Per Nordlöw wrote: If a D-program GC-allocates via `new` an array spanning multiple pages but after processing only keeps a slice to it that fits inside a single `mmape`d page will GC-collection then free the other unreferenced pages? I realize that such a feature in a GC of any language and type must rely on the OS memory manager being able to free parts of a previously allocated set of continuously positioned pages. Does this depend on whether the used page is the first, last or a page in the middle of the set of pages allocated in one call to mmap. I don't believe the GC frees half of allocated memory if there are no references to the unreferenced point. It would break c style strings I think.
Re: Keeping a subset of pages allocate via a single call to mmap()
On Saturday, 13 October 2018 at 18:40:58 UTC, Per Nordlöw wrote: If a D-program GC-allocates via `new` an array spanning multiple pages but after processing only keeps a slice to it that fits inside a single `mmape`d page will GC-collection then free the other unreferenced pages? IIRC GC never frees anything https://issues.dlang.org/show_bug.cgi?id=3284 was it fixed?
Re: custom sorting of lists ?
On 10/13/18 3:48 AM, Jacob Carlborg wrote: On 2018-10-12 21:40, Codifies wrote: a while ago I wrote a doubly linked list (in C), which has a compare callback to allow custom sorting for example int cmpNodes(cnode_t* n1, cnode_t* n2) { mapNode_t* rn1 = (mapNode_t*)(n1->data); mapNode_t* rn2 = (mapNode_t*)(n2->data); if (rn1->G + rn1->H > rn2->G + rn2->H) return 1; return 0; } would be called by clistSort(openList, cmpNodes); The list would then be ordered by G + H fields (or any other algorithm you code) I notice there is a doubly linked list in the standard library, however it doesn't seem to allow for a custom compare, I'd rather not port my old C list code, can someone please give me some clues as to how I can reorder a list with a custom comparison...? I don't think you can sort a list because sorting requires random access, which a list doesn't provide. Is there a reason you cannot use an array? You can't quick-sort a list. You can merge sort it, and it's O(nlgn). I'll work on getting a sort routine into Phobos for it, but I don't know what the appropriate location for it is, as a member or along-side std.algorithm.sort. -Steve
Re: ported a sortable list from my old C code
On 10/13/18 7:11 AM, Codifies wrote: https://run.dlang.io/gist/b8b03ce3246951b5356db064ab68b22e its a bit fugly at the moment and I want to use something other than a void pointer (any?) (the whole thing was very pointer centric as everything was malloc'd...) I'm not entirely sure it would benefit from turning into a class ? Does anyone has any ideas on improving this sortable list Yes, use mergesort instead of bubble sort. As I said, I will attempt to add sorting to Phobos for slist and dlist. -Steve
Re: custom sorting of lists ?
On Saturday, October 13, 2018 6:52:05 PM MDT Steven Schveighoffer via Digitalmars-d-learn wrote: > You can't quick-sort a list. You can merge sort it, and it's O(nlgn). > > I'll work on getting a sort routine into Phobos for it, but I don't know > what the appropriate location for it is, as a member or along-side > std.algorithm.sort. Unless there's something about the implementation that's tied to the list itself, I would think that it would make more sense to make it a generic algorithm, then it will work with any non-random-access range, and it avoids needing to reimplement it for similar circumstances. IMHO, it really only makes sense to tie it to the container if the implementation itself needs to be for some reason. - Jonathan M Davis
Re: std.regex is fat
On Friday, 12 October 2018 at 13:42:34 UTC, Alex wrote: On Friday, 12 October 2018 at 13:25:33 UTC, Chris Katko wrote: Like, insanely fat. All I wanted was a simple regex. The second include a regex function, my program would no longer compile "out of memory for fork". /usr/bin/time -v reports it went from 150MB of RAM for D, DAllegro, and Allegro5. To over 650MB of RAM, and from 1.5 seconds to >5.5 seconds to compile. Now I have to close all my Chrome tabs just to compile. Just for one line of regex. And I get it, it's the overhead of the library import, not the single line. But good gosh, more than 3X the RAM of the entire project for a single library import? Something doesn't add up! Hm... maybe, you run into this: https://forum.dlang.org/post/mailman.3091.1517866806.9493.digitalmar...@puremagic.com So wait, if their solution was to simply REMOVE std.regex from isEmail. That doesn't solve the regex problem at all. And from what I read in that thread, this penalty is paid per template INSTANTIATION which could explode. 1 - Does anyone know WHY it's so incredibly fat? 2 - If this isn't going to be fixed anytime soon, shouldn't there be a DISCLAIMER on the documentation? (+potential workarounds like keeping regex queries in their own file.) I mean, this kind of thing shouldn't require looking through forums. It's a clear bug, and if it's a WONTFIX (even temporarily), it should be documented clearly as such. If I'm running into this issue, how many other people already did, and possibly even gave up on using D?
Re: std.regex is fat
On Sunday, 14 October 2018 at 02:44:55 UTC, Chris Katko wrote: On Friday, 12 October 2018 at 13:42:34 UTC, Alex wrote: [...] So wait, if their solution was to simply REMOVE std.regex from isEmail. That doesn't solve the regex problem at all. And from what I read in that thread, this penalty is paid per template INSTANTIATION which could explode. [...] For comparison, I just tested and grep uses about 4 MB of RAM to run. So it's not the regex. It's the dmd / templates / CTFE, right?
Re: std.regex is fat
On Sunday, 14 October 2018 at 03:07:59 UTC, Chris Katko wrote: For comparison, I just tested and grep uses about 4 MB of RAM to run. Running and compiling are two entirely different things. Running the D regex code should be comparable, but compiling it is slow, in great part because of internal templates... There was an effort to speed up the template code, but it is still not complete.
Re: std.regex is fat
On Sunday, 14 October 2018 at 02:44:55 UTC, Chris Katko wrote: So wait, if their solution was to simply REMOVE std.regex from isEmail. That was ctRegex, which is different than regex. That doesn't solve the regex problem at all. And from what I read in that thread, this penalty is paid per template INSTANTIATION which could explode. Template instantiation, which is a big issue for ctRegex, but not for regular regex.