www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - std.collection lets rename it into std,ridiculous.

reply bls <bizprac orange.fr> writes:
Hi
What's  the problem to implement some very basic containers ?
And No !! Don't waste time to tell about built in Arrays and Associative 
arrays, I am following D for at 5 years now..

What I definitely don't get is
queues, stacks and dequeues, and also specialized kind of  stacks/queues 
  don't depend on ranges. Why we don't habe them.
Everybody, using D for serious purposes, is creating home brewed stuff.

But fuc da duc..

the whole Range collection stuff is completely undefined.

All we know right now is that Algorithms are working on 
data-structures. (Pretty new, beside)

//First incarnation ..
public class Deque(T)
{
     private class Node()
     {
         T _value;
         Node _previous;
         Node _next
     }
}
Yep..
should be

final public class Deque(T)
{
}

We are still not there ..
struct Node()

final class Deque(T, alias allocator)
{
}
// Let's range-i-fy it ... and here we are

final class Deque(T, alias allocator) : IXXXRange|T
{
  // push and pop without sense.. what is enqueue now ?
}

Shit. all I want is a generique Queue

The std.collection situation is a shame,
Bjoern
Feb 19 2012
next sibling parent reply "Yao Gomez" <yao.gomez gmail.com> writes:
On Sunday, 19 February 2012 at 22:55:05 UTC, bls wrote:
 Hi
 What's  the problem to implement some very basic containers ?
 And No !! Don't waste time to tell about built in Arrays and 
 Associative arrays, I am following D for at 5 years now..

 What I definitely don't get is
 queues, stacks and dequeues, and also specialized kind of  
 stacks/queues
  don't depend on ranges. Why we don't habe them.
 Everybody, using D for serious purposes, is creating home 
 brewed stuff.

 But fuc da duc..

 the whole Range collection stuff is completely undefined.

 All we know right now is that Algorithms are working on 
 data-structures. (Pretty new, beside)

 //First incarnation ..
 public class Deque(T)
 {
     private class Node()
     {
         T _value;
         Node _previous;
         Node _next
     }
 }
 Yep..
 should be

 final public class Deque(T)
 {
 }

 We are still not there ..
 struct Node()

 final class Deque(T, alias allocator)
 {
 }
 // Let's range-i-fy it ... and here we are

 final class Deque(T, alias allocator) : IXXXRange|T
 {
  // push and pop without sense.. what is enqueue now ?
 }

 Shit. all I want is a generique Queue

 The std.collection situation is a shame,
 Bjoern

Eagerly waiting your contribution, preferably through a pull request, to remedy this unfortunate situation.
Feb 19 2012
next sibling parent bls <bizprac orange.fr> writes:
On 02/19/2012 03:40 PM, Yao Gomez wrote:
 Eagerly waiting your contribution, preferably through a pull request, to
 remedy this unfortunate situation.

OK, Will do. All I need is guide to Range-Interfaces. (and a good reason why I should iterate over stacks and queues) But wait. Despite that : Are final classes the way to go ? I don't know. Is it written in the sand or is it the new golden rule ? What about the allocator ? Who knows... But shit isn't dcollections showing the way how to implement flex. allocator on demand. ? You know it. Everybody is able to contribute to std.collections. But thanks to the ignorance here and there, std. collection is still a joke. Period. Bjoern
Feb 19 2012
prev sibling parent bls <bizprac orange.fr> writes:
On 02/19/2012 03:40 PM, Yao Gomez wrote:
 agerly waiting your contribution, preferably through a pull request, to
 remedy this unfortunate situation.

Still waiting for an answer.. Show me the Quality assurance table for collections. This can't be difficult for You, since yoy know how to design it.. And finally there is SList, Still En Voque ?
Feb 19 2012
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, February 19, 2012 02:05:18 bls wrote:
 Hi
 What's  the problem to implement some very basic containers ?
 And No !! Don't waste time to tell about built in Arrays and Associative
 arrays, I am following D for at 5 years now..

std.container is where containers/collection go. The main reason that we don't have more is that Andrei is working on the design for custom allocators which will have a definite impact on the containers. So, rather than create a bunch of container types which are going to have to be redone later, we just don't have very many. At least we have _something_ now (it was quite a while before we got std.container), and much of the basics of how containers are supposed to look like and work have been ironed out, but the allocator situation is proving to be a roadblock. However, not very long ago, Andrei said something about having a breakthrough in his work on the allocator design, so we may be seeing custom allocators - and thus more containers - fairly soon. - Jonathan M Davis
Feb 19 2012
prev sibling next sibling parent reply "Bernard Helyer" <b.helyer gmail.com> writes:
Maybe when you learn to type like an adult people will listen to 
you?
Feb 19 2012
next sibling parent reply bls <bizprac orange.fr> writes:
On 02/19/2012 04:05 PM, Bernard Helyer wrote:
 Maybe when you learn to type like an adult people will listen to you?

Facts, that's what I am are talking about. If you don't like my speak ...sorry. My point is that D2 needs asap a working container/collection lib (and I think the "How to allocate/de-allocate" question becomes more and more ridiculous. That Stuff is meanwhile library based.. Typedef f.i.) So why not plug- in an allocator. ?
Feb 19 2012
next sibling parent reply bls <bizprac orange.fr> writes:
On 02/19/2012 04:48 PM, Bernard Helyer wrote:
 On Monday, 20 February 2012 at 00:29:20 UTC, bls wrote:
 On 02/19/2012 04:05 PM, Bernard Helyer wrote:
 Maybe when you learn to type like an adult people will listen to you?

Facts, that's what I am are talking about. If you don't like my speak ...sorry. My point is that D2 needs asap a working container/collection lib (and I think the "How to allocate/de-allocate" question becomes more and more ridiculous. That Stuff is meanwhile library based.. Typedef f.i.) So why not plug- in an allocator. ?

When you use words on the internet people judge you based on your words. There's more to proposals than technical merits, and if you don't understand that that's fine, but don't be surprised when people dismiss you quickly. People filter information because they have to -- they'll take any excuse to ignore you. Don't make it _easy_ for them.

Mo excuse. Be assured, and there is no doubt that I will name shit SHIT. I live in a free country. Any substantial feedback ?
Feb 19 2012
next sibling parent bcs <bcs example.com> writes:
On 02/19/2012 04:21 AM, bls wrote:
 Any substantial feedback ?

http://docs.python.org/tutorial/datastructures.html#using-lists-as-stacks
Feb 19 2012
prev sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 02/20/2012 06:30 AM, James Miller wrote:
 On 20 February 2012 16:43, H. S. Teoh<hsteoh quickfur.ath.cx>  wrote:
 On Mon, Feb 20, 2012 at 04:19:10PM +1300, James Miller wrote:
 [...]
 My feedback is that for most people's purposes, associative arrays and
 arrays (dynamic and static) are fine. PHP doesn't have a well-used
 collections library (though it does exist) but it is used by millions
 of sites every day. I don't normally need an explicit
 queue/stack/priority queue.

The convenience and flexibility of D's arrays have, for the most part, replaced my need for explicit stacks or queues. For example, here's a stack: T[] stack; void push(elem) { stack ~= elem; } T pop() { T elem = stack[$-1]; stack = stack[0..$-1]; return elem; } Here's a queue: T[] queue; void enqueue(elem) { queue ~= elem; } T dequeue() { T elem = queue[0]; queue = queue[1..$]; return elem; } It's so trivial to implement that it's hardly worth the effort to implement a class for it. Your mileage may vary, though. T

The cool thing about that implementation is that, by using slices, you generally avoid allocation, unless its neccessary.

As far the queue is concerned. The stack implementation misses an assumeSafeAppend and will reallocate unnecessarily.
Feb 20 2012
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Mon, Feb 20, 2012 at 07:42:07PM +0100, a wrote:
But if you only access it via push() and pop(), then there are no
other references to the stack, so why should the GC reallocate it
on append?

Because the GC doesn't know there aren't any other references to it unless you tell it with assumeSafeAppend.

Ahh, I see. Thanks! T -- Being able to learn is a great learning; being able to unlearn is a greater learning.
Feb 20 2012
prev sibling next sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Monday, February 20, 2012 11:40:40 H. S. Teoh wrote:
 On Mon, Feb 20, 2012 at 07:42:07PM +0100, a wrote:
But if you only access it via push() and pop(), then there are no
other references to the stack, so why should the GC reallocate it
on append?

Because the GC doesn't know there aren't any other references to it unless you tell it with assumeSafeAppend.

Ahh, I see. Thanks!

Nick ran into this problem and ended up writing an article on it: https://www.semitwist.com/articles/article/view/don-t-use-arrays-as-stacks And, of course, if you haven't read Steven's article on arrays, you should read that: http://www.dsource.org/projects/dcollections/wiki/ArrayArticle In fact, we really should get Steven's article up on dlang.org. It's one of those articles that _every_ D programmer should read. - Jonathan M Davis
Feb 20 2012
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/20/12 1:45 PM, Jonathan M Davis wrote:
 In fact, we really should get Steven's article up on dlang.org. It's one of
 those articles that _every_ D programmer should read.

Pull request before we forget about that please. Thanks, Andrei
Feb 20 2012
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, February 20, 2012 14:55:36 Andrei Alexandrescu wrote:
 On 2/20/12 1:45 PM, Jonathan M Davis wrote:
 In fact, we really should get Steven's article up on dlang.org. It's one
 of
 those articles that _every_ D programmer should read.

Pull request before we forget about that please.

Steven's the one with the actual article though. He's going to have to do it. The best that any of the rest of us can do is copy the HTML over. If it's anything like the other articles on dlang.org, it was generated using ddoc, and that's what we'd want to commit to the repository. - Jonathan M Davis
Feb 20 2012
prev sibling next sibling parent Brad Anderson <eco gnuk.net> writes:
--f46d043089b486782104b96bd1de
Content-Type: text/plain; charset=ISO-8859-1

On Mon, Feb 20, 2012 at 1:55 PM, Andrei Alexandrescu <
SeeWebsiteForEmail erdani.org> wrote:

 On 2/20/12 1:45 PM, Jonathan M Davis wrote:

 In fact, we really should get Steven's article up on dlang.org. It's one
 of
 those articles that _every_ D programmer should read.

Pull request before we forget about that please. Thanks, Andrei

Where does an article like that go? It seems like the D website is missing a "Concepts" section with high level descriptions of certain core features. The language reference is too low level for most beginners. The Articles section doesn't feel right to me (I wouldn't think to check there to figure out how slices or ranges work). Perhaps add a Concepts section, move the appropriate articles over from Articles, and keep Articles around for interesting topics that wouldn't belong in Concepts (like Don's floating point article, most of the iPad contest entries, and this "don't use arrays as stacks article"). Another great article for a Concepts section would be the recent book excerpt on ranges that was released a month or two ago (if the author would allow it). Ranges are painfully undocumented (I only had an understanding of them because I had watched Andrei's BoostCon talk). Regards, Brad Anderson --f46d043089b486782104b96bd1de Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable On Mon, Feb 20, 2012 at 1:55 PM, Andrei Alexandrescu <span dir=3D"ltr">&lt;= <a href=3D"mailto:SeeWebsiteForEmail erdani.org">SeeWebsiteForEmail erdani.= org</a>&gt;</span> wrote:<br><div class=3D"gmail_quote"><blockquote class= =3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padd= ing-left:1ex"> <div class=3D"im">On 2/20/12 1:45 PM, Jonathan M Davis wrote:<br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex"> In fact, we really should get Steven&#39;s article up on <a href=3D"http://= dlang.org" target=3D"_blank">dlang.org</a>. It&#39;s one of<br> those articles that _every_ D programmer should read.<br> </blockquote> <br></div> Pull request before we forget about that please.<br> <br> Thanks,<br> <br> Andrei<br> </blockquote></div><br><div>Where does an article like that go? =A0It seems= like the D website is missing a &quot;Concepts&quot; section with high lev= el descriptions of certain core features. =A0The language reference is too = low level for most beginners. =A0The Articles section doesn&#39;t feel righ= t to me (I wouldn&#39;t think to check there to figure out how slices or ra= nges work). =A0Perhaps add a Concepts section, move the appropriate article= s over from Articles, and keep Articles around for interesting topics that = wouldn&#39;t belong in Concepts (like Don&#39;s floating point article, mos= t of the iPad contest entries, and this &quot;don&#39;t use arrays as stack= s article&quot;).</div> <div><br></div><div>Another great article for a Concepts section would be t= he recent book excerpt on ranges that was released a month or two ago (if t= he author would allow it). =A0Ranges are painfully undocumented (I only had= an understanding of them because I had watched Andrei&#39;s BoostCon talk)= .</div> <div><br></div><div>Regards,</div><div>Brad Anderson</div> --f46d043089b486782104b96bd1de--
Feb 20 2012
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 20 Feb 2012 16:03:19 -0500, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:

 On Monday, February 20, 2012 14:55:36 Andrei Alexandrescu wrote:
 On 2/20/12 1:45 PM, Jonathan M Davis wrote:
 In fact, we really should get Steven's article up on dlang.org. It's  

 of
 those articles that _every_ D programmer should read.

Pull request before we forget about that please.

Steven's the one with the actual article though. He's going to have to do it. The best that any of the rest of us can do is copy the HTML over. If it's anything like the other articles on dlang.org, it was generated using ddoc, and that's what we'd want to commit to the repository.

I'm sorry, I promised to do this a long time ago. When I have time to pay attention to D again (I've been super-busy at work and home for the last 2 weeks), this is the first thing I will do. It's generated using TRAC Wiki, it should be pretty trivial to convert to ddoc. -Steve
Feb 24 2012
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Friday, February 24, 2012 11:34:11 Steven Schveighoffer wrote:
 I'm sorry, I promised to do this a long time ago. When I have time to pay
 attention to D again (I've been super-busy at work and home for the last 2
 weeks), this is the first thing I will do.
 
 It's generated using TRAC Wiki, it should be pretty trivial to convert to
 ddoc.

Just so long as it's not forgotten. We all get busy. I haven't had as much time for D lately either, and there are some Phobos things that I definitely need to get back to and get done. - Jonathan M Davis
Feb 24 2012
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 24 Feb 2012 11:34:11 -0500, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:

 On Mon, 20 Feb 2012 16:03:19 -0500, Jonathan M Davis  
 <jmdavisProg gmx.com> wrote:

 On Monday, February 20, 2012 14:55:36 Andrei Alexandrescu wrote:
 On 2/20/12 1:45 PM, Jonathan M Davis wrote:
 In fact, we really should get Steven's article up on dlang.org. It's  

 of
 those articles that _every_ D programmer should read.

Pull request before we forget about that please.

Steven's the one with the actual article though. He's going to have to do it. The best that any of the rest of us can do is copy the HTML over. If it's anything like the other articles on dlang.org, it was generated using ddoc, and that's what we'd want to commit to the repository.

I'm sorry, I promised to do this a long time ago. When I have time to pay attention to D again (I've been super-busy at work and home for the last 2 weeks), this is the first thing I will do.

As promised: https://github.com/D-Programming-Language/d-programming-language.org/pull/97 And now I'm finally caught up in the newsgroup! -Steve
Mar 05 2012
prev sibling next sibling parent James Miller <james aatch.net> writes:
On 6 March 2012 14:15, Steven Schveighoffer <schveiguy yahoo.com> wrote:
 On Fri, 24 Feb 2012 11:34:11 -0500, Steven Schveighoffer
 <schveiguy yahoo.com> wrote:

 On Mon, 20 Feb 2012 16:03:19 -0500, Jonathan M Davis <jmdavisProg gmx.co=


 wrote:

 On Monday, February 20, 2012 14:55:36 Andrei Alexandrescu wrote:
 On 2/20/12 1:45 PM, Jonathan M Davis wrote:
 In fact, we really should get Steven's article up on dlang.org. It's
 one
 of
 those articles that _every_ D programmer should read.

Pull request before we forget about that please.

Steven's the one with the actual article though. He's going to have to =



 it.
 The best that any of the rest of us can do is copy the HTML over. If it=



 anything like the other articles on dlang.org, it was generated using
 ddoc,
 and that's what we'd want to commit to the repository.

I'm sorry, I promised to do this a long time ago. =C2=A0When I have time=


 attention to D again (I've been super-busy at work and home for the last=


 weeks), this is the first thing I will do.

As promised: https://github.com/D-Programming-Language/d-programming-language.org/pull=

 And now I'm finally caught up in the newsgroup!

 -Steve

Awesome work Steve, your original article was brilliant, clearly explained how D arrays and slices work without out segueing into other topics, which tends to happen with these kinds of articles. -- James Miller
Mar 05 2012
prev sibling next sibling parent "F i L" <witte2008 gmail.com> writes:
Jonathan M Davis wrote:
 Nick ran into this problem and ended up writing an article on 
 it:

 https://www.semitwist.com/articles/article/view/don-t-use-arrays-as-stacks

 And, of course, if you haven't read Steven's article on arrays, 
 you should
 read that:

 http://www.dsource.org/projects/dcollections/wiki/ArrayArticle

 In fact, we really should get Steven's article up on dlang.org. 
 It's one of
 those articles that _every_ D programmer should read.

 - Jonathan M Davis

I didn't know about array.reserve() and array.capacity! Is there any other undocumented methods? Like capacityStep maybe?
Mar 05 2012
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday, March 06, 2012 04:59:42 F i L wrote:
 Jonathan M Davis wrote:
 Nick ran into this problem and ended up writing an article on
 it:
 
 https://www.semitwist.com/articles/article/view/don-t-use-arrays-as-stacks
 
 And, of course, if you haven't read Steven's article on arrays,
 you should
 read that:
 
 http://www.dsource.org/projects/dcollections/wiki/ArrayArticle
 
 In fact, we really should get Steven's article up on dlang.org.
 It's one of
 those articles that _every_ D programmer should read.
 
 - Jonathan M Davis

I didn't know about array.reserve() and array.capacity! Is there any other undocumented methods? Like capacityStep maybe?

They _are_ documented: http://dlang.org/phobos/object.html Though I can see why people would miss them. - Jonathan M Davis
Mar 05 2012
prev sibling next sibling parent "F i L" <witte2008 gmail.com> writes:
Jonathan M Davis wrote:
 They _are_ documented:

 http://dlang.org/phobos/object.html

 Though I can see why people would miss them.

I see. That's odd, though. What are array (specific?) methods doing in the Object base class?
Mar 05 2012
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday, March 06, 2012 06:06:54 F i L wrote:
 Jonathan M Davis wrote:
 They _are_ documented:
 
 http://dlang.org/phobos/object.html
 
 Though I can see why people would miss them.

I see. That's odd, though. What are array (specific?) methods doing in the Object base class?

They're _not_ in the Object base class. They're just in the same file - just like Throwable and Exception are (though oddly, those two aren't documented). It makes it so that you don't have to import anything to use them. They're _always_ available. - Jonathan M Davis
Mar 05 2012
prev sibling parent "F i L" <witte2008 gmail.com> writes:
Jonathan M Davis wrote:
 They're _not_ in the Object base class. They're just in the 
 same file - just
 like Throwable and Exception are (though oddly, those two 
 aren't documented).
 It makes it so that you don't have to import anything to use 
 them. They're
 _always_ available.

Makes sense, thanks for the explanation.
Mar 05 2012
prev sibling parent bls <bizprac orange.fr> writes:
On 02/19/2012 04:20 PM, James Miller wrote:
 On 20 February 2012 13:05, Bernard Helyer<b.helyer gmail.com>  wrote:
 Maybe when you learn to type like an adult people will listen to you?

Its also worth mentioning that most structures are simple enough that for 99% of purposes, a "homebrew" implementation is fine. I was taught how to implement a queue and a stack at the same times as using it, that is how simple some of these containers are. And if you need massive speed, then you probably wouldn't use generic containers anyway...

Sure thing.. for a while, What if you have to manage a bigger piece of software, 20 peiple project . Would nt it be better to use a "default container" having a dedicated interface. Sanity wise ? -- But this is not my point. I think that std.container/collection is a shame (to whom it may concern)
Feb 19 2012
prev sibling next sibling parent James Miller <james aatch.net> writes:
On 20 February 2012 13:05, Bernard Helyer <b.helyer gmail.com> wrote:
 Maybe when you learn to type like an adult people will listen to you?

Its also worth mentioning that most structures are simple enough that for 99% of purposes, a "homebrew" implementation is fine. I was taught how to implement a queue and a stack at the same times as using it, that is how simple some of these containers are. And if you need massive speed, then you probably wouldn't use generic containers anyway...
Feb 19 2012
prev sibling next sibling parent "Bernard Helyer" <b.helyer gmail.com> writes:
On Monday, 20 February 2012 at 00:29:20 UTC, bls wrote:
 On 02/19/2012 04:05 PM, Bernard Helyer wrote:
 Maybe when you learn to type like an adult people will listen 
 to you?

Facts, that's what I am are talking about. If you don't like my speak ...sorry. My point is that D2 needs asap a working container/collection lib (and I think the "How to allocate/de-allocate" question becomes more and more ridiculous. That Stuff is meanwhile library based.. Typedef f.i.) So why not plug- in an allocator. ?

When you use words on the internet people judge you based on your words. There's more to proposals than technical merits, and if you don't understand that that's fine, but don't be surprised when people dismiss you quickly. People filter information because they have to -- they'll take any excuse to ignore you. Don't make it _easy_ for them.
Feb 19 2012
prev sibling next sibling parent "Yao Gomez" <yao.gomez gmail.com> writes:
On Monday, 20 February 2012 at 01:01:16 UTC, bls wrote:
 On 02/19/2012 03:40 PM, Yao Gomez wrote:
 agerly waiting your contribution, preferably through a pull 
 request, to
 remedy this unfortunate situation.

Still waiting for an answer.. Show me the Quality assurance table for collections. This can't be difficult for You, since yoy know how to design it.. And finally there is SList, Still En Voque ?

You are the one getting all emotional about the std.ridiculous module. Besides, where do yoy (ha!) get that I know how to design it? Strawman too much?
Feb 19 2012
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/19/12 4:05 AM, bls wrote:
[snip
 The std.collection situation is a shame,

I understand your frustration, and you are entitled to it. This std.container situation has gone on forever. It's all my fault. I know what to do, but work and family put great demands on my time, and I find it very difficult to focus on good design in the bits and pieces of time I have left. A quick and dirty set of containers will unfortunately not help. Such designs have inevitably caused more problems for us than they solved (xml, json come to mind). We need to do the right thing. Andrei
Feb 19 2012
next sibling parent reply Derek <ddparnell bigpond.com> writes:
On Mon, 20 Feb 2012 14:05:07 +1100, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 We need to do the right thing.

Do we? Really? That takes sooo loooong it encourages many home-baked-reinvented-wheels that might very well end up taking more time and effort from the community than incrementally creating a standard set of containers. Does it really matter if our initial efforts for some of the expected data structures are less than 'The Right Thing'? If they meet 80%+ of our requirements and continue to evolve towards perfection, I'm pretty sure the community could cope with a NQR product for now. -- Derek Parnell Melbourne, Australia
Feb 20 2012
parent Jason <lowe tricom.org> writes:
D as in Development Hell.
Feb 20 2012
prev sibling parent "a" <a a.com> writes:
On Monday, 20 February 2012 at 10:44:03 UTC, Derek wrote:
 On Mon, 20 Feb 2012 14:05:07 +1100, Andrei Alexandrescu 
 <SeeWebsiteForEmail erdani.org> wrote:

 We need to do the right thing.

Do we? Really? That takes sooo loooong it encourages many home-baked-reinvented-wheels that might very well end up taking more time and effort from the community than incrementally creating a standard set of containers. Does it really matter if our initial efforts for some of the expected data structures are less than 'The Right Thing'? If they meet 80%+ of our requirements and continue to evolve towards perfection, I'm pretty sure the community could cope with a NQR product for now.

You could use dcollections ( http://www.dsource.org/projects/dcollections ) if you need something now.
Feb 20 2012
prev sibling next sibling parent James Miller <james aatch.net> writes:
 When you use words on the internet people judge you based on your words.
 There's more to proposals than technical merits, and if you don't
 understand that that's fine, but don't be surprised when people dismiss
 you quickly. People filter information because they have to -- they'll
 take any excuse to ignore you. Don't make it _easy_ for them.

Mo excuse. Be assured, and there is no doubt =C2=A0that I will name shit =

 live in a free country.
 Any substantial feedback ?

However, claiming such a thing only lowers peoples opinion of you. Other people that use the "I live in a free country" defense include thugs that intimidate people and teenagers disagreeing with their parents. If that is your only defense, then you clearly don't have a defined reason for holding your opinion. As for your writing, it is obvious that you are french, however, that does not excuse 1) casual mixing languages in writing, you might speak like that, but this isn't verbal conversation. 2) rudeness. Bad manners are bad manners, regardless of language and 3) not proofreading, a few typos here and there are ok, especially if English is not your first language, but you don't even punctuate properly, and I /know/ that French has the same punctuation rules as any other Latin-derived language. My feedback is that for most people's purposes, associative arrays and arrays (dynamic and static) are fine. PHP doesn't have a well-used collections library (though it does exist) but it is used by millions of sites every day. I don't normally need an explicit queue/stack/priority queue. James Miller
Feb 19 2012
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Mon, Feb 20, 2012 at 04:19:10PM +1300, James Miller wrote:
[...]
 My feedback is that for most people's purposes, associative arrays and
 arrays (dynamic and static) are fine. PHP doesn't have a well-used
 collections library (though it does exist) but it is used by millions
 of sites every day. I don't normally need an explicit
 queue/stack/priority queue.

The convenience and flexibility of D's arrays have, for the most part, replaced my need for explicit stacks or queues. For example, here's a stack: T[] stack; void push(elem) { stack ~= elem; } T pop() { T elem = stack[$-1]; stack = stack[0..$-1]; return elem; } Here's a queue: T[] queue; void enqueue(elem) { queue ~= elem; } T dequeue() { T elem = queue[0]; queue = queue[1..$]; return elem; } It's so trivial to implement that it's hardly worth the effort to implement a class for it. Your mileage may vary, though. T -- Some ideas are so stupid that only intellectuals could believe them. -- George Orwell
Feb 19 2012
prev sibling next sibling parent James Miller <james aatch.net> writes:
On 20 February 2012 16:43, H. S. Teoh <hsteoh quickfur.ath.cx> wrote:
 On Mon, Feb 20, 2012 at 04:19:10PM +1300, James Miller wrote:
 [...]
 My feedback is that for most people's purposes, associative arrays and
 arrays (dynamic and static) are fine. PHP doesn't have a well-used
 collections library (though it does exist) but it is used by millions
 of sites every day. I don't normally need an explicit
 queue/stack/priority queue.

The convenience and flexibility of D's arrays have, for the most part, replaced my need for explicit stacks or queues. For example, here's a stack: =C2=A0 =C2=A0 =C2=A0 =C2=A0T[] stack; =C2=A0 =C2=A0 =C2=A0 =C2=A0void push(elem) { =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0stack ~=3D elem; =C2=A0 =C2=A0 =C2=A0 =C2=A0} =C2=A0 =C2=A0 =C2=A0 =C2=A0T pop() { =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0T elem =3D stack[$=

 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0stack =3D stack[0.=

 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0return elem;
 =C2=A0 =C2=A0 =C2=A0 =C2=A0}

 Here's a queue:

 =C2=A0 =C2=A0 =C2=A0 =C2=A0T[] queue;
 =C2=A0 =C2=A0 =C2=A0 =C2=A0void enqueue(elem) {
 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0queue ~=3D elem;
 =C2=A0 =C2=A0 =C2=A0 =C2=A0}
 =C2=A0 =C2=A0 =C2=A0 =C2=A0T dequeue() {
 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0T elem =3D queue[0=

 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0queue =3D queue[1.=

 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0return elem;
 =C2=A0 =C2=A0 =C2=A0 =C2=A0}

 It's so trivial to implement that it's hardly worth the effort to
 implement a class for it.

 Your mileage may vary, though.


 T

The cool thing about that implementation is that, by using slices, you generally avoid allocation, unless its neccessary.
Feb 19 2012
prev sibling next sibling parent "a" <a a.com> writes:
 here's a
 stack:

 	T[] stack;
 	void push(elem) {
 		stack ~= elem;
 	}
 	T pop() {
 		T elem = stack[$-1];
 		stack = stack[0..$-1];
 		return elem;
 	}

Won't this reallocate every time you pop an element and then push a new one?
Feb 20 2012
prev sibling next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Mon, Feb 20, 2012 at 09:33:51AM +0100, a wrote:
here's a stack:

	T[] stack;
	void push(elem) {
		stack ~= elem;
	}
	T pop() {
		T elem = stack[$-1];
		stack = stack[0..$-1];
		return elem;
	}

Won't this reallocate every time you pop an element and then push a new one?

Nope, it doesn't. That's the power of D slices. When you create a dynamic array, the GC allocates a certain amount of memory, let's call it a "page", and sets the array to point to the beginning of this memory. When you append to this array, it simply uses up more of this memory. No reallocation actually occurs until the page is used up, at which point the GC allocates a larger page to store the array in. This scheme means that this code is very efficient for small stacks, because there's no repeated allocation/deallocation (which if you ever played with malloc/free, you'd know are expensive), just updating a few pointers. For large stacks, the reallocations only take place occasionally, so even in that case performance is still pretty good. T -- If you want to solve a problem, you need to address its root cause, not just its symptoms. Otherwise it's like treating cancer with Tylenol...
Feb 20 2012
parent reply "Daniel Murphy" <yebblies nospamgmail.com> writes:
"H. S. Teoh" <hsteoh quickfur.ath.cx> wrote in message 
news:mailman.666.1329752861.20196.digitalmars-d puremagic.com...
 Won't this reallocate every time you pop an element and then push a
 new one?

Nope, it doesn't. That's the power of D slices. When you create a dynamic array, the GC allocates a certain amount of memory, let's call it a "page", and sets the array to point to the beginning of this memory. When you append to this array, it simply uses up more of this memory. No reallocation actually occurs until the page is used up, at which point the GC allocates a larger page to store the array in. This scheme means that this code is very efficient for small stacks, because there's no repeated allocation/deallocation (which if you ever played with malloc/free, you'd know are expensive), just updating a few pointers. For large stacks, the reallocations only take place occasionally, so even in that case performance is still pretty good.

This is incorrect. eg: T[] stack = new immutable(int)[](20); stack ~= 3; // probably does it in place auto stack2 = stack[]; // take a slice of the full stack stack = stack[0..$-1]; // ok, take a slice stack ~= 7; // must reallocate to avoid overwriting immutable memory Try it out, it works the same with mutable elements.
Feb 20 2012
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/20/12 10:13 AM, Daniel Murphy wrote:
 "H. S. Teoh"<hsteoh quickfur.ath.cx>  wrote in message
 news:mailman.666.1329752861.20196.digitalmars-d puremagic.com...
 Won't this reallocate every time you pop an element and then push a
 new one?

Nope, it doesn't. That's the power of D slices. When you create a dynamic array, the GC allocates a certain amount of memory, let's call it a "page", and sets the array to point to the beginning of this memory. When you append to this array, it simply uses up more of this memory. No reallocation actually occurs until the page is used up, at which point the GC allocates a larger page to store the array in. This scheme means that this code is very efficient for small stacks, because there's no repeated allocation/deallocation (which if you ever played with malloc/free, you'd know are expensive), just updating a few pointers. For large stacks, the reallocations only take place occasionally, so even in that case performance is still pretty good.

This is incorrect. eg: T[] stack = new immutable(int)[](20); stack ~= 3; // probably does it in place auto stack2 = stack[]; // take a slice of the full stack stack = stack[0..$-1]; // ok, take a slice stack ~= 7; // must reallocate to avoid overwriting immutable memory Try it out, it works the same with mutable elements.

Yah, assumeSafeAppend() needs to be used in the stack implementation. I don't know how we can address this better. Andrei
Feb 20 2012
prev sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Monday, February 20, 2012 10:34:20 Andrei Alexandrescu wrote:
 On 2/20/12 10:13 AM, Daniel Murphy wrote:
 "H. S. Teoh"<hsteoh quickfur.ath.cx> wrote in message
 news:mailman.666.1329752861.20196.digitalmars-d puremagic.com...
 
 Won't this reallocate every time you pop an element and then push a
 new one?

[..] Nope, it doesn't. That's the power of D slices. When you create a dynamic array, the GC allocates a certain amount of memory, let's call it a "page", and sets the array to point to the beginning of this memory. When you append to this array, it simply uses up more of this memory. No reallocation actually occurs until the page is used up, at which point the GC allocates a larger page to store the array in. This scheme means that this code is very efficient for small stacks, because there's no repeated allocation/deallocation (which if you ever played with malloc/free, you'd know are expensive), just updating a few pointers. For large stacks, the reallocations only take place occasionally, so even in that case performance is still pretty good.

This is incorrect. eg: T[] stack = new immutable(int)[](20); stack ~= 3; // probably does it in place auto stack2 = stack[]; // take a slice of the full stack stack = stack[0..$-1]; // ok, take a slice stack ~= 7; // must reallocate to avoid overwriting immutable memory Try it out, it works the same with mutable elements.

Yah, assumeSafeAppend() needs to be used in the stack implementation. I don't know how we can address this better.

The reality of the matter is that you need to understand how arrays work in D in order to use them efficiently. And for something like a stack or a queue, you really should use a wrapper. Yes, D arrays are extremely powerful, but that doesn't mean that you won't need to wrap them in a container type for some types of usage, just like you'd wrap an array in many other languages. - Jonathan M Davis
Feb 20 2012
prev sibling next sibling parent "a" <a a.com> writes:
 Nope, it doesn't. That's the power of D slices. When you create 
 a
 dynamic array, the GC allocates a certain amount of memory, 
 let's call
 it a "page", and sets the array to point to the beginning of 
 this
 memory. When you append to this array, it simply uses up more 
 of this
 memory. No reallocation actually occurs until the page is used 
 up, at
 which point the GC allocates a larger page to store the array 
 in.

Yes, it does. When you take a slice of an array and then append an element to it, the slice has to be reallocated or the element in the original array after the end of the slice would be modified. For example: auto a = [1,2,3,4,5]; auto b = a[0..3]; b ~= 0; writeln(a); If b was not reallocated, the code above would print [1, 2, 3, 0, 5], which is probably not what one would expect. This would cause problems if a function took array as a parameter and then appended to it. If you passed an array slice to such function you would have a non-deterministic bug - when the appending would cause reallocation, everything would be okay, but when it wouldn't, the function would modifiy the array outside of the slice that was passed to it. Arrays in D used to work like that IIRC. Someone in this thread mentioned that you should use assumeSafeAppend for stack implementation (I did not know about assumeSafeAppend before that). The following code: auto a = [1,2,3,4,5]; auto b = a[0..3]; assumeSafeAppend(b); b ~= 0; writeln(a); prints [1, 2, 3, 0, 5], so b is not reallocated in this case.
Feb 20 2012
prev sibling next sibling parent "a" <a a.com> writes:
 auto a = [1,2,3,4,5];
 auto b = a[0..3];
 assumeSafeAppend(b);
 b ~= 0;
 writeln(a);

 prints [1, 2, 3, 0, 5], so b is not reallocated in this case.

Just to clarify: this is not guaranteed to print [1, 2, 3, 0, 5], it only does if there is still enough memory in a block allocated to b and it doesn't have to be reallocated.
Feb 20 2012
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Mon, Feb 20, 2012 at 05:16:17PM +0100, a wrote:
Nope, it doesn't. That's the power of D slices. When you create a
dynamic array, the GC allocates a certain amount of memory, let's
call it a "page", and sets the array to point to the beginning of
this memory. When you append to this array, it simply uses up more of
this memory. No reallocation actually occurs until the page is used
up, at which point the GC allocates a larger page to store the array
in.

Yes, it does. When you take a slice of an array and then append an element to it, the slice has to be reallocated or the element in the original array after the end of the slice would be modified.

I know that. But we're implementing a stack here. The stack slice is the only thing that refers to that part of the memory. The reallocation only happens if you start making external references to elements/slices on the stack. But if you only access it via push() and pop(), then there are no other references to the stack, so why should the GC reallocate it on append? T -- Государство делает вид, что платит нам зарплату, а мы делаем вид, что работаем.
Feb 20 2012
prev sibling next sibling parent "a" <a a.com> writes:
 But if you only access it via push() and pop(), then there are 
 no other references to the stack, so why should the GC 
 reallocate it on append?

Because the GC doesn't know there aren't any other references to it unless you tell it with assumeSafeAppend.
Feb 20 2012
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 20 Feb 2012 11:22:32 -0500, a <a a.com> wrote:

 auto a = [1,2,3,4,5];
 auto b = a[0..3];
 assumeSafeAppend(b);
 b ~= 0;
 writeln(a);

 prints [1, 2, 3, 0, 5], so b is not reallocated in this case.

Just to clarify: this is not guaranteed to print [1, 2, 3, 0, 5], it only does if there is still enough memory in a block allocated to b and it doesn't have to be reallocated.

In fact, it is guaranteed. a is guaranteed to be allocated on the heap, because that's what an array literal does (currently, but it probably shouldn't be). It's guaranteed to be inserted into a block large enough to hold 5 numbers, so you definitely can put 4 numbers (1, 2, 3, 0) into it. This will never reallocate. However, It's not guaranteed that the last number will be 5 after assumeSafeAppend is called. Once you call assumeSafeAppend, all data after that last element is invalid (i.e. not used). To refer to that data is implementation-defined. E.g. a different version of assumeSafeAppend may set all invalid bytes to 0, or some other sentinel value. -Steve
Feb 24 2012