Re: std.container ranges
Am 02.11.2011, 12:48 Uhr, schrieb Steven Schveighoffer
schvei...@yahoo.com:
In dcollections, removing a specific element (using the default
comparison operator for that element) on a *fast lookup* container is as
simple as:
container.remove(container.find(x));
Which removes the element x if it's found. However, this is not defined
for containers which use O(n) time to search (such as linked list), you
must use std.algorithm.find for that:
container.remove(find(container[], x).begin);
Should work, and takes O(n) time.
-Steve
While I stumble over this. I found that I sometimes need a certain
container (data structure/algorithm), but with an additional fast removal
or lookup. So I returned a handle (a pointer or array index) for any
inserted element that you can store (in the element itself for example)
and use for lookup/removal. Templates bake the correct struct for this:
// The element I want to store
struct Element {
// ... actual data
size_t handle; // a pointer to a node in disguise, returned from
insert(...)
}
// A collection node
struct Node {
Element e;
Node* prev;
Node* next;
}
// Usage
elem.handle = list.insert(elem);
list.remove(elem.handle);
Now you have a double-linked list with O(1) removal, as long as you keep
the handle around. The limitation is, that the handle has to remain
constant. So a binary heap with the elements embedded in an array and no
indirection through a pointer would not work. As soon as elements are
reorganized, their handle (array index in this case) becomes invalid.
But the point is, that you can reduce the time complexity for removal in
every data structure like this in an implementation agnostic way (unless
plain array of elements) and I think it is better than Java's approach
that just works, but may result in an O(n) lookup operation.
Iterators with remove functionality overlap with this partially. (They
don't need an extra handle stored somewhere, but generally go over the
complete list.)
Re: std.container ranges
On Sat, 05 Nov 2011 17:28:34 -0400, Marco Leise marco.le...@gmx.de wrote:
Am 02.11.2011, 12:48 Uhr, schrieb Steven Schveighoffer
schvei...@yahoo.com:
In dcollections, removing a specific element (using the default
comparison operator for that element) on a *fast lookup* container is
as simple as:
container.remove(container.find(x));
Which removes the element x if it's found. However, this is not
defined for containers which use O(n) time to search (such as linked
list), you must use std.algorithm.find for that:
container.remove(find(container[], x).begin);
Should work, and takes O(n) time.
-Steve
While I stumble over this. I found that I sometimes need a certain
container (data structure/algorithm), but with an additional fast
removal or lookup. So I returned a handle (a pointer or array index)
for any inserted element that you can store (in the element itself for
example) and use for lookup/removal. Templates bake the correct struct
for this:
// The element I want to store
struct Element {
// ... actual data
size_t handle; // a pointer to a node in disguise, returned from
insert(...)
}
// A collection node
struct Node {
Element e;
Node* prev;
Node* next;
}
// Usage
elem.handle = list.insert(elem);
list.remove(elem.handle);
You should be able to do this with dcollections:
struct Element(T) {
T data;
List!T.cursor handle;
}
elem.handle = list.insert(list.end, elem.data); // x is the value being
inserted
list.remove(elem.handle); // removes the element you inserted earlier.
Note, you have to specify an insertion point (this is similar to C++).
But note that you can't exactly create a handle to a list of the Element
type, because you need that cursor type to define Element.
Now you have a double-linked list with O(1) removal, as long as you keep
the handle around. The limitation is, that the handle has to remain
constant. So a binary heap with the elements embedded in an array and no
indirection through a pointer would not work. As soon as elements are
reorganized, their handle (array index in this case) becomes invalid.
But the point is, that you can reduce the time complexity for removal in
every data structure like this in an implementation agnostic way (unless
plain array of elements) and I think it is better than Java's approach
that just works, but may result in an O(n) lookup operation.
Iterators with remove functionality overlap with this partially. (They
don't need an extra handle stored somewhere, but generally go over the
complete list.)
Definitely. This is the benefit of iterators/cursors. The ability to
refer to exactly one element makes things much more straightforward. It's
why dcollections has cursors.
-Steve
Re: std.container ranges
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). Well, thank god that's cleared up. Time to move on. /Max
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: 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 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
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 Thu, 03 Nov 2011 03:41:27 -0400, Mike Parker aldac...@gmail.com 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
Re: std.container ranges
On Wed, 02 Nov 2011 19:24:03 -0400, Max Wolter awishform...@gmail.com 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
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: std.container ranges
On 03.11.2011 19:34, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath tob...@pankrath.net 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
On Thu, 03 Nov 2011 12:35:36 -0400, Dmitry Olshansky dmitry.o...@gmail.com wrote: On 03.11.2011 19:34, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath tob...@pankrath.net 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 Thu, 03 Nov 2011 12:32:06 -0400, Christophe trav...@phare.normalesup.org 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 11/03/2011 06:13 PM, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 12:35:36 -0400, Dmitry Olshansky dmitry.o...@gmail.com wrote: On 03.11.2011 19:34, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath tob...@pankrath.net 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: std.container ranges
On 03.11.2011 21:13, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 12:35:36 -0400, Dmitry Olshansky dmitry.o...@gmail.com wrote: On 03.11.2011 19:34, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath tob...@pankrath.net 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 Thu, 03 Nov 2011 13:47:28 -0400, Timon Gehr timon.g...@gmx.ch wrote: On 11/03/2011 06:13 PM, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 12:35:36 -0400, Dmitry Olshansky dmitry.o...@gmail.com wrote: On 03.11.2011 19:34, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath tob...@pankrath.net 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 Thu, 03 Nov 2011 14:08:31 -0400, Dmitry Olshansky dmitry.o...@gmail.com 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 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 11/03/2011 07:15 PM, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 13:47:28 -0400, Timon Gehr timon.g...@gmx.ch wrote: On 11/03/2011 06:13 PM, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 12:35:36 -0400, Dmitry Olshansky dmitry.o...@gmail.com wrote: On 03.11.2011 19:34, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath tob...@pankrath.net 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 03.11.2011 22:37, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 14:08:31 -0400, Dmitry Olshansky dmitry.o...@gmail.com 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 Thu, 03 Nov 2011 14:50:31 -0400, Timon Gehr timon.g...@gmx.ch wrote: On 11/03/2011 07:15 PM, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 13:47:28 -0400, Timon Gehr timon.g...@gmx.ch wrote: On 11/03/2011 06:13 PM, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 12:35:36 -0400, Dmitry Olshansky dmitry.o...@gmail.com wrote: On 03.11.2011 19:34, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath tob...@pankrath.net 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 Thu, 03 Nov 2011 16:27:46 -0400, Dmitry Olshansky dmitry.o...@gmail.com wrote: On 03.11.2011 22:37, Steven Schveighoffer wrote: On Thu, 03 Nov 2011 14:08:31 -0400, Dmitry Olshansky dmitry.o...@gmail.com 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 11/03/2011 09:46 PM, Steven Schveighoffer wrote:
On Thu, 03 Nov 2011 14:50:31 -0400, Timon Gehr timon.g...@gmx.ch wrote:
On 11/03/2011 07:15 PM, Steven Schveighoffer wrote:
On Thu, 03 Nov 2011 13:47:28 -0400, Timon Gehr timon.g...@gmx.ch
wrote:
On 11/03/2011 06:13 PM, Steven Schveighoffer wrote:
On Thu, 03 Nov 2011 12:35:36 -0400, Dmitry Olshansky
dmitry.o...@gmail.com wrote:
On 03.11.2011 19:34, Steven Schveighoffer wrote:
On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath
tob...@pankrath.net 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 17:13:55 -0400, Timon Gehr timon.g...@gmx.ch wrote:
On 11/03/2011 09:46 PM, Steven Schveighoffer wrote:
On Thu, 03 Nov 2011 14:50:31 -0400, Timon Gehr timon.g...@gmx.ch
wrote:
On 11/03/2011 07:15 PM, Steven Schveighoffer wrote:
On Thu, 03 Nov 2011 13:47:28 -0400, Timon Gehr timon.g...@gmx.ch
wrote:
On 11/03/2011 06:13 PM, Steven Schveighoffer wrote:
On Thu, 03 Nov 2011 12:35:36 -0400, Dmitry Olshansky
dmitry.o...@gmail.com wrote:
On 03.11.2011 19:34, Steven Schveighoffer wrote:
On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath
tob...@pankrath.net 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
Re: std.container ranges
On Thu, 03 Nov 2011 14:50:31 -0400, Timon Gehr timon.g...@gmx.ch 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
Kagamin , dans le message (digitalmars.D.learn:30362), a écrit : Steven Schveighoffer Wrote: ahem, using dcollections: foreach(ref doRemove, cell; organism.purge) doRemove = cell.x == x cell.y == y; complexity: O(n) may be a generic iteration handler would be more useful? foreach(ref handler, cell; organism.each) if(cell.x == x cell.y == y) handler.removeCurrent(); it could provide a whole api, say, you may want to have lookahead foreach(ref handler, cell; organism.each) if(cell.x == x cell.y == y handler.next.x==0) handler.removeCurrent(); That's not easier than using Tobias' improved foreach: foreach(cell, cellRange; organism[]) if (cell.x == x cell.y == y) organism.remove(cellRange); If you want to use algorithm specialized and optimized for the container, I would prefer to use purge than each + handler. purge seems better to me, because it can be specialized for the container and for the action, and do not require to learn a new handler structure. each do not seem to add a lot to foreach(cell, cellRange; range), since it must be able to cope with any operation provided by handler, and any operation combinaisons...
Re: std.container ranges
On Tue, 01 Nov 2011 16:53:26 -0400, Max Wolter awishform...@gmail.com
wrote:
On 10/30/2011 9:28 PM, Jonathan M Davis wrote:
On Sunday, October 30, 2011 20:53:02 Max Wolter wrote:
Hello there.
Thank you very much for the explanation.
However, while I really liked the concept of ranges in Andrei's book
and
a lot of it seems intuitive and faster than using iterators, I can't
shake the feeling that in this case, it's just unnecessarily
convoluted.
Maybe it's just the fact that the container library is still very
basic,
but I don't think I should go through such a complicated procedure to
remove an known element from a list. It's just not a very simple or
intuitive solution, which is something I came to love D for thus far.
You would be doing exactly the same thing in C++ except that it would
be with
an iterator rather than a range. You would use find to find the
iterator to the
element that you wanted and then you'd pass that to the list's erase
function.
It is only more complicated in D in that you get a range which _starts_
with
the element that you want (essentially, you get the iterator to that
element
plus the end iterator for the list), so if you want to remove only the
first
element, you take it from the front of the range. Other than that, it's
the
same as in C++. You can't remove an element from a list in C++ by
giving that
element to the list anymore than you can in D. In both cases, you need
an
iterator or a range.
So, in comparison to C++, there's no significant difference. Now, Java
does have
a remove function which will take an element and remove the first
occurence of
that element from a list, and we could theoretically add one, but why?
It
would just be duplicating the functionality that find already gives.
Java
doesn't use iterators the way the C++ does, and it doesn't have ranges,
so it
_can't_ have a find function the way that C++ and D do, but D can. And
in some
cases, find can do it more efficiently than your loop could have.
I grant you that if you're not used to using find like this in C++ (and
far,
far too many C++ programmers use loops instead of find - in part
because pre-
C++11, there were no lambdas and any time you need a custom comparison
function, it's a pain to get one), then it's not immediately intuitive,
but
it's far more flexible and powerful than removing elements by giving the
element to a remove function on the list. And if you really want to use
a
loop, then you still can. You just can't use foreach.
for(auto r = organism[]; !r.empty; r.popFront())
{
if(r.front.x == x r.front.y == y)
{
organism.stableLinearRemove(take(r, 1));
break;
}
}
but that's a lot more verbose than simply using find, and as I said, in
at
least some cases, find can be more efficient than simply looping, since
it's
optimized for finding elements.
- Jonathan M Davis
Hello again.
I've read all further replies in this thread, but it seems to me this is
the most appropriate place to respond.
Simply put, all of those options are too verbose. If what you want to do
is simple, the syntax should also be simple, this is what I love about
D. As a side-note, I don't come from Java, but I still expect a
container to be able to remove an element by passing it to a method. The
verbosity and the details of this operation should be hidden in the
implementation of the method and I shouldn't need to know about the
details. Otherwise, I could just as well implement my own container.
The basic response to this is, when dealing with containers generically
(that is, you know you have a container, but you don't know what type),
the remove this element operation is not necessarily a good primitive to
have.
Simply because from the myriad of containers, only some can implement this
operation efficiently. Java embeds this operation in the interface, which
means any interface you have to a container could potentially use O(n)
time to remove that element. Such an innocuous piece of syntax *should*
have a cost if it's not efficient IMO.
BTW, the original question doesn't provide enough information to say
remove this element. Even in Java, if you aren't using the default
comparison, you must use a comparator method to determine which one to
remove. If cell.x == x cell.y == y *is* the comparison operator for
the type, then the syntax gets much simpler, because you don't need to
pass a specialized comparison function.
In dcollections, removing a specific element (using the default comparison
operator for that element) on a *fast lookup* container is as simple as:
container.remove(container.find(x));
Which removes the element x if it's found. However, this is not defined
for containers which use O(n) time to search (such as linked list), you
must use std.algorithm.find for that:
container.remove(find(container[], x).begin);
Should work, and takes O(n) time.
Re: std.container ranges
On Nov 2, 2011, at 12:48 PM, Steven Schveighoffer wrote: Hello again. I've read all further replies in this thread, but it seems to me this is the most appropriate place to respond. Simply put, all of those options are too verbose. If what you want to do is simple, the syntax should also be simple, this is what I love about D. As a side-note, I don't come from Java, but I still expect a container to be able to remove an element by passing it to a method. The verbosity and the details of this operation should be hidden in the implementation of the method and I shouldn't need to know about the details. Otherwise, I could just as well implement my own container. The basic response to this is, when dealing with containers generically (that is, you know you have a container, but you don't know what type), the remove this element operation is not necessarily a good primitive to have. Simply because from the myriad of containers, only some can implement this operation efficiently. Java embeds this operation in the interface, which means any interface you have to a container could potentially use O(n) time to remove that element. Such an innocuous piece of syntax *should* have a cost if it's not efficient IMO. BTW, the original question doesn't provide enough information to say remove this element. Even in Java, if you aren't using the default comparison, you must use a comparator method to determine which one to remove. If cell.x == x cell.y == y *is* the comparison operator for the type, then the syntax gets much simpler, because you don't need to pass a specialized comparison function. In dcollections, removing a specific element (using the default comparison operator for that element) on a *fast lookup* container is as simple as: container.remove(container.find(x)); Which removes the element x if it's found. However, this is not defined for containers which use O(n) time to search (such as linked list), you must use std.algorithm.find for that: container.remove(find(container[], x).begin); Should work, and takes O(n) time. -Steve I can't really understand what is wrong with an inefficient remove this element primitive if it's really what the user had to do... Once it's in the documentation that the operation is inefficient, why the user must be forced to dig into the newsgroup to find out some code? Why can't that be furnished in a free function, for example? Cheers, Paolo
Re: std.container ranges
On 11/2/11 8:48 AM, Steven Schveighoffer wrote:
On Tue, 01 Nov 2011 16:53:26 -0400, Max Wolter awishform...@gmail.com
wrote:
On 10/30/2011 9:28 PM, Jonathan M Davis wrote:
On Sunday, October 30, 2011 20:53:02 Max Wolter wrote:
Hello there.
Thank you very much for the explanation.
However, while I really liked the concept of ranges in Andrei's book
and
a lot of it seems intuitive and faster than using iterators, I can't
shake the feeling that in this case, it's just unnecessarily
convoluted.
Maybe it's just the fact that the container library is still very
basic,
but I don't think I should go through such a complicated procedure to
remove an known element from a list. It's just not a very simple or
intuitive solution, which is something I came to love D for thus far.
You would be doing exactly the same thing in C++ except that it would
be with
an iterator rather than a range. You would use find to find the
iterator to the
element that you wanted and then you'd pass that to the list's erase
function.
It is only more complicated in D in that you get a range which
_starts_ with
the element that you want (essentially, you get the iterator to that
element
plus the end iterator for the list), so if you want to remove only
the first
element, you take it from the front of the range. Other than that,
it's the
same as in C++. You can't remove an element from a list in C++ by
giving that
element to the list anymore than you can in D. In both cases, you
need an
iterator or a range.
So, in comparison to C++, there's no significant difference. Now,
Java does have
a remove function which will take an element and remove the first
occurence of
that element from a list, and we could theoretically add one, but
why? It
would just be duplicating the functionality that find already gives.
Java
doesn't use iterators the way the C++ does, and it doesn't have
ranges, so it
_can't_ have a find function the way that C++ and D do, but D can.
And in some
cases, find can do it more efficiently than your loop could have.
I grant you that if you're not used to using find like this in C++
(and far,
far too many C++ programmers use loops instead of find - in part
because pre-
C++11, there were no lambdas and any time you need a custom comparison
function, it's a pain to get one), then it's not immediately
intuitive, but
it's far more flexible and powerful than removing elements by giving the
element to a remove function on the list. And if you really want to
use a
loop, then you still can. You just can't use foreach.
for(auto r = organism[]; !r.empty; r.popFront())
{
if(r.front.x == x r.front.y == y)
{
organism.stableLinearRemove(take(r, 1));
break;
}
}
but that's a lot more verbose than simply using find, and as I said,
in at
least some cases, find can be more efficient than simply looping,
since it's
optimized for finding elements.
- Jonathan M Davis
Hello again.
I've read all further replies in this thread, but it seems to me this
is the most appropriate place to respond.
Simply put, all of those options are too verbose. If what you want to
do is simple, the syntax should also be simple, this is what I love
about D. As a side-note, I don't come from Java, but I still expect a
container to be able to remove an element by passing it to a method.
The verbosity and the details of this operation should be hidden in
the implementation of the method and I shouldn't need to know about
the details. Otherwise, I could just as well implement my own container.
The basic response to this is, when dealing with containers generically
(that is, you know you have a container, but you don't know what type),
the remove this element operation is not necessarily a good primitive
to have.
Simply because from the myriad of containers, only some can implement
this operation efficiently. Java embeds this operation in the interface,
which means any interface you have to a container could potentially use
O(n) time to remove that element. Such an innocuous piece of syntax
*should* have a cost if it's not efficient IMO.
BTW, the original question doesn't provide enough information to say
remove this element. Even in Java, if you aren't using the default
comparison, you must use a comparator method to determine which one to
remove. If cell.x == x cell.y == y *is* the comparison operator for
the type, then the syntax gets much simpler, because you don't need to
pass a specialized comparison function.
In dcollections, removing a specific element (using the default
comparison operator for that element) on a *fast lookup* container is as
simple as:
container.remove(container.find(x));
Which removes the element x if it's found. However, this is not defined
for containers which use O(n) time to search (such as linked list), you
must use std.algorithm.find for that:
container.remove(find(container[], x).begin);
Should work, and takes O(n) time.
-Steve
I don't really understand what's wrong with inefficient methods. You can
have inefficient
Re: std.container ranges
On Wed, 02 Nov 2011 08:40:19 -0400, Ary Manzana a...@esperanto.org.ar
wrote:
On 11/2/11 8:48 AM, Steven Schveighoffer wrote:
The basic response to this is, when dealing with containers generically
(that is, you know you have a container, but you don't know what type),
the remove this element operation is not necessarily a good primitive
to have.
Simply because from the myriad of containers, only some can implement
this operation efficiently. Java embeds this operation in the interface,
which means any interface you have to a container could potentially use
O(n) time to remove that element. Such an innocuous piece of syntax
*should* have a cost if it's not efficient IMO.
BTW, the original question doesn't provide enough information to say
remove this element. Even in Java, if you aren't using the default
comparison, you must use a comparator method to determine which one to
remove. If cell.x == x cell.y == y *is* the comparison operator for
the type, then the syntax gets much simpler, because you don't need to
pass a specialized comparison function.
In dcollections, removing a specific element (using the default
comparison operator for that element) on a *fast lookup* container is as
simple as:
container.remove(container.find(x));
Which removes the element x if it's found. However, this is not defined
for containers which use O(n) time to search (such as linked list), you
must use std.algorithm.find for that:
container.remove(find(container[], x).begin);
Should work, and takes O(n) time.
-Steve
I don't really understand what's wrong with inefficient methods. You can
have inefficient methods that are convenient, like removing an element
by the default comparison, or giving it a delegate to match the
element(s) to remove.
You profile your application. Is that method the bottle-neck? If so, you
change it to a more efficient one. If not, you are happy you had that
method there, performing in an inefficient way, but which doesn't matter
that much compared to, say, opening an SQL connection.
Programmers want to program, fast. They have schedules, they need to
deliver. They don't need to always find the best solution. They can find
a compromise between working and fast, move on, and later profile
and worry about what matters most.
Programmers don't want to fight with the language or think Oh, so to
remove an element I need to use this operation and combine it with that
one and with that other one...
Or use the right container for the job?
Where it really comes into play is generic programming.
Let's say I write some algorithm that removes certain elements from a
container:
removeElements(C, T)(C c, T t[]...)
{
foreach(x; t)
c.remove(t);
}
What's the complexity of this algorithm? For a HashSet, for instance, it
will be O(n) where n is the number of elements to remove.
But for an ArrayList, it will be O(n*m) where m is the number of elements
in c.
So what we get is, an algorithm whose complexity depends on the complexity
of an operation that varies *widely*. What you end up with is things like
sorting algorithms which are O(n^2) or even worse.
What omitting those methods from the containers that don't support it does
is allow you to make *predictably efficient* generic algorithms. For
example, you know sorting is going to be at most O(nlgn). I don't care
how beautiful the syntax is, a quadratic sort is epic fail, and should be
avoided at all costs.
std.container tries to allow having these inefficient methods by changing
the name (so algorithms can still claim efficiency by not using those
names). My stance is this makes the API overly complex for very little
gain. If something is inefficient, either don't use it, or use the range
interface via std.algorithm. Why should I write a linear search algorithm
when std.algorithm already has done this?
-Steve
Re: std.container ranges
On 11/2/11 10:12 AM, Steven Schveighoffer wrote:
On Wed, 02 Nov 2011 08:40:19 -0400, Ary Manzana a...@esperanto.org.ar
wrote:
On 11/2/11 8:48 AM, Steven Schveighoffer wrote:
The basic response to this is, when dealing with containers generically
(that is, you know you have a container, but you don't know what type),
the remove this element operation is not necessarily a good primitive
to have.
Simply because from the myriad of containers, only some can implement
this operation efficiently. Java embeds this operation in the interface,
which means any interface you have to a container could potentially use
O(n) time to remove that element. Such an innocuous piece of syntax
*should* have a cost if it's not efficient IMO.
BTW, the original question doesn't provide enough information to say
remove this element. Even in Java, if you aren't using the default
comparison, you must use a comparator method to determine which one to
remove. If cell.x == x cell.y == y *is* the comparison operator for
the type, then the syntax gets much simpler, because you don't need to
pass a specialized comparison function.
In dcollections, removing a specific element (using the default
comparison operator for that element) on a *fast lookup* container is as
simple as:
container.remove(container.find(x));
Which removes the element x if it's found. However, this is not defined
for containers which use O(n) time to search (such as linked list), you
must use std.algorithm.find for that:
container.remove(find(container[], x).begin);
Should work, and takes O(n) time.
-Steve
I don't really understand what's wrong with inefficient methods. You
can have inefficient methods that are convenient, like removing an
element by the default comparison, or giving it a delegate to match
the element(s) to remove.
You profile your application. Is that method the bottle-neck? If so,
you change it to a more efficient one. If not, you are happy you had
that method there, performing in an inefficient way, but which doesn't
matter that much compared to, say, opening an SQL connection.
Programmers want to program, fast. They have schedules, they need to
deliver. They don't need to always find the best solution. They can
find a compromise between working and fast, move on, and later
profile and worry about what matters most.
Programmers don't want to fight with the language or think Oh, so to
remove an element I need to use this operation and combine it with
that one and with that other one...
Or use the right container for the job?
Where it really comes into play is generic programming.
Let's say I write some algorithm that removes certain elements from a
container:
removeElements(C, T)(C c, T t[]...)
{
foreach(x; t)
c.remove(t);
}
What's the complexity of this algorithm? For a HashSet, for instance, it
will be O(n) where n is the number of elements to remove.
But for an ArrayList, it will be O(n*m) where m is the number of
elements in c.
But I'm sure in this algorithm I have for this app I'm making, my
collection won't have more than 50 elements. So everything will be O(1).
I need to remove an element from the collection. I really don't care
about the complexity of the operation, because if n is 50, everything is
O(1).
Why can't I have an inefficient (for you) remove operation that, for me,
will be ok? I don't want to spend 2 hours browsing the ranges algorithms
to figure out how to combine them to remove an element...
My point is, as someone else said it in another post: add inefficient
operations and tell the programmer so. Then he can decide what to do. If
he's sure that that performance penalty is not a big issue for him,
he'll be happy to have that method available.
Re: std.container ranges
On Wed, 02 Nov 2011 09:17:39 -0400, Ary Manzana a...@esperanto.org.ar
wrote:
On 11/2/11 10:12 AM, Steven Schveighoffer wrote:
On Wed, 02 Nov 2011 08:40:19 -0400, Ary Manzana a...@esperanto.org.ar
wrote:
On 11/2/11 8:48 AM, Steven Schveighoffer wrote:
The basic response to this is, when dealing with containers
generically
(that is, you know you have a container, but you don't know what
type),
the remove this element operation is not necessarily a good
primitive
to have.
Simply because from the myriad of containers, only some can implement
this operation efficiently. Java embeds this operation in the
interface,
which means any interface you have to a container could potentially
use
O(n) time to remove that element. Such an innocuous piece of syntax
*should* have a cost if it's not efficient IMO.
BTW, the original question doesn't provide enough information to say
remove this element. Even in Java, if you aren't using the default
comparison, you must use a comparator method to determine which one to
remove. If cell.x == x cell.y == y *is* the comparison operator for
the type, then the syntax gets much simpler, because you don't need to
pass a specialized comparison function.
In dcollections, removing a specific element (using the default
comparison operator for that element) on a *fast lookup* container is
as
simple as:
container.remove(container.find(x));
Which removes the element x if it's found. However, this is not
defined
for containers which use O(n) time to search (such as linked list),
you
must use std.algorithm.find for that:
container.remove(find(container[], x).begin);
Should work, and takes O(n) time.
-Steve
I don't really understand what's wrong with inefficient methods. You
can have inefficient methods that are convenient, like removing an
element by the default comparison, or giving it a delegate to match
the element(s) to remove.
You profile your application. Is that method the bottle-neck? If so,
you change it to a more efficient one. If not, you are happy you had
that method there, performing in an inefficient way, but which doesn't
matter that much compared to, say, opening an SQL connection.
Programmers want to program, fast. They have schedules, they need to
deliver. They don't need to always find the best solution. They can
find a compromise between working and fast, move on, and later
profile and worry about what matters most.
Programmers don't want to fight with the language or think Oh, so to
remove an element I need to use this operation and combine it with
that one and with that other one...
Or use the right container for the job?
Where it really comes into play is generic programming.
Let's say I write some algorithm that removes certain elements from a
container:
removeElements(C, T)(C c, T t[]...)
{
foreach(x; t)
c.remove(t);
}
What's the complexity of this algorithm? For a HashSet, for instance, it
will be O(n) where n is the number of elements to remove.
But for an ArrayList, it will be O(n*m) where m is the number of
elements in c.
But I'm sure in this algorithm I have for this app I'm making, my
collection won't have more than 50 elements. So everything will be O(1).
I need to remove an element from the collection. I really don't care
about the complexity of the operation, because if n is 50, everything is
O(1).
Then your specific application can use std.algorithm.find to implement the
equivalent. Only the algorithm body changes, not the usage of the
algorithm.
Why can't I have an inefficient (for you) remove operation that, for me,
will be ok?
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?
I don't want to spend 2 hours browsing the ranges algorithms to figure
out how to combine them to remove an element...
You severely exaggerate the amount of time needed to browse the
algorithms. I wrote an equivalent in less
Re: std.container ranges
On 11/2/2011 2:41 PM, Steven Schveighoffer wrote:
On Wed, 02 Nov 2011 09:17:39 -0400, Ary Manzana a...@esperanto.org.ar
wrote:
On 11/2/11 10:12 AM, Steven Schveighoffer wrote:
On Wed, 02 Nov 2011 08:40:19 -0400, Ary Manzana a...@esperanto.org.ar
wrote:
On 11/2/11 8:48 AM, Steven Schveighoffer wrote:
The basic response to this is, when dealing with containers
generically
(that is, you know you have a container, but you don't know what
type),
the remove this element operation is not necessarily a good
primitive
to have.
Simply because from the myriad of containers, only some can implement
this operation efficiently. Java embeds this operation in the
interface,
which means any interface you have to a container could potentially
use
O(n) time to remove that element. Such an innocuous piece of syntax
*should* have a cost if it's not efficient IMO.
BTW, the original question doesn't provide enough information to say
remove this element. Even in Java, if you aren't using the default
comparison, you must use a comparator method to determine which one to
remove. If cell.x == x cell.y == y *is* the comparison operator for
the type, then the syntax gets much simpler, because you don't need to
pass a specialized comparison function.
In dcollections, removing a specific element (using the default
comparison operator for that element) on a *fast lookup* container
is as
simple as:
container.remove(container.find(x));
Which removes the element x if it's found. However, this is not
defined
for containers which use O(n) time to search (such as linked list),
you
must use std.algorithm.find for that:
container.remove(find(container[], x).begin);
Should work, and takes O(n) time.
-Steve
I don't really understand what's wrong with inefficient methods. You
can have inefficient methods that are convenient, like removing an
element by the default comparison, or giving it a delegate to match
the element(s) to remove.
You profile your application. Is that method the bottle-neck? If so,
you change it to a more efficient one. If not, you are happy you had
that method there, performing in an inefficient way, but which doesn't
matter that much compared to, say, opening an SQL connection.
Programmers want to program, fast. They have schedules, they need to
deliver. They don't need to always find the best solution. They can
find a compromise between working and fast, move on, and later
profile and worry about what matters most.
Programmers don't want to fight with the language or think Oh, so to
remove an element I need to use this operation and combine it with
that one and with that other one...
Or use the right container for the job?
Where it really comes into play is generic programming.
Let's say I write some algorithm that removes certain elements from a
container:
removeElements(C, T)(C c, T t[]...)
{
foreach(x; t)
c.remove(t);
}
What's the complexity of this algorithm? For a HashSet, for instance, it
will be O(n) where n is the number of elements to remove.
But for an ArrayList, it will be O(n*m) where m is the number of
elements in c.
But I'm sure in this algorithm I have for this app I'm making, my
collection won't have more than 50 elements. So everything will be
O(1). I need to remove an element from the collection. I really don't
care about the complexity of the operation, because if n is 50,
everything is O(1).
Then your specific application can use std.algorithm.find to implement
the equivalent. Only the algorithm body changes, not the usage of the
algorithm.
Why can't I have an inefficient (for you) remove operation that, for
me, will be ok?
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?
I don't want to spend 2 hours browsing the ranges algorithms to figure
out how to combine them to remove an element...
You severely exaggerate the amount of time needed to browse the
algorithms. I wrote an equivalent in less than a minute. And I don't
Re: std.container ranges
Steven Schveighoffer Wrote: ahem, using dcollections: foreach(ref doRemove, cell; organism.purge) doRemove = cell.x == x cell.y == y; complexity: O(n) may be a generic iteration handler would be more useful? foreach(ref handler, cell; organism.each) if(cell.x == x cell.y == y) handler.removeCurrent(); it could provide a whole api, say, you may want to have lookahead foreach(ref handler, cell; organism.each) if(cell.x == x cell.y == y handler.next.x==0) handler.removeCurrent();
Re: std.container ranges
Jonathan M Davis wrote:
find allows
you to do that just fine, and such a remove function would simply be
duplicating its functionality.
But this thread serves as a proof that it is not obvious and something like
containers should be obvious to use. Deleting an element with a certain
value is a common task and should should not take
three function calls, with functions from three different modules.
You would be doing exactly the same thing in C++ except that it would be
with an iterator rather than a range. You would use find to find the
iterator to the element that you wanted and then you'd pass that to the
list's erase function.
I don't think we should refer to C++ as an benchmark for ease of use.
How do you delete every occurence of v? Not just the first one? Is this
equally easy with find and take? I didn't find an easy way not
envolving a loop within 10 Minutes by reading the documentation.
What do you think of an construct like this:
foreach(item, itemRange; container)
{
// itemRange is a range only containing item
// itemRange.length == 1 itemRange.front == item
}
That would be analogous to foreach over array with an index. You might think
that iterating explicity may not be elegant. But it is what people want to
do and it should not be any harder than necessary.
--
Tobias
Re: std.container ranges
On 31.10.2011 11:16, Tobias Pankrath wrote:
Jonathan M Davis wrote:
find allows
you to do that just fine, and such a remove function would simply be
duplicating its functionality.
But this thread serves as a proof that it is not obvious and something like
containers should be obvious to use. Deleting an element with a certain
value is a common task and should should not take
three function calls, with functions from three different modules.
You would be doing exactly the same thing in C++ except that it would be
with an iterator rather than a range. You would use find to find the
iterator to the element that you wanted and then you'd pass that to the
list's erase function.
I don't think we should refer to C++ as an benchmark for ease of use.
How do you delete every occurence of v? Not just the first one? Is this
equally easy with find and take? I didn't find an easy way not
envolving a loop within 10 Minutes by reading the documentation.
It is, let's use remove from std.algorithm! ... though there is no
overload of remove for forward ranges ... crap, worthy of bugzilla
report. Or SList could be special enough to offer a built-in remove with
predicate done in O(n).
However this should work( yet because of apparent bug in SList it
doesn't). The bug is:
Line 1294 of std.container should be:
for (; !r.empty; r.popFront())
...
or it will remove the whole container.
Code:
import std.container, std.range;
import std.functional, std.algorithm, std.stdio;
void removeFromList(alias pred, T)(ref SList!T s)
{
static if(is(typeof(pred) == string))
alias unaryFun!pred Pred;
else
alias pred Pred;
for(auto r=s[]; !r.empty; )
{
if(Pred(r.front))
{
r = s.linearRemove(take(r,1));
continue;
}
else
r.popFront();
}
}
void main()
{
SList!int list(20, 30, 40, 50, 60); // will work with stock Phobos if
the first element % 20 != 0
removeFromList!a % 20 == 0(list);
writeln(list[]);
}
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.
What do you think of an construct like this:
foreach(item, itemRange; container)
{
// itemRange is a range only containing item
// itemRange.length == 1 itemRange.front == item
}
That would be analogous to foreach over array with an index. You might think
that iterating explicity may not be elegant. But it is what people want to
do and it should not be any harder than necessary.
You still can, just use plain range interface with empty/front/popFront.
for(auto r = list[]; !r.empty; r.popFront())
{
...
}
--
Dmitry Olshansky
Re: std.container ranges
On Monday, October 31, 2011 13:16:11 Dmitry Olshansky wrote: On 31.10.2011 11:16, Tobias Pankrath wrote: Jonathan M Davis wrote: find allows you to do that just fine, and such a remove function would simply be duplicating its functionality. But this thread serves as a proof that it is not obvious and something like containers should be obvious to use. Deleting an element with a certain value is a common task and should should not take three function calls, with functions from three different modules. You would be doing exactly the same thing in C++ except that it would be with an iterator rather than a range. You would use find to find the iterator to the element that you wanted and then you'd pass that to the list's erase function. I don't think we should refer to C++ as an benchmark for ease of use. How do you delete every occurence of v? Not just the first one? Is this equally easy with find and take? I didn't find an easy way not envolving a loop within 10 Minutes by reading the documentation. It is, let's use remove from std.algorithm! ... though there is no overload of remove for forward ranges ... crap, worthy of bugzilla report. Probably because it has to swap elements around, which requires a bidirectional range. Or SList could be special enough to offer a built-in remove with predicate done in O(n). It would be valuable in general IMHO. We should add something similar to the STL's remove_if function on linked lists. The fact that std.algorith.remove must shuffle elements around instead of actually removing them (similar to what the STL does with its free function erase) just shows how it doesn't really work all that well. It can be done _much_ more efficiently by putting remove_if (or whatever we would call it) on the container. It's also less confusing, since std.algorithm.remove (and the STL's erase function) doesn't actually _anything_. You have to pass the returned range (or iterator in C++) to the container's linearRemove function (or erase in C++) to remove the elements, which is _highly_ confusing (but since iterators and ranges don't really know about their containers beyond the elements that they reference, it's the best that can be done with a free function). For the case where you're searching for a specific element to remove though, I see no reason to add another function. That's what find is for (and given that we have lambdas, it's easy to use even in the case where you need a predicate other than ==), and if you really want to, you can iterate the range explicitly and pass the portion of the range to the container's remove function that you want to remove. The main problem with it is that we don't have proper examples, and we don't have enough documentation explaining ranges in general, so it's not immediately obvious to people how to properly use a container's remove function. - Jonathan M Davis
Re: std.container ranges
On 31.10.2011 18:38, Steven Schveighoffer wrote:
On Mon, 31 Oct 2011 05:16:11 -0400, Dmitry Olshansky
dmitry.o...@gmail.com wrote:
On 31.10.2011 11:16, Tobias Pankrath wrote:
Jonathan M Davis wrote:
find allows
you to do that just fine, and such a remove function would simply be
duplicating its functionality.
But this thread serves as a proof that it is not obvious and
something like
containers should be obvious to use. Deleting an element with a certain
value is a common task and should should not take
three function calls, with functions from three different modules.
You would be doing exactly the same thing in C++ except that it
would be
with an iterator rather than a range. You would use find to find the
iterator to the element that you wanted and then you'd pass that to the
list's erase function.
I don't think we should refer to C++ as an benchmark for ease of use.
How do you delete every occurence of v? Not just the first one? Is this
equally easy with find and take? I didn't find an easy way not
envolving a loop within 10 Minutes by reading the documentation.
It is, let's use remove from std.algorithm! ... though there is no
overload of remove for forward ranges ... crap, worthy of bugzilla
report. Or SList could be special enough to offer a built-in remove
with predicate done in O(n).
However this should work( yet because of apparent bug in SList it
doesn't). The bug is:
Line 1294 of std.container should be:
for (; !r.empty; r.popFront())
...
or it will remove the whole container.
Code:
import std.container, std.range;
import std.functional, std.algorithm, std.stdio;
void removeFromList(alias pred, T)(ref SList!T s)
{
static if(is(typeof(pred) == string))
alias unaryFun!pred Pred;
else
alias pred Pred;
for(auto r=s[]; !r.empty; )
{
if(Pred(r.front))
{
r = s.linearRemove(take(r,1));
continue;
}
else
r.popFront();
}
}
void main()
{
SList!int list(20, 30, 40, 50, 60); // will work with stock Phobos if
the first element % 20 != 0
removeFromList!a % 20 == 0(list);
writeln(list[]);
}
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.
ahem, using dcollections:
foreach(ref doRemove, cell; organism.purge)
doRemove = cell.x == x cell.y == y;
complexity: O(n)
While computer happily does O(n) work here, my brain screams in
cognitive dissonance figuring out that this assignment actually does
delete... meh voodoo through and through :)
I'd rather
organism.remove!((cell){ return cell.x == x cell.y == y; })();
or something like that.
But it's not a question of form, but more of a missing stuff that should
be there.
:)
-Steve
--
Dmitry Olshansky
Re: std.container ranges
Looks like it was accidental cross-posting: On 31.10.2011 20:11, Alessandro Stamatto wrote: 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. Now you're scaring me... You're saying that SList in D not only is bugged, but a templated remove_if would run in O(N^2) instead of O(N) Basically I'm saying that with current SList *implementation* it will run in O(N^2), because for some reason it always do a check on each range passed to remove that it does belong to this list. (i.e. it walks from head till hits it or it's own tail) -- Dmitry Olshansky
Re: std.container ranges (n^2 ?!!!!)
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. Now you're scaring me... You're saying that SList in D not only is bugged, but a templated remove_if would run in O(N^2) instead of O(N)
Re: std.container ranges
On Mon, 31 Oct 2011 12:40:37 -0400, Dmitry Olshansky
dmitry.o...@gmail.com wrote:
On 31.10.2011 18:38, Steven Schveighoffer wrote:
On Mon, 31 Oct 2011 05:16:11 -0400, Dmitry Olshansky
dmitry.o...@gmail.com wrote:
On 31.10.2011 11:16, Tobias Pankrath wrote:
Jonathan M Davis wrote:
find allows
you to do that just fine, and such a remove function would simply be
duplicating its functionality.
But this thread serves as a proof that it is not obvious and
something like
containers should be obvious to use. Deleting an element with a
certain
value is a common task and should should not take
three function calls, with functions from three different modules.
You would be doing exactly the same thing in C++ except that it
would be
with an iterator rather than a range. You would use find to find the
iterator to the element that you wanted and then you'd pass that to
the
list's erase function.
I don't think we should refer to C++ as an benchmark for ease of use.
How do you delete every occurence of v? Not just the first one? Is
this
equally easy with find and take? I didn't find an easy way not
envolving a loop within 10 Minutes by reading the documentation.
It is, let's use remove from std.algorithm! ... though there is no
overload of remove for forward ranges ... crap, worthy of bugzilla
report. Or SList could be special enough to offer a built-in remove
with predicate done in O(n).
However this should work( yet because of apparent bug in SList it
doesn't). The bug is:
Line 1294 of std.container should be:
for (; !r.empty; r.popFront())
...
or it will remove the whole container.
Code:
import std.container, std.range;
import std.functional, std.algorithm, std.stdio;
void removeFromList(alias pred, T)(ref SList!T s)
{
static if(is(typeof(pred) == string))
alias unaryFun!pred Pred;
else
alias pred Pred;
for(auto r=s[]; !r.empty; )
{
if(Pred(r.front))
{
r = s.linearRemove(take(r,1));
continue;
}
else
r.popFront();
}
}
void main()
{
SList!int list(20, 30, 40, 50, 60); // will work with stock Phobos if
the first element % 20 != 0
removeFromList!a % 20 == 0(list);
writeln(list[]);
}
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.
ahem, using dcollections:
foreach(ref doRemove, cell; organism.purge)
doRemove = cell.x == x cell.y == y;
complexity: O(n)
While computer happily does O(n) work here, my brain screams in
cognitive dissonance figuring out that this assignment actually does
delete... meh voodoo through and through :)
I'd rather
organism.remove!((cell){ return cell.x == x cell.y == y; })();
or something like that.
But it's not a question of form, but more of a missing stuff that should
be there.
That could also be added (and I agree it's a good idea). Alas, interface
templates still don't work, so it'd have to be defined as a convention.
Note that this isn't really the intended usage for purge (though it works
quite nicely as an afterthought). Typically, when I use purge, I'm
iterating through all the elements, processing them somehow, and then
deciding to remove them or not based on the processing.
For instance, a main thread processing results from sub-threads, and
removing ones that are finished.
Think of it as an implementation of Java's Iterator.remove:
http://download.oracle.com/javase/7/docs/api/java/util/Iterator.html#remove()
-Steve
std.container ranges
Hello there.
I seem to be having problems wrapping my head around how to use the
ranges in the context of containers in phobos. Specifically, I can't
seem to figure out how to remove an element from a linked list.
foreach(cell; organism)
{
if(cell.x == x cell.y == y)
{
organism.stableLinearRemove(cell);
break;
}
}
mind.d(123): Error: function
std.container.SList!(Cell).SList.linearRemove (Range r) is not callable
using argument types (Cell)
mind.d(123): Error: cannot implicitly convert expression (cell) of type
cell.Cell to Take!(Range)
I somehow get the feeling such a basic operation should just...work?
/Max
Re: std.container ranges
On Sunday, October 30, 2011 11:38:30 Max Wolter wrote:
Hello there.
I seem to be having problems wrapping my head around how to use the
ranges in the context of containers in phobos. Specifically, I can't
seem to figure out how to remove an element from a linked list.
foreach(cell; organism)
{
if(cell.x == x cell.y == y)
{
organism.stableLinearRemove(cell);
break;
}
}
mind.d(123): Error: function
std.container.SList!(Cell).SList.linearRemove (Range r) is not callable
using argument types (Cell)
mind.d(123): Error: cannot implicitly convert expression (cell) of type
cell.Cell to Take!(Range)
I somehow get the feeling such a basic operation should just...work?
linearRemove (and stableLinearRemove) takes a _range_ not a value. cell is an
element in the list, not a range over the list. The range that it takes must
be either of type SList.Range or Take!(SList.Range). You get that range by
slicing an SList. Take!(SList.Range) is for the case where you want only a
portion of the beginning of a range rather than the whole range. Your example
actually has a really simple solution:
auto found = find!((a){return a.x == x a.y == y;})(organism[]);
organism.stableLinearRemove(take(found, 1));
It finds the element in the list that you're looking for, and then it passes a
range with that one element to stableLinearRemove so that it'll remove it.
- Jonathan M Davis
Re: std.container ranges
On 10/30/2011 6:45 PM, Jonathan M Davis wrote:
On Sunday, October 30, 2011 11:38:30 Max Wolter wrote:
Hello there.
I seem to be having problems wrapping my head around how to use the
ranges in the context of containers in phobos. Specifically, I can't
seem to figure out how to remove an element from a linked list.
foreach(cell; organism)
{
if(cell.x == x cell.y == y)
{
organism.stableLinearRemove(cell);
break;
}
}
mind.d(123): Error: function
std.container.SList!(Cell).SList.linearRemove (Range r) is not callable
using argument types (Cell)
mind.d(123): Error: cannot implicitly convert expression (cell) of type
cell.Cell to Take!(Range)
I somehow get the feeling such a basic operation should just...work?
linearRemove (and stableLinearRemove) takes a _range_ not a value. cell is an
element in the list, not a range over the list. The range that it takes must
be either of type SList.Range or Take!(SList.Range). You get that range by
slicing an SList. Take!(SList.Range) is for the case where you want only a
portion of the beginning of a range rather than the whole range. Your example
actually has a really simple solution:
auto found = find!((a){return a.x == x a.y == y;})(organism[]);
organism.stableLinearRemove(take(found, 1));
It finds the element in the list that you're looking for, and then it passes a
range with that one element to stableLinearRemove so that it'll remove it.
- Jonathan M Davis
Hello there.
Thank you very much for the explanation.
However, while I really liked the concept of ranges in Andrei's book and
a lot of it seems intuitive and faster than using iterators, I can't
shake the feeling that in this case, it's just unnecessarily convoluted.
Maybe it's just the fact that the container library is still very basic,
but I don't think I should go through such a complicated procedure to
remove an known element from a list. It's just not a very simple or
intuitive solution, which is something I came to love D for thus far.
/Max
Re: std.container ranges
On Sunday, October 30, 2011 20:53:02 Max Wolter wrote:
Hello there.
Thank you very much for the explanation.
However, while I really liked the concept of ranges in Andrei's book and
a lot of it seems intuitive and faster than using iterators, I can't
shake the feeling that in this case, it's just unnecessarily convoluted.
Maybe it's just the fact that the container library is still very basic,
but I don't think I should go through such a complicated procedure to
remove an known element from a list. It's just not a very simple or
intuitive solution, which is something I came to love D for thus far.
You would be doing exactly the same thing in C++ except that it would be with
an iterator rather than a range. You would use find to find the iterator to the
element that you wanted and then you'd pass that to the list's erase function.
It is only more complicated in D in that you get a range which _starts_ with
the element that you want (essentially, you get the iterator to that element
plus the end iterator for the list), so if you want to remove only the first
element, you take it from the front of the range. Other than that, it's the
same as in C++. You can't remove an element from a list in C++ by giving that
element to the list anymore than you can in D. In both cases, you need an
iterator or a range.
So, in comparison to C++, there's no significant difference. Now, Java does
have
a remove function which will take an element and remove the first occurence of
that element from a list, and we could theoretically add one, but why? It
would just be duplicating the functionality that find already gives. Java
doesn't use iterators the way the C++ does, and it doesn't have ranges, so it
_can't_ have a find function the way that C++ and D do, but D can. And in some
cases, find can do it more efficiently than your loop could have.
I grant you that if you're not used to using find like this in C++ (and far,
far too many C++ programmers use loops instead of find - in part because pre-
C++11, there were no lambdas and any time you need a custom comparison
function, it's a pain to get one), then it's not immediately intuitive, but
it's far more flexible and powerful than removing elements by giving the
element to a remove function on the list. And if you really want to use a
loop, then you still can. You just can't use foreach.
for(auto r = organism[]; !r.empty; r.popFront())
{
if(r.front.x == x r.front.y == y)
{
organism.stableLinearRemove(take(r, 1));
break;
}
}
but that's a lot more verbose than simply using find, and as I said, in at
least some cases, find can be more efficient than simply looping, since it's
optimized for finding elements.
- Jonathan M Davis
Re: std.container ranges
On Monday, October 31, 2011 12:11:45 Mike Parker wrote: On 10/31/2011 5:28 AM, Jonathan M Davis wrote: So, in comparison to C++, there's no significant difference. Now, Java does have a remove function which will take an element and remove the first occurence of that element from a list, and we could theoretically add one, but why? IMO, it's much more intuitive to say list.remove(item). It's the first thing a lot of people expect coming from a Java background, that's for sure. The first time I tried to use SList, being unfamiliar with ranges as I was, it took a while to figure out what I needed to do. IIRC, I had to post here to ask. The problem is that you really have to understand ranges and the Phobos functions that manipulate them before you can begin to use containers. I think that's wrong. Ideally, containers should be usable without having to know about find and Take and whatever else. This isn't the first time this question has come up in the NG and I've got a feeling it won't be the last. At the very least it would be nice to see something in the documentation tying std.algorithm and std.range together with std.container. Something to point the way for those to whom it isn't obvious. I definitely agree that the documentation should be improved to at least give the basic example of using find with linearRemove. Adding something similar to C++'s remove_if which removes all elements which match a predicate could also be useful, but I don't at all agree that there should be a function which takes an element and removes the first element which is equal to it. find allows you to do that just fine, and such a remove function would simply be duplicating its functionality. As for understanding ranges, it's definitely true that there needs to be more documentation and/or articles on them so that the concept can better communicated. That's a definite flaw in the current documentation. But there's a lot in Phobos which you're just not going to be able to use if you don't understand ranges, and the library would definitely be worse if it used them less, since they're such a powerful concept, so I think that the problem is the lack of communication on ranges, not the fact that ranges are used so heavily in Phobos. - Jonathan M Davis
