www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - eliminating std.range.SListRange?

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
It seems to me it doesn't bring anything noteworthy over 
std.container.SList. Would anyone miss it if I erased it?

Andrei
May 30 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:

 It seems to me it doesn't bring anything noteworthy over 
 std.container.SList. Would anyone miss it if I erased it?

One linked list is enough. Can't the heap in std.algorithm be moved to the collections/containers? Bye, bearophile
May 30 2010
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 05/30/2010 02:01 PM, bearophile wrote:
 Andrei Alexandrescu:

 It seems to me it doesn't bring anything noteworthy over
 std.container.SList. Would anyone miss it if I erased it?

One linked list is enough.

Sounds good.
 Can't the heap in std.algorithm be moved to the collections/containers?

The heap is a tad difficult to tackle. Most of the time you don't want to create a heap, but instead to organize an existing range as a heap. As such, the heap is not always obvious to think of as a container. I'm undecided on how to approach this. Andrei
May 30 2010
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:
 Sounds good.

I'd like a single linked one, and a double linked one (but in my opinion in modern programming linked lists are uncommon. In most situations dynamic arrays are better).
 The heap is a tad difficult to tackle. Most of the time you don't want 
 to create a heap, but instead to organize an existing range as a heap. 
 As such, the heap is not always obvious to think of as a container. I'm 
 undecided on how to approach this.

As usual some pieces of Reality don't perfectly fit our categories :-) A collection is something able to hold/keep many items. A heap is a data structure, it's one specific organization of data. They are two different things, it's like the difference between an "array" and a "sorted array", they are two different data structures (because you can't append randomly in the second one), but they are represented with the same collection. You can map one data structure on different collections. A "heap struct" (as the one in std.algorithm) is not an algorithm, so std.algorithm is not the right place for it, so it's better to move it elsewhere. Bye, bearophile
May 30 2010
parent reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
On 05/30/2010 06:00 PM, bearophile wrote:

 I'd like a single linked one, and a double linked one (but in my opinion in
modern programming linked lists are uncommon. In most situations dynamic arrays
are better).

I think you just program too much in python <g>
May 30 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
Ellery Newcomer:
 I think you just program too much in python <g>

On modern CPUs most times liked lists are the wrong data structure to use. They are slower, use more memory, can be less handy and less safe. There are few situations where a single/double linked list is better, but they are quite uncommon (for example when you have often to add/remove items from the middle of a sequence and you can find such points quickly, this happens for example in the dancing link algorithm). Bye, bearophile
May 30 2010
parent reply Jonathan M Davis <jmdavisProg gmail.com> writes:
bearophile wrote:

 Ellery Newcomer:
 I think you just program too much in python <g>

On modern CPUs most times liked lists are the wrong data structure to use. They are slower, use more memory, can be less handy and less safe. There are few situations where a single/double linked list is better, but they are quite uncommon (for example when you have often to add/remove items from the middle of a sequence and you can find such points quickly, this happens for example in the dancing link algorithm). Bye, bearophile

Uncommon? Sure, if you don't need the ability to arbitrarily add and remove elements from a container, then a vector type is definitely better than a linked list. However, there are _plenty_ of cases out there where the ability to arbitrarily add and remove elements from a container is a necessity. It depends entirely on the algorithm that you're using and what you're trying to do. Just because you, personally, don't run into many situations where linked lists are needed does not mean that others don't. Linked lists are a basic, vital data structure in any good container library. True, it's best to prefer vector types when you don't need the specific abilities of a linked list, but that does not mean that the linked list isn't going to be frequently used, just that it shouldn't be used when it isn't needed. - Jonathan M Davis
May 30 2010
parent bearophile <bearophileHUGS lycos.com> writes:
Jonathan M Davis:

Uncommon? Sure, if you don't need the ability to arbitrarily add and remove
elements from a container, then a vector type is definitely better than a
linked list. However, there are _plenty_ of cases out there where the ability
to arbitrarily add and remove elements from a container is a necessity. It
depends entirely on the algorithm that you're using and what you're trying to
do.<

In many cases the items you have to remove are not so specific, so you can just pop the last item of a dynamic array. The same for adding items. If you have to remove specific items you often don't need to keep their order, so you can move the last item to the array slot that now is free, and shorten the array length by one. You can take a look here: http://www.fantascienza.net/leonardo/ar/list_deletions.html Dynamic arrays can contain references or pointers, so you can swap items around efficiently using their index. Modern CPUs have two or more cache layers, this means that today following link chains worsens the access pattern inside the cache lines, and pointers need memory that increses cache pressure. In most of your algorithms you can replace linked lists with *good* dynamic arrays (D ones are not good enough in their append performance) with a general performance and memory improvement. And the code can become simpler. There are few situations where linked lists are useful, but today they are uncommon. Even if you use linked lists often, this doesn't mean they are the often better than using a dynamic array. Bye, bearophile
May 31 2010
prev sibling next sibling parent Lutger <lutger.blijdestijn gmail.com> writes:
Andrei Alexandrescu wrote:

 On 05/30/2010 02:01 PM, bearophile wrote:
 Andrei Alexandrescu:

 It seems to me it doesn't bring anything noteworthy over
 std.container.SList. Would anyone miss it if I erased it?

One linked list is enough.

Sounds good.
 Can't the heap in std.algorithm be moved to the collections/containers?

The heap is a tad difficult to tackle. Most of the time you don't want to create a heap, but instead to organize an existing range as a heap. As such, the heap is not always obvious to think of as a container. I'm undecided on how to approach this. Andrei

I would also rather think of heap as the heapify operation, not unlike partition.
Jun 01 2010
prev sibling next sibling parent reply Don <nospam nospam.com> writes:
Steven Schveighoffer wrote:
 On Sun, 30 May 2010 18:33:22 -0400, Andrei Alexandrescu 
 <SeeWebsiteForEmail erdani.org> wrote:
 
 
 The heap is a tad difficult to tackle. Most of the time you don't want 
 to create a heap, but instead to organize an existing range as a heap. 
 As such, the heap is not always obvious to think of as a container. 
 I'm undecided on how to approach this.

It's easier to think of a heap as a single entity with operations on it. At least for me anyway. Most of the time, once you make a range a heap, you want to continue to use it as a heap. Restricting operations on that range by defining a heap type around it can do this. Otherwise, you could accidentally do something foolish like sort the range. -Steve

But for several graph algorithms, (eg, A* pathfinding), you have {key1, key2} pairs, forming a heap based on key1, but you also need to able to search for key2. The container is a hybrid, consisting of heap on {key1} + AA on {key2}. It uses the heap operations, but it's not exactly a heap. Incidentally this requires the adjust_heap() operation, which was dropped from the STL for political reasons, but should be provided in D.
Jun 01 2010
parent Don <nospam nospam.com> writes:
Steven Schveighoffer wrote:
 On Tue, 01 Jun 2010 09:17:15 -0400, Don <nospam nospam.com> wrote:
 
 Steven Schveighoffer wrote:
 On Sun, 30 May 2010 18:33:22 -0400, Andrei Alexandrescu 
 <SeeWebsiteForEmail erdani.org> wrote:

 The heap is a tad difficult to tackle. Most of the time you don't 
 want to create a heap, but instead to organize an existing range as 
 a heap. As such, the heap is not always obvious to think of as a 
 container. I'm undecided on how to approach this.

it. At least for me anyway. Most of the time, once you make a range a heap, you want to continue to use it as a heap. Restricting operations on that range by defining a heap type around it can do this. Otherwise, you could accidentally do something foolish like sort the range. -Steve

But for several graph algorithms, (eg, A* pathfinding), you have {key1, key2} pairs, forming a heap based on key1, but you also need to able to search for key2. The container is a hybrid, consisting of heap on {key1} + AA on {key2}. It uses the heap operations, but it's not exactly a heap.

And such a container would be not a heap. I don't think it should be impossible to define such a construct if a vanilla heap type is also defined. My recommendation: keep the heap functions in std.algorithm and create a std.container based off them.

That's what I think, too.
Jun 01 2010
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 06/01/2010 07:57 AM, Steven Schveighoffer wrote:
 On Sun, 30 May 2010 18:33:22 -0400, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:


 The heap is a tad difficult to tackle. Most of the time you don't want
 to create a heap, but instead to organize an existing range as a heap.
 As such, the heap is not always obvious to think of as a container.
 I'm undecided on how to approach this.

It's easier to think of a heap as a single entity with operations on it. At least for me anyway. Most of the time, once you make a range a heap, you want to continue to use it as a heap. Restricting operations on that range by defining a heap type around it can do this. Otherwise, you could accidentally do something foolish like sort the range.

The problem is the original range is still around. void fun(Range)(Range r) if (isRandomAccessRange!Range) { auto heap = BinaryHeap!Range(r); ... use heap, but r is still there ... } This is not memory-unsafe, but may mess up the working of the heap. If the heap takes a copy of the range, that would most often be wasteful. Andrei
Jun 01 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 06/01/2010 08:43 AM, Steven Schveighoffer wrote:
 On Tue, 01 Jun 2010 09:28:28 -0400, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 On 06/01/2010 07:57 AM, Steven Schveighoffer wrote:
 On Sun, 30 May 2010 18:33:22 -0400, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:


 The heap is a tad difficult to tackle. Most of the time you don't want
 to create a heap, but instead to organize an existing range as a heap.
 As such, the heap is not always obvious to think of as a container.
 I'm undecided on how to approach this.

It's easier to think of a heap as a single entity with operations on it. At least for me anyway. Most of the time, once you make a range a heap, you want to continue to use it as a heap. Restricting operations on that range by defining a heap type around it can do this. Otherwise, you could accidentally do something foolish like sort the range.

The problem is the original range is still around. void fun(Range)(Range r) if (isRandomAccessRange!Range) { auto heap = BinaryHeap!Range(r); ... use heap, but r is still there ... } This is not memory-unsafe, but may mess up the working of the heap. If the heap takes a copy of the range, that would most often be wasteful.

You can go through lengths to make sure r isn't accessible outside it's heap interface, for example, by splitting fun into two functions: void fun(Range)(Range r) if (isRandomAccessRange!Range) { auto heap = BinaryHeap!Range(r); fun2(heap); // in this function, r is not accessible. } And even without this, I can stop using r after the first line. I have a better chance of not using r in a non-heap way in that case. A heap type also may want to make a copy of the input, most other containers do. This allows it to own the storage for the data.

Good points. Let me just mention that I wrote BinaryHeap for a number of practical necessities. Without exception, _all_ would be killed if copying would be required. IMHO requiring copying is out of the question. I see two possibilities: (a) Move BinaryHeap as it is to std.container. That means you can build a heap around any given random-access range, but it also means that the heap can't grow beyond the original range's size. Incidentally this is often the case, but I'm sure not always. (b) Have BinaryHeap require a container, then define a method Array!(T).acquire(T[]) that assumes ownership of a given buffer. In such cases, you can define a growable BinaryHeap on top of an array that has just acquired a given range. Other random-access ranges, however, would not be supported. Not sure what to do. Andrei
Jun 01 2010
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sun, 30 May 2010 18:33:22 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:


 The heap is a tad difficult to tackle. Most of the time you don't want  
 to create a heap, but instead to organize an existing range as a heap.  
 As such, the heap is not always obvious to think of as a container. I'm  
 undecided on how to approach this.

It's easier to think of a heap as a single entity with operations on it. At least for me anyway. Most of the time, once you make a range a heap, you want to continue to use it as a heap. Restricting operations on that range by defining a heap type around it can do this. Otherwise, you could accidentally do something foolish like sort the range. -Steve
Jun 01 2010
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 01 Jun 2010 09:17:15 -0400, Don <nospam nospam.com> wrote:

 Steven Schveighoffer wrote:
 On Sun, 30 May 2010 18:33:22 -0400, Andrei Alexandrescu  
 <SeeWebsiteForEmail erdani.org> wrote:

 The heap is a tad difficult to tackle. Most of the time you don't want  
 to create a heap, but instead to organize an existing range as a heap.  
 As such, the heap is not always obvious to think of as a container.  
 I'm undecided on how to approach this.

it. At least for me anyway. Most of the time, once you make a range a heap, you want to continue to use it as a heap. Restricting operations on that range by defining a heap type around it can do this. Otherwise, you could accidentally do something foolish like sort the range. -Steve

But for several graph algorithms, (eg, A* pathfinding), you have {key1, key2} pairs, forming a heap based on key1, but you also need to able to search for key2. The container is a hybrid, consisting of heap on {key1} + AA on {key2}. It uses the heap operations, but it's not exactly a heap.

And such a container would be not a heap. I don't think it should be impossible to define such a construct if a vanilla heap type is also defined. My recommendation: keep the heap functions in std.algorithm and create a std.container based off them. -Steve
Jun 01 2010
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 01 Jun 2010 09:28:28 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 On 06/01/2010 07:57 AM, Steven Schveighoffer wrote:
 On Sun, 30 May 2010 18:33:22 -0400, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:


 The heap is a tad difficult to tackle. Most of the time you don't want
 to create a heap, but instead to organize an existing range as a heap.
 As such, the heap is not always obvious to think of as a container.
 I'm undecided on how to approach this.

It's easier to think of a heap as a single entity with operations on it. At least for me anyway. Most of the time, once you make a range a heap, you want to continue to use it as a heap. Restricting operations on that range by defining a heap type around it can do this. Otherwise, you could accidentally do something foolish like sort the range.

The problem is the original range is still around. void fun(Range)(Range r) if (isRandomAccessRange!Range) { auto heap = BinaryHeap!Range(r); ... use heap, but r is still there ... } This is not memory-unsafe, but may mess up the working of the heap. If the heap takes a copy of the range, that would most often be wasteful.

You can go through lengths to make sure r isn't accessible outside it's heap interface, for example, by splitting fun into two functions: void fun(Range)(Range r) if (isRandomAccessRange!Range) { auto heap = BinaryHeap!Range(r); fun2(heap); // in this function, r is not accessible. } And even without this, I can stop using r after the first line. I have a better chance of not using r in a non-heap way in that case. A heap type also may want to make a copy of the input, most other containers do. This allows it to own the storage for the data. -Steve
Jun 01 2010
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 01 Jun 2010 09:43:55 -0400, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:


 And even without this, I can stop using r after the first line.  I have  
 a better chance of not using r in a non-heap way in that case.

Note, this is similar to how immutable data must be created mutable, cast to immutable, and then you must forget the original mutable reference. -Steve
Jun 01 2010