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
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 parent reply "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
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 reply "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'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.


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
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'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.


 
 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 reply "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
next 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
prev sibling 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