Re: Formatted date
On Thursday, November 03, 2011 16:58 Lishaak Bystroushaak wrote: > Hello. > > Is there any way how to format date with formating strings? Something > like strftime in python; > http://docs.python.org/library/datetime.html#strftime-and-strptime-behavior Not currently. SysTime (and the other time point types in std.datetime) have functions for converting them to specific ISO standards but not custom formatting strings. That's in the works but hasn't been completed yet. In the meantime, you can get a time_t from a SysTime using its unixTime property and pass that to C's strftime (though be warned that it risks being an hour off on Windows, since for some bizarre reason Windows applies DST to UTC such that time_t on Windows isn't actually guaranteed to always be the number of seconds since midnight January 1st, 1970 in UTC). Another alternative is that someone ported the deprecated std.dateparse (which worked with the deprecated and very broken std.date) to use SysTime, and you can use that: https://gist.github.com/1283011 toCustomString will be added to SysTime and the other time point types in std.datetime, but its design hasn't been completed sorted out yet, let alone fully implemented, so it's in the works, but it could be a little while before it makes it into Phobos. - Jonathan M Davis
Formatted date
Hello. Is there any way how to format date with formating strings? Something like strftime in python; http://docs.python.org/library/datetime.html#strftime-and-strptime-behavior
Re: std.container & ranges
On Thu, 03 Nov 2011 14:50:31 -0400, Timon Gehr wrote: On 11/03/2011 07:15 PM, Steven Schveighoffer wrote: I could use this idea, I think, to implement a singly linked list in dcollections as well (the prospect of not having O(1) removal is what has stopped me). Thanks for the idea! Nice! Looking at dcollections' List interface, the one thing I can't implement is back() (i.e. get the last element in the list). I can implement everything else. It might be worth it to make an exception for this (i.e. just throw if someone calls back()) in order to have a singly-linked list implementation. -Steve
Re: std.container & ranges
On Thu, 03 Nov 2011 17:13:55 -0400, Timon Gehr wrote: On 11/03/2011 09:46 PM, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 14:50:31 -0400, Timon Gehr wrote: On 11/03/2011 07:15 PM, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 13:47:28 -0400, Timon Gehr wrote: On 11/03/2011 06:13 PM, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 12:35:36 -0400, Dmitry Olshansky wrote: On 03.11.2011 19:34, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath wrote: Dmitry Olshansky wrote: And more importantly, it still would be horribly slow O(N^2). Personally, because of that I'd prefer hand-rolled intrusive singly-linked list any time of day. To be honest, I don't understand this. A "remove_if" for non-intrusive single-linked lists should be doable in O(N). Yeah, poor wording going to kill me one day :) And looking at how SList works with "checked" remove does O(N^2) turned out to be a context for reference for intrusive singly-linked list, just my bad. As for why I'd rather go with intrusive lists, it's because of it usually uses less memory due to node structures being more padding-free. Anyway the point should have been focused on _hand-rolled_ part, mostly because SList is plain not ready for prime time*. And btw singly-linked list it's not hard to implement and you can fine tune it how you like it e.g. they do play nice with free list allocation strategy. Not to say of circular lists and/or using sentinels. SList is a poor singly linked list implementation. It does not support O(1) removal. -Steve Aye, looking at SList implementation I can say that it sort of tries to verify that this is a correct list. Otherwise it would be O(1). Indeed passing wrong range/iterator is quite bad in linked lists and could lead to all manner of funky bugs, but the cost is horrific. Especially since insert doesn't do this extra check. No, it's necessarily doing O(n) search for current node because it has no reference to the previous node. The range type for a SList has a single pointer to the currently iterated node. How do you remove that node without having access to the head/previous pointer? The container interface does not expose references to the 'Node' struct, therefore the following approach would be practical: It does, actually. A range is a reference to a Node struct. But I still think the following approach will work. 0. Have a sentinel for end of list. (O(1) additional memory for the entire list). It is the only node in the list that has a null 'next' pointer. example, for removing just the current node: 1. if the following node is not the sentinel 1.1. Move value from following node into the current node. 1.2. Remove following node. 2. if the following node is the sentinel 2.1. erase the contents of the current node (iff it has indirections) 2.2. set it's 'next' field to null Removing an entire range is just erasing the contents of the current node and setting the 'next' field of the associated Node to zero. Removing a Take!Range is a simple generalization of the algorithm above. This would be a good addition to the type. It could not be a stableRemove, however, because it would invalidate any ranges pointing at the node you removed. Can you put together a pull request? I can do that, but it will have to wait a few days, as I am quite busy at the moment. No rush. I just wanted to know if you would do it, and if not, I would do it. If not, I can see about doing it. One issue, you could not do this if the value is immutable/const. That is true. But how to fix this? Resolving it by simply not exposing the remove method if it is impossible to implement the straightforward way would be an option, but I don't think that is satisfying. Probably it could be made to work by creating some kind of head mutable structure. I will think about it. It should even be possible to generalize std.typecons.Rebindable for structs to help this idea. Hm... rebindable doesn't help if the item is a struct. You'd have to store an allocated struct on the heap. -Steve My point is, if you have a struct like this: struct S{ const int* x; immutable int y; } Then that could be stored in the list as struct _S{ const(int)* x; int y; S getS(){return S(x,y);} } Without putting the type system under pressure. But on second thought, std.typecons.Rebindable can probably not meaningfully be generalized to structs because it could not deal with member functions. Yes, this looks like a viable solution. Not sure how it would be done in a generic way. I think what is best is to have getS be like this: S *getS(){ return cast(S*)&this;} And never provide access to this As long as S.opCmp, S.opEquals, and S.toHash are all const, this should be no issue (this needs to be a requirement). I wonder if we really have to go through such trouble... -Steve
Re: std.container & ranges
On 11/03/2011 09:46 PM, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 14:50:31 -0400, Timon Gehr wrote: On 11/03/2011 07:15 PM, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 13:47:28 -0400, Timon Gehr wrote: On 11/03/2011 06:13 PM, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 12:35:36 -0400, Dmitry Olshansky wrote: On 03.11.2011 19:34, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath wrote: Dmitry Olshansky wrote: And more importantly, it still would be horribly slow O(N^2). Personally, because of that I'd prefer hand-rolled intrusive singly-linked list any time of day. To be honest, I don't understand this. A "remove_if" for non-intrusive single-linked lists should be doable in O(N). Yeah, poor wording going to kill me one day :) And looking at how SList works with "checked" remove does O(N^2) turned out to be a context for reference for intrusive singly-linked list, just my bad. As for why I'd rather go with intrusive lists, it's because of it usually uses less memory due to node structures being more padding-free. Anyway the point should have been focused on _hand-rolled_ part, mostly because SList is plain not ready for prime time*. And btw singly-linked list it's not hard to implement and you can fine tune it how you like it e.g. they do play nice with free list allocation strategy. Not to say of circular lists and/or using sentinels. SList is a poor singly linked list implementation. It does not support O(1) removal. -Steve Aye, looking at SList implementation I can say that it sort of tries to verify that this is a correct list. Otherwise it would be O(1). Indeed passing wrong range/iterator is quite bad in linked lists and could lead to all manner of funky bugs, but the cost is horrific. Especially since insert doesn't do this extra check. No, it's necessarily doing O(n) search for current node because it has no reference to the previous node. The range type for a SList has a single pointer to the currently iterated node. How do you remove that node without having access to the head/previous pointer? The container interface does not expose references to the 'Node' struct, therefore the following approach would be practical: It does, actually. A range is a reference to a Node struct. But I still think the following approach will work. 0. Have a sentinel for end of list. (O(1) additional memory for the entire list). It is the only node in the list that has a null 'next' pointer. example, for removing just the current node: 1. if the following node is not the sentinel 1.1. Move value from following node into the current node. 1.2. Remove following node. 2. if the following node is the sentinel 2.1. erase the contents of the current node (iff it has indirections) 2.2. set it's 'next' field to null Removing an entire range is just erasing the contents of the current node and setting the 'next' field of the associated Node to zero. Removing a Take!Range is a simple generalization of the algorithm above. This would be a good addition to the type. It could not be a stableRemove, however, because it would invalidate any ranges pointing at the node you removed. Can you put together a pull request? I can do that, but it will have to wait a few days, as I am quite busy at the moment. No rush. I just wanted to know if you would do it, and if not, I would do it. If not, I can see about doing it. One issue, you could not do this if the value is immutable/const. That is true. But how to fix this? Resolving it by simply not exposing the remove method if it is impossible to implement the straightforward way would be an option, but I don't think that is satisfying. Probably it could be made to work by creating some kind of head mutable structure. I will think about it. It should even be possible to generalize std.typecons.Rebindable for structs to help this idea. Hm... rebindable doesn't help if the item is a struct. You'd have to store an allocated struct on the heap. -Steve My point is, if you have a struct like this: struct S{ const int* x; immutable int y; } Then that could be stored in the list as struct _S{ const(int)* x; int y; S getS(){return S(x,y);} } Without putting the type system under pressure. But on second thought, std.typecons.Rebindable can probably not meaningfully be generalized to structs because it could not deal with member functions.
Re: std.container & ranges
On Thu, 03 Nov 2011 16:27:46 -0400, Dmitry Olshansky wrote: On 03.11.2011 22:37, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 14:08:31 -0400, Dmitry Olshansky wrote: On 03.11.2011 21:13, Steven Schveighoffer wrote: dcollections stipulates that all ranges/cursors can be verified in O(lgn) time or better to belong to a specific container. In some cases, this adds an extra word to the range/cursor, and in others, it's easy to determine or the owner-reference was already needed. Since everything is a class, the fallback is to just stick an owner class instance in the range. This stipulation is necessary to allow safe slicing. Seems reasonable, I'd expect checks to go away in release, right(?). For the moment, no. I am not sure whether this is the right decision or not, because once you get beyond arrays, when to do bounds checks becomes fuzzy. For example, imagine you have this: auto ts = new TreeSet!int(1, 3, 5, 7, 9); What does this mean? auto r = ts[2..4]; Note that a range type for a treeset has a pointer to a begin and end node for the container. For arrays, not doing a bounds check is simply less code. For a RBTree, you still have to look for the specific node, even if you are in release mode. Another example: auto ts2 = ts.dup; // duplicate the treeset auto c1 = ts2.elemAt(3); // get the node for 3 in ts2 auto r2 = ts[c1..ts.end]; hm-h will that actually work? I mean searching in ts for node from ts2? c1 is a cursor, so there is no need to search for it (the point of a cursor is to keep a reference to an element for later use). All you have to do is verify it's in the container (and the ordering is valid). If unchecked, it will result in likely a segfault, because the two endpoints are not connected. Here I can say, we can skip the belongs check (which is an O(lgn) walk up the tree). Well, I was mostly talking about this kind of scenario i.e. skip checking that cursor do belong to this collection. While in ts[2..4] example there is no (explicit) cursors so it's a different situation. So what should happen? Should it throw? But I'm still doing it in release mode. I'm not sure what's best. Should I just do the least work possible, or should I make it consistent with ts[2..4]? I'd say release mode should avoid as much extra work as possible while keeping primary functionality intact, but that's just me. Yes, it's a dilemma that I'm not sure what the right answer is. It does make sense that release mode should just avoid the checks altogether. -Steve
Re: std.container & ranges
On Thu, 03 Nov 2011 14:50:31 -0400, Timon Gehr wrote: On 11/03/2011 07:15 PM, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 13:47:28 -0400, Timon Gehr wrote: On 11/03/2011 06:13 PM, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 12:35:36 -0400, Dmitry Olshansky wrote: On 03.11.2011 19:34, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath wrote: Dmitry Olshansky wrote: And more importantly, it still would be horribly slow O(N^2). Personally, because of that I'd prefer hand-rolled intrusive singly-linked list any time of day. To be honest, I don't understand this. A "remove_if" for non-intrusive single-linked lists should be doable in O(N). Yeah, poor wording going to kill me one day :) And looking at how SList works with "checked" remove does O(N^2) turned out to be a context for reference for intrusive singly-linked list, just my bad. As for why I'd rather go with intrusive lists, it's because of it usually uses less memory due to node structures being more padding-free. Anyway the point should have been focused on _hand-rolled_ part, mostly because SList is plain not ready for prime time*. And btw singly-linked list it's not hard to implement and you can fine tune it how you like it e.g. they do play nice with free list allocation strategy. Not to say of circular lists and/or using sentinels. SList is a poor singly linked list implementation. It does not support O(1) removal. -Steve Aye, looking at SList implementation I can say that it sort of tries to verify that this is a correct list. Otherwise it would be O(1). Indeed passing wrong range/iterator is quite bad in linked lists and could lead to all manner of funky bugs, but the cost is horrific. Especially since insert doesn't do this extra check. No, it's necessarily doing O(n) search for current node because it has no reference to the previous node. The range type for a SList has a single pointer to the currently iterated node. How do you remove that node without having access to the head/previous pointer? The container interface does not expose references to the 'Node' struct, therefore the following approach would be practical: It does, actually. A range is a reference to a Node struct. But I still think the following approach will work. 0. Have a sentinel for end of list. (O(1) additional memory for the entire list). It is the only node in the list that has a null 'next' pointer. example, for removing just the current node: 1. if the following node is not the sentinel 1.1. Move value from following node into the current node. 1.2. Remove following node. 2. if the following node is the sentinel 2.1. erase the contents of the current node (iff it has indirections) 2.2. set it's 'next' field to null Removing an entire range is just erasing the contents of the current node and setting the 'next' field of the associated Node to zero. Removing a Take!Range is a simple generalization of the algorithm above. This would be a good addition to the type. It could not be a stableRemove, however, because it would invalidate any ranges pointing at the node you removed. Can you put together a pull request? I can do that, but it will have to wait a few days, as I am quite busy at the moment. No rush. I just wanted to know if you would do it, and if not, I would do it. If not, I can see about doing it. One issue, you could not do this if the value is immutable/const. That is true. But how to fix this? Resolving it by simply not exposing the remove method if it is impossible to implement the straightforward way would be an option, but I don't think that is satisfying. Probably it could be made to work by creating some kind of head mutable structure. I will think about it. It should even be possible to generalize std.typecons.Rebindable for structs to help this idea. Hm... rebindable doesn't help if the item is a struct. You'd have to store an allocated struct on the heap. -Steve
Re: std.container & ranges
On 03.11.2011 22:37, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 14:08:31 -0400, Dmitry Olshansky wrote: On 03.11.2011 21:13, Steven Schveighoffer wrote: dcollections stipulates that all ranges/cursors can be verified in O(lgn) time or better to belong to a specific container. In some cases, this adds an extra word to the range/cursor, and in others, it's easy to determine or the owner-reference was already needed. Since everything is a class, the fallback is to just stick an owner class instance in the range. This stipulation is necessary to allow safe slicing. Seems reasonable, I'd expect checks to go away in release, right(?). For the moment, no. I am not sure whether this is the right decision or not, because once you get beyond arrays, when to do bounds checks becomes fuzzy. For example, imagine you have this: auto ts = new TreeSet!int(1, 3, 5, 7, 9); What does this mean? auto r = ts[2..4]; Note that a range type for a treeset has a pointer to a begin and end node for the container. For arrays, not doing a bounds check is simply less code. For a RBTree, you still have to look for the specific node, even if you are in release mode. Another example: auto ts2 = ts.dup; // duplicate the treeset auto c1 = ts2.elemAt(3); // get the node for 3 in ts2 auto r2 = ts[c1..ts.end]; hm-h will that actually work? I mean searching in ts for node from ts2? Here I can say, we can skip the belongs check (which is an O(lgn) walk up the tree). Well, I was mostly talking about this kind of scenario i.e. skip checking that cursor do belong to this collection. While in ts[2..4] example there is no (explicit) cursors so it's a different situation. But I'm still doing it in release mode. I'm not sure what's best. Should I just do the least work possible, or should I make it consistent with ts[2..4]? I'd say release mode should avoid as much extra work as possible while keeping primary functionality intact, but that's just me. -- Dmitry Olshansky
Re: std.container & ranges
On 11/03/2011 07:15 PM, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 13:47:28 -0400, Timon Gehr wrote: On 11/03/2011 06:13 PM, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 12:35:36 -0400, Dmitry Olshansky wrote: On 03.11.2011 19:34, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath wrote: Dmitry Olshansky wrote: And more importantly, it still would be horribly slow O(N^2). Personally, because of that I'd prefer hand-rolled intrusive singly-linked list any time of day. To be honest, I don't understand this. A "remove_if" for non-intrusive single-linked lists should be doable in O(N). Yeah, poor wording going to kill me one day :) And looking at how SList works with "checked" remove does O(N^2) turned out to be a context for reference for intrusive singly-linked list, just my bad. As for why I'd rather go with intrusive lists, it's because of it usually uses less memory due to node structures being more padding-free. Anyway the point should have been focused on _hand-rolled_ part, mostly because SList is plain not ready for prime time*. And btw singly-linked list it's not hard to implement and you can fine tune it how you like it e.g. they do play nice with free list allocation strategy. Not to say of circular lists and/or using sentinels. SList is a poor singly linked list implementation. It does not support O(1) removal. -Steve Aye, looking at SList implementation I can say that it sort of tries to verify that this is a correct list. Otherwise it would be O(1). Indeed passing wrong range/iterator is quite bad in linked lists and could lead to all manner of funky bugs, but the cost is horrific. Especially since insert doesn't do this extra check. No, it's necessarily doing O(n) search for current node because it has no reference to the previous node. The range type for a SList has a single pointer to the currently iterated node. How do you remove that node without having access to the head/previous pointer? The container interface does not expose references to the 'Node' struct, therefore the following approach would be practical: It does, actually. A range is a reference to a Node struct. But I still think the following approach will work. 0. Have a sentinel for end of list. (O(1) additional memory for the entire list). It is the only node in the list that has a null 'next' pointer. example, for removing just the current node: 1. if the following node is not the sentinel 1.1. Move value from following node into the current node. 1.2. Remove following node. 2. if the following node is the sentinel 2.1. erase the contents of the current node (iff it has indirections) 2.2. set it's 'next' field to null Removing an entire range is just erasing the contents of the current node and setting the 'next' field of the associated Node to zero. Removing a Take!Range is a simple generalization of the algorithm above. This would be a good addition to the type. It could not be a stableRemove, however, because it would invalidate any ranges pointing at the node you removed. Can you put together a pull request? I can do that, but it will have to wait a few days, as I am quite busy at the moment. If not, I can see about doing it. One issue, you could not do this if the value is immutable/const. That is true. But how to fix this? Resolving it by simply not exposing the remove method if it is impossible to implement the straightforward way would be an option, but I don't think that is satisfying. Probably it could be made to work by creating some kind of head mutable structure. I will think about it. It should even be possible to generalize std.typecons.Rebindable for structs to help this idea. I could use this idea, I think, to implement a singly linked list in dcollections as well (the prospect of not having O(1) removal is what has stopped me). Thanks for the idea! Nice!
Re: std.container & ranges
On Thu, 03 Nov 2011 22:08:31 +0400, Dmitry Olshansky wrote: > On 03.11.2011 21:13, Steven Schveighoffer wrote: >> The range type for a SList has a single pointer to the currently >> iterated node. How do you remove that node without having access to the >> head/previous pointer? >> >> > removeAfter ? ;) Hm though it does hit as strange. Looking at my code, I > usually keep previous node but only when I remove elements during > iteration. Matt Austern's excellent "STL Singly Linked Lists" presentation is relevant: http://accu.org/index.php/accu_branches/accu_usa/past Slide 11 is titled "Solving the insert problem: off-by-one iterators". Also slide 16. Ali
Re: std.container & ranges
On Thu, 03 Nov 2011 14:08:31 -0400, Dmitry Olshansky wrote: On 03.11.2011 21:13, Steven Schveighoffer wrote: dcollections stipulates that all ranges/cursors can be verified in O(lgn) time or better to belong to a specific container. In some cases, this adds an extra word to the range/cursor, and in others, it's easy to determine or the owner-reference was already needed. Since everything is a class, the fallback is to just stick an owner class instance in the range. This stipulation is necessary to allow safe slicing. Seems reasonable, I'd expect checks to go away in release, right(?). For the moment, no. I am not sure whether this is the right decision or not, because once you get beyond arrays, when to do bounds checks becomes fuzzy. For example, imagine you have this: auto ts = new TreeSet!int(1, 3, 5, 7, 9); What does this mean? auto r = ts[2..4]; Note that a range type for a treeset has a pointer to a begin and end node for the container. For arrays, not doing a bounds check is simply less code. For a RBTree, you still have to look for the specific node, even if you are in release mode. Another example: auto ts2 = ts.dup; // duplicate the treeset auto c1 = ts2.elemAt(3); // get the node for 3 in ts2 auto r2 = ts[c1..ts.end]; Here I can say, we can skip the belongs check (which is an O(lgn) walk up the tree). But I'm still doing it in release mode. I'm not sure what's best. Should I just do the least work possible, or should I make it consistent with ts[2..4]? -Steve
Re: std.container & ranges
On Thu, 03 Nov 2011 13:47:28 -0400, Timon Gehr wrote: On 11/03/2011 06:13 PM, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 12:35:36 -0400, Dmitry Olshansky wrote: On 03.11.2011 19:34, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath wrote: Dmitry Olshansky wrote: And more importantly, it still would be horribly slow O(N^2). Personally, because of that I'd prefer hand-rolled intrusive singly-linked list any time of day. To be honest, I don't understand this. A "remove_if" for non-intrusive single-linked lists should be doable in O(N). Yeah, poor wording going to kill me one day :) And looking at how SList works with "checked" remove does O(N^2) turned out to be a context for reference for intrusive singly-linked list, just my bad. As for why I'd rather go with intrusive lists, it's because of it usually uses less memory due to node structures being more padding-free. Anyway the point should have been focused on _hand-rolled_ part, mostly because SList is plain not ready for prime time*. And btw singly-linked list it's not hard to implement and you can fine tune it how you like it e.g. they do play nice with free list allocation strategy. Not to say of circular lists and/or using sentinels. SList is a poor singly linked list implementation. It does not support O(1) removal. -Steve Aye, looking at SList implementation I can say that it sort of tries to verify that this is a correct list. Otherwise it would be O(1). Indeed passing wrong range/iterator is quite bad in linked lists and could lead to all manner of funky bugs, but the cost is horrific. Especially since insert doesn't do this extra check. No, it's necessarily doing O(n) search for current node because it has no reference to the previous node. The range type for a SList has a single pointer to the currently iterated node. How do you remove that node without having access to the head/previous pointer? The container interface does not expose references to the 'Node' struct, therefore the following approach would be practical: It does, actually. A range is a reference to a Node struct. But I still think the following approach will work. 0. Have a sentinel for end of list. (O(1) additional memory for the entire list). It is the only node in the list that has a null 'next' pointer. example, for removing just the current node: 1. if the following node is not the sentinel 1.1. Move value from following node into the current node. 1.2. Remove following node. 2. if the following node is the sentinel 2.1. erase the contents of the current node (iff it has indirections) 2.2. set it's 'next' field to null Removing an entire range is just erasing the contents of the current node and setting the 'next' field of the associated Node to zero. Removing a Take!Range is a simple generalization of the algorithm above. This would be a good addition to the type. It could not be a stableRemove, however, because it would invalidate any ranges pointing at the node you removed. Can you put together a pull request? If not, I can see about doing it. One issue, you could not do this if the value is immutable/const. I could use this idea, I think, to implement a singly linked list in dcollections as well (the prospect of not having O(1) removal is what has stopped me). Thanks for the idea! -Steve
Re: std.container & ranges
On 03.11.2011 21:13, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 12:35:36 -0400, Dmitry Olshansky wrote: On 03.11.2011 19:34, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath wrote: Dmitry Olshansky wrote: And more importantly, it still would be horribly slow O(N^2). Personally, because of that I'd prefer hand-rolled intrusive singly-linked list any time of day. To be honest, I don't understand this. A "remove_if" for non-intrusive single-linked lists should be doable in O(N). Yeah, poor wording going to kill me one day :) And looking at how SList works with "checked" remove does O(N^2) turned out to be a context for reference for intrusive singly-linked list, just my bad. As for why I'd rather go with intrusive lists, it's because of it usually uses less memory due to node structures being more padding-free. Anyway the point should have been focused on _hand-rolled_ part, mostly because SList is plain not ready for prime time*. And btw singly-linked list it's not hard to implement and you can fine tune it how you like it e.g. they do play nice with free list allocation strategy. Not to say of circular lists and/or using sentinels. SList is a poor singly linked list implementation. It does not support O(1) removal. -Steve Aye, looking at SList implementation I can say that it sort of tries to verify that this is a correct list. Otherwise it would be O(1). Indeed passing wrong range/iterator is quite bad in linked lists and could lead to all manner of funky bugs, but the cost is horrific. Especially since insert doesn't do this extra check. No, it's necessarily doing O(n) search for current node because it has no reference to the previous node. The range type for a SList has a single pointer to the currently iterated node. How do you remove that node without having access to the head/previous pointer? removeAfter ? ;) Hm though it does hit as strange. Looking at my code, I usually keep previous node but only when I remove elements during iteration. I suggested to Andrei having the range keep track of the *previous* node/head, but he did not like that idea (too many dereferences for front()). Another option is to have a removeAllButFirst method, but that's kind of awkward... And then using a sentinel as in Timon's idea doesn't look half bad. Actually, it opens up a question of "Checked ranges" akin to "Checked iterators" used in many STL implementations. Any ideas what they can carry around as an "ID" of list? Root pointer won't cut it, as it can be easily removed during iteration. If SList was a class it's reference probably would do. dcollections stipulates that all ranges/cursors can be verified in O(lgn) time or better to belong to a specific container. In some cases, this adds an extra word to the range/cursor, and in others, it's easy to determine or the owner-reference was already needed. Since everything is a class, the fallback is to just stick an owner class instance in the range. This stipulation is necessary to allow safe slicing. Seems reasonable, I'd expect checks to go away in release, right(?). -- Dmitry Olshansky
Re: std.container & ranges
On 11/03/2011 06:13 PM, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 12:35:36 -0400, Dmitry Olshansky wrote: On 03.11.2011 19:34, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath wrote: Dmitry Olshansky wrote: And more importantly, it still would be horribly slow O(N^2). Personally, because of that I'd prefer hand-rolled intrusive singly-linked list any time of day. To be honest, I don't understand this. A "remove_if" for non-intrusive single-linked lists should be doable in O(N). Yeah, poor wording going to kill me one day :) And looking at how SList works with "checked" remove does O(N^2) turned out to be a context for reference for intrusive singly-linked list, just my bad. As for why I'd rather go with intrusive lists, it's because of it usually uses less memory due to node structures being more padding-free. Anyway the point should have been focused on _hand-rolled_ part, mostly because SList is plain not ready for prime time*. And btw singly-linked list it's not hard to implement and you can fine tune it how you like it e.g. they do play nice with free list allocation strategy. Not to say of circular lists and/or using sentinels. SList is a poor singly linked list implementation. It does not support O(1) removal. -Steve Aye, looking at SList implementation I can say that it sort of tries to verify that this is a correct list. Otherwise it would be O(1). Indeed passing wrong range/iterator is quite bad in linked lists and could lead to all manner of funky bugs, but the cost is horrific. Especially since insert doesn't do this extra check. No, it's necessarily doing O(n) search for current node because it has no reference to the previous node. The range type for a SList has a single pointer to the currently iterated node. How do you remove that node without having access to the head/previous pointer? The container interface does not expose references to the 'Node' struct, therefore the following approach would be practical: 0. Have a sentinel for end of list. (O(1) additional memory for the entire list). It is the only node in the list that has a null 'next' pointer. example, for removing just the current node: 1. if the following node is not the sentinel 1.1. Move value from following node into the current node. 1.2. Remove following node. 2. if the following node is the sentinel 2.1. erase the contents of the current node (iff it has indirections) 2.2. set it's 'next' field to null Removing an entire range is just erasing the contents of the current node and setting the 'next' field of the associated Node to zero. Removing a Take!Range is a simple generalization of the algorithm above.
Re: Double implicitly converted to real
Charles McAnany Wrote: > I noticed that one of the guarantees in TDPL is that any code that is valid > in both C > and D should compile with the same result. This is almost true (there are few differences, in D fixed-size arrays are managed by value instead of by pointer, and global floating point variables are initialized to NaN instead of 0), but only where all C compilers themselves give the same results. Floating point operations are based on a standard implementation, but I think in practice different optimizations cause different C compilers to not give exactly the same result when floating point values are used (even the same CPU gives different results if you use the FP stack with 80 bit reals or if you use 64 bit doubles in SSE registers). So small differences are expected. Your program is designed to blow up those small differences. > It seems D is implicitly converting double to real. Is this the usual > behavior? DMD compiler sometimes uses real values for intermediate values, so such differences are not so unexpected. Bye, bearophile
Re: std.container & ranges
On Thu, 03 Nov 2011 12:32:06 -0400, Christophe wrote: "Steven Schveighoffer" , dans le message (digitalmars.D.learn:30402), a The primitive for a container is remove(range). Ranges are essential to containers, and should be the major interface to them. Programmers have to learn ranges to use containers. Hiding ranges is not helping them. But here, it is more complicated than that, because range may be more powerful than iterators, they are less friendly to use when a single element reference has to be used. c.remove(find(c.all, E)); will not remove the first occurence of E, but all elements beyond E. so instead we have to write: c.remove(take(find(c[], E), 1)); Then it's too much. The problem is that range are not practical to refer to a single element in the container. We need to have single-element reference to manipulate the range. Then a function should be used to find such one-element reference. std.find is already taken, and can hardly be changed (although it should be name popUntil), but we can still use a find method of the container. auto r = take(find(c[], E), 1); should just be written: auto r = c.find(E); Then the syntax to remove a single element from c is acceptable: c.remove(c.find(E)). Now let us remove several consecutive elements from c, let us say, all elements between the value E and the next value F: | auto r = find(c[], E); | int i=0; | foreach(e, r) | if (e == F) break; | else ++i; | c.remove(take(r, i+1)); That is not practical at all, and in addition, it is not efficient, since r is walked again from E to F. If we add little methods to single element reference to make them behave a little like iterators, we can recreate ranges from two single element references, and regain all the power of iterators. To remove all elements from E to the next F included: auto r = c.find( E); c.remove(r, r.find(F)++); // or c.remove(range(r, r.find(F)++)); (I use the find method a bit like a joker in this exemple, it is just to get the idea). In conclusion, to refer to a single element of a container for simple operations, range looses against iterator. Ranges even loose to refer to a range of consecutive elements... Many alternatives are possible, but a simple iterator structure to refer to a single element, and that you can combine to recreate a range (and use all range algorithms) would be enough, and would complete the range interface to make them have no drawback against iterators. Preaching to the choir sir :) http://www.dsource.org/projects/dcollections/browser/branches/d2/concepts.txt If you can convince Andrei that cursors are a good addition to std.container, you have my admiration. I've tried and failed quite a few times. To illustrate syntax: auto cursor = c.elemAt(E); c.remove(c[cursor..c.end]); // note, $ could be used here, but opDollar is broken. Note, this only works if c supports elemAt. For example, TreeSet supports this, LinkList does not. But dcollections supports even other slicing abilities. For example TreeSet can do this too: c.remove(c[E..F]); If you have a container that doesn't support elemAt, you can use std.algorithm.find, and the dcollections' range.begin method to get a valid cursor: auto cursor = find(c[], E).begin; I realize this isn't much better than take(find(c[], E), 1), but I don't know if you realize what a task/chore it would be to create a simple shortcut in a class for std.algorithm.find. -Steve
Re: std.container & ranges
On Thu, 03 Nov 2011 12:35:36 -0400, Dmitry Olshansky wrote: On 03.11.2011 19:34, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath wrote: Dmitry Olshansky wrote: And more importantly, it still would be horribly slow O(N^2). Personally, because of that I'd prefer hand-rolled intrusive singly-linked list any time of day. To be honest, I don't understand this. A "remove_if" for non-intrusive single-linked lists should be doable in O(N). Yeah, poor wording going to kill me one day :) And looking at how SList works with "checked" remove does O(N^2) turned out to be a context for reference for intrusive singly-linked list, just my bad. As for why I'd rather go with intrusive lists, it's because of it usually uses less memory due to node structures being more padding-free. Anyway the point should have been focused on _hand-rolled_ part, mostly because SList is plain not ready for prime time*. And btw singly-linked list it's not hard to implement and you can fine tune it how you like it e.g. they do play nice with free list allocation strategy. Not to say of circular lists and/or using sentinels. SList is a poor singly linked list implementation. It does not support O(1) removal. -Steve Aye, looking at SList implementation I can say that it sort of tries to verify that this is a correct list. Otherwise it would be O(1). Indeed passing wrong range/iterator is quite bad in linked lists and could lead to all manner of funky bugs, but the cost is horrific. Especially since insert doesn't do this extra check. No, it's necessarily doing O(n) search for current node because it has no reference to the previous node. The range type for a SList has a single pointer to the currently iterated node. How do you remove that node without having access to the head/previous pointer? I suggested to Andrei having the range keep track of the *previous* node/head, but he did not like that idea (too many dereferences for front()). Another option is to have a removeAllButFirst method, but that's kind of awkward... Actually, it opens up a question of "Checked ranges" akin to "Checked iterators" used in many STL implementations. Any ideas what they can carry around as an "ID" of list? Root pointer won't cut it, as it can be easily removed during iteration. If SList was a class it's reference probably would do. dcollections stipulates that all ranges/cursors can be verified in O(lgn) time or better to belong to a specific container. In some cases, this adds an extra word to the range/cursor, and in others, it's easy to determine or the owner-reference was already needed. Since everything is a class, the fallback is to just stick an owner class instance in the range. This stipulation is necessary to allow safe slicing. -Steve
Re: std.container & ranges
On 03.11.2011 19:34, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath wrote: Dmitry Olshansky wrote: And more importantly, it still would be horribly slow O(N^2). Personally, because of that I'd prefer hand-rolled intrusive singly-linked list any time of day. To be honest, I don't understand this. A "remove_if" for non-intrusive single-linked lists should be doable in O(N). Yeah, poor wording going to kill me one day :) And looking at how SList works with "checked" remove does O(N^2) turned out to be a context for reference for intrusive singly-linked list, just my bad. As for why I'd rather go with intrusive lists, it's because of it usually uses less memory due to node structures being more padding-free. Anyway the point should have been focused on _hand-rolled_ part, mostly because SList is plain not ready for prime time*. And btw singly-linked list it's not hard to implement and you can fine tune it how you like it e.g. they do play nice with free list allocation strategy. Not to say of circular lists and/or using sentinels. SList is a poor singly linked list implementation. It does not support O(1) removal. -Steve Aye, looking at SList implementation I can say that it sort of tries to verify that this is a correct list. Otherwise it would be O(1). Indeed passing wrong range/iterator is quite bad in linked lists and could lead to all manner of funky bugs, but the cost is horrific. Especially since insert doesn't do this extra check. Actually, it opens up a question of "Checked ranges" akin to "Checked iterators" used in many STL implementations. Any ideas what they can carry around as an "ID" of list? Root pointer won't cut it, as it can be easily removed during iteration. If SList was a class it's reference probably would do. * I think I'll scrap together a pull request to address both these issues though. -- Dmitry Olshansky
Re: std.container & ranges
"Steven Schveighoffer" , dans le message (digitalmars.D.learn:30402), a > The primitive for a container is remove(range). Ranges are essential to > containers, and should be the major interface to them. Programmers have to learn ranges to use containers. Hiding ranges is not helping them. But here, it is more complicated than that, because range may be more powerful than iterators, they are less friendly to use when a single element reference has to be used. c.remove(find(c.all, E)); will not remove the first occurence of E, but all elements beyond E. so instead we have to write: c.remove(take(find(c[], E), 1)); Then it's too much. The problem is that range are not practical to refer to a single element in the container. We need to have single-element reference to manipulate the range. Then a function should be used to find such one-element reference. std.find is already taken, and can hardly be changed (although it should be name popUntil), but we can still use a find method of the container. auto r = take(find(c[], E), 1); should just be written: auto r = c.find(E); Then the syntax to remove a single element from c is acceptable: c.remove(c.find(E)). Now let us remove several consecutive elements from c, let us say, all elements between the value E and the next value F: | auto r = find(c[], E); | int i=0; | foreach(e, r) | if (e == F) break; | else ++i; | c.remove(take(r, i+1)); That is not practical at all, and in addition, it is not efficient, since r is walked again from E to F. If we add little methods to single element reference to make them behave a little like iterators, we can recreate ranges from two single element references, and regain all the power of iterators. To remove all elements from E to the next F included: auto r = c.find( E); c.remove(r, r.find(F)++); // or c.remove(range(r, r.find(F)++)); (I use the find method a bit like a joker in this exemple, it is just to get the idea). In conclusion, to refer to a single element of a container for simple operations, range looses against iterator. Ranges even loose to refer to a range of consecutive elements... Many alternatives are possible, but a simple iterator structure to refer to a single element, and that you can combine to recreate a range (and use all range algorithms) would be enough, and would complete the range interface to make them have no drawback against iterators.
Re: [beginner] Why nothing is printed to stdout ?
Nick Sabalausky Wrote: > > Seems like ./ tries to fix some sort of Namespace Pollution Hell when > > virtually every installed program ends up in path. > > It's also a safety/security matter. Imagine: > > $ cat ./ls > #!/bin/sh > rm ~ -rf > > Gee, let's see what's inside this directory...WTF? God dammit!! > > Windows generally gets away without such problems because even the power > users usually stick to the GUI for most stuff, and also because extensive > shell scripting is generally avoided. It's ok to have a limited set of "keyword-class" tools in global namespace, but not every installed program. For example, on windows you don't have firefox or git or dmd in path (by default). You don't run dmd in arbitrary directory just to see what it will do.
Re: Double implicitly converted to real
Le 03/11/2011 15:39, Charles McAnany a écrit : Hi. I noticed that one of the guarantees in TDPL is that any code that is valid in both C and D should compile with the same result. But I'm seeing a different behavior here. I'm trying to find the smallest double for which the comparison x+1/x = x is true. I take a number way too small, and a number way too large, and then binary search (for 100 iterations) to get the desired number: //add appropriate import std.stdio or #include int main(){ double min = 1; double max = 100; int iters = 0; double average; for(;iters<100; iters++){ average = (min+max)/2; if( average + 1/average == average) max = average; else min = average; } printf("%f",average); return 0; } Here's the problem: D (under DMD v2.051) gives this answer: 4294967296.00 C (gcc version 3.4.6 20060404): 134217728.00 It seems D is implicitly converting double to real. Is this the usual behavior? Cheers, Charles. As long as you don't loose information, you can cast implicitely in D. If you loose information (or the compiler cannot prove that your are not loosing information) then an explicit cast is required. So this implicit cast is expected. Now, you are not using real in your code, so you shouldn't use real anywhere. Are you sure this is the actual issue ? Finally, both compiler you are using are rather old ones. dmd is in version 2.056 now and gdc has 4.6.2 version (and using 2.055 frontend).
Re: std.container & ranges
On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath wrote: Dmitry Olshansky wrote: And more importantly, it still would be horribly slow O(N^2). Personally, because of that I'd prefer hand-rolled intrusive singly-linked list any time of day. To be honest, I don't understand this. A "remove_if" for non-intrusive single-linked lists should be doable in O(N). SList is a poor singly linked list implementation. It does not support O(1) removal. -Steve
Re: std.container & ranges
On Wed, 02 Nov 2011 19:24:03 -0400, Max Wolter wrote: On 11/2/2011 2:41 PM, Steven Schveighoffer wrote: I never said you couldn't (and I've even given examples of such implementations). It's just not neatly packaged into a method. But again, if the method is exactly the same as the efficient version for other containers, it becomes *impossible* to design an algorithm that guarantees any sort of complexity. As I said before, quadratic sort is epic fail, and needs to always be avoided. I'll give you a scenario: People often complain that Linked List does not have an opIndex on it. Yes it's inefficient, but so what? "I know it's inefficient, let me decide whether it's worth it or not." So let's say I add it to LinkList. Those people are happy. But now, LinkList becomes defined as a *random-access-range* according to std.ranges. Therefore, std.algorithm.sort(linklist) compiles! And is now something like O(n^3). Whereas LinkList already defines a sort method, which uses mergesort (O(nlgn)). So are you going to realize this when reading someones code and you see: sort(somelist); That it's going to be horribly inefficient? Why shouldn't we strive for a library where such things just don't compile? Hello. You generally arguing this is all nice and good, but this is a very specific case. I am using a LinkList because in my code, the elements are iterated over a million times and during this, I add stuff in-between elements all the time. However, I will be removing stuff *very* rarely. I am thus using the appropriate container and it doesn't matter whether the remove will be inefficient. A linked list (any list really) is important if you want to maintain insertion order. If that's not important, don't use a list, a hash or tree is about as efficient. There exist (not in D) hybrid container types that allow O(1) removal using value, and maintain insertion order. In fact, the actual remove is not inefficient if you have a reference to an element (not just the value). Unfortunately, for SList, this is not the case, but it should be fixed at some point. But I still maintain, anything in std.container is not just a container for your code, it's a container that tries to cater to the most common needs. If you want a remove(value) function, it is trivial to write. To put it another way: if removing elements was of crucial importance to the performance of my code in the first place, I wouldn't (and shouldn't) be using a LinkList. As long as you don't need to search for the element to remove using its value, removal in a linked list should be O(1). A linked list that does not allow O(1) removal and O(1) insertion given a topological reference is a failure (yes, that includes the current version of SList). Therefore, implementing an inefficient method which does this won't be of consequence. Finally, the fundamental statement I'm trying to make here is: adding and removing *single* elements should be a straightforward method call for *any* container. Adding, yes. Removing a container-selected element, yes. Removing a *specific* element, no. Inserting an element in a *specific location*, no. std.container has taken the stance that primitives should reflect the efficiency of the operation. This is not the only valid position to have. It's just std.container's position. For example, Java allows this. As a side note, your example about generic programming is really neat and makes sense; personally, I would never want a linked list with indexes and it's also a horrible analogy to the complaint at hand. People have asked for it and argued vigorously for it on this newsgroup, just as you are arguing for this. -Steve
Re: std.container & ranges
On Thu, 03 Nov 2011 03:41:27 -0400, Mike Parker wrote: On 11/2/2011 10:41 PM, Steven Schveighoffer wrote: Then your specific application can use std.algorithm.find to implement the equivalent. Only the algorithm body changes, not the usage of the algorithm. This is the root of the problem. How are we supposed to know that we need something from std.algorithm to remove something from a container in std.container? It's non-intuitive and non-obvious unless you already have more than a passing familiarity with ranges. If we can't have remove(element) on a container, then we need some good documentation in the std.container module that points the way. The primitive for a container is remove(range). Ranges are essential to containers, and should be the major interface to them. remove(value) translates to remove(findRangeFor(value)). I'm asserting that we should not promote this "shortcut" if it's unavoidably linear in nature, otherwise, remove(value) has the stigma of being slow, even for containers which can do it quickly. It's not the only choice, and there are ways to argue both sides. But the fact that one can still do this using std.algorithm makes it at least so you can have the best of both worlds -- it's difficult to do, not impossible, but we can still develop generic code with complexity guarantees. I agree the documentation needs more care. I think std.container suffers from neglect in other areas too. I argued this position, however, because even though it's not spelled out in std.container's docs, it *is* the position std.container is taking. -Steve
Double implicitly converted to real
Hi. I noticed that one of the guarantees in TDPL is that any code that is valid in both C and D should compile with the same result. But I'm seeing a different behavior here. I'm trying to find the smallest double for which the comparison x+1/x = x is true. I take a number way too small, and a number way too large, and then binary search (for 100 iterations) to get the desired number: //add appropriate import std.stdio or #include int main(){ double min = 1; double max = 100; int iters = 0; double average; for(;iters<100; iters++){ average = (min+max)/2; if( average + 1/average == average) max = average; else min = average; } printf("%f",average); return 0; } Here's the problem: D (under DMD v2.051) gives this answer: 4294967296.00 C (gcc version 3.4.6 20060404): 134217728.00 It seems D is implicitly converting double to real. Is this the usual behavior? Cheers, Charles.
Re: std.container & ranges
Dmitry Olshansky wrote: > And more importantly, it still would be horribly slow O(N^2). > Personally, because of that I'd prefer hand-rolled intrusive > singly-linked list any time of day. > To be honest, I don't understand this. A "remove_if" for non-intrusive single-linked lists should be doable in O(N). I still think the interface to container lacks a important feature here.
Re: std.container & ranges
On 2011-11-03 08:41, Mike Parker wrote: On 11/2/2011 10:41 PM, Steven Schveighoffer wrote: Then your specific application can use std.algorithm.find to implement the equivalent. Only the algorithm body changes, not the usage of the algorithm. This is the root of the problem. How are we supposed to know that we need something from std.algorithm to remove something from a container in std.container? It's non-intuitive and non-obvious unless you already have more than a passing familiarity with ranges. If we can't have remove(element) on a container, then we need some good documentation in the std.container module that points the way. What about having a remove method on a container that calls remove in std.algorithm, just as a convenience. -- /Jacob Carlborg
Re: std.container & ranges
On Thursday, November 03, 2011 16:41:27 Mike Parker wrote: > On 11/2/2011 10:41 PM, Steven Schveighoffer wrote: > > Then your specific application can use std.algorithm.find to implement > > the equivalent. Only the algorithm body changes, not the usage of the > > algorithm. > > This is the root of the problem. How are we supposed to know that we > need something from std.algorithm to remove something from a container > in std.container? It's non-intuitive and non-obvious unless you already > have more than a passing familiarity with ranges. If we can't have > remove(element) on a container, then we need some good documentation in > the std.container module that points the way. It's quite clear that we need to do a better job getting the concept of ranges across (probably with at least one explanatory article) and that std.container's documentation needs improvement. - Jonathan M Davis
Re: std.container & ranges
On 11/2/2011 10:41 PM, Steven Schveighoffer wrote: Then your specific application can use std.algorithm.find to implement the equivalent. Only the algorithm body changes, not the usage of the algorithm. This is the root of the problem. How are we supposed to know that we need something from std.algorithm to remove something from a container in std.container? It's non-intuitive and non-obvious unless you already have more than a passing familiarity with ranges. If we can't have remove(element) on a container, then we need some good documentation in the std.container module that points the way.
Re: how to use curl to download a file
On 11/2/2011 9:43 PM, Ary Manzana wrote: On 11/1/11 11:49 PM, Mike Parker wrote: On 11/2/2011 3:20 AM, Frédéric Galusik wrote: Hi, As the curl documentation is a little bit ...wow. http://www.digitalmars.com/d/2.0/phobos/etc_c_curl.html Do someone have a simple example on how to download a simple file ? Thank you. ++ I don't think we should expect detailed documentation for modules in etc.c. These are interfaces to existing C libraries, not Phobos-specific modules. There's no need to duplicate existing documentation. If you want to learn how to use libcurl, the place to look is the libcurl homepage. http://curl.haxx.se/libcurl/ Wrong. If you want programmers to use D, give them the solution, now. It's a D binding to a C library. The interface is the same. It's not that hard to put a little example at the top of the page showing a basic usage. Wrappers over these libraries should be documented, sure. But for the C interface, IMO, a link to the project homepage is sufficient. Any differences on the D side should be mentioned, of course. But that's all. Otherwise, how many examples should be given? Which functionality should be shown? libcurl, specifically, has several examples already available from the project page. Adding more to the D docs is redundant.