www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - Complex networks in D

reply "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
Following the discussion on digitalmars.D, I've put together a 
little (... er, long ...) blog post discussing the basics of my D 
graph library:
http://braingam.es/2013/07/complex-networks-in-d/

The main slant of this post is the ease of writing this stuff in 
D.  Later posts will follow up on performance issues and fill in 
some more detail about the workings of the library.

{Enj,Destr}oy :-)
Jul 15 2013
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 7/15/2013 2:32 PM, Joseph Rushton Wakeling wrote:

 Following the discussion on digitalmars.D, I've put together a little (... er,
 long ...) blog post discussing the basics of my D graph library:
 http://braingam.es/2013/07/complex-networks-in-d/

 The main slant of this post is the ease of writing this stuff in D.  Later
posts
 will follow up on performance issues and fill in some more detail about the
 workings of the library.

 {Enj,Destr}oy :-)


https://news.ycombinator.com/item?id=6050404
Jul 16 2013
parent reply "Paulo Pinto" <pjmlp progtools.org> writes:
On Tuesday, 16 July 2013 at 07:17:59 UTC, Walter Bright wrote:

 On 7/15/2013 2:32 PM, Joseph Rushton Wakeling wrote:

 Following the discussion on digitalmars.D, I've put together a 
 little (... er,
 long ...) blog post discussing the basics of my D graph 
 library:
 http://braingam.es/2013/07/complex-networks-in-d/

 The main slant of this post is the ease of writing this stuff 
 in D.  Later posts
 will follow up on performance issues and fill in some more 
 detail about the
 workings of the library.

 {Enj,Destr}oy :-)


 https://news.ycombinator.com/item?id=6050404


http://www.reddit.com/r/programming/comments/1iegj9/complex_networks_in_d/
Jul 16 2013
parent reply "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Tuesday, 16 July 2013 at 08:27:07 UTC, Paulo Pinto wrote:

 On Tuesday, 16 July 2013 at 07:17:59 UTC, Walter Bright wrote:

 https://news.ycombinator.com/item?id=6050404


 http://www.reddit.com/r/programming/comments/1iegj9/complex_networks_in_d/


Thanks! :-)
Jul 16 2013
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 7/16/2013 2:27 AM, Joseph Rushton Wakeling wrote:

 On Tuesday, 16 July 2013 at 08:27:07 UTC, Paulo Pinto wrote:

 On Tuesday, 16 July 2013 at 07:17:59 UTC, Walter Bright wrote:

 https://news.ycombinator.com/item?id=6050404


 http://www.reddit.com/r/programming/comments/1iegj9/complex_networks_in_d/


 Thanks! :-)


People are much more likely to read your article from links in reddit and 
hackernews if you put in as a comment some description of it. Don't wait for 
others to do it for you! They may mischaracterize it, or worse, the opportunity 
will slip by.
Jul 16 2013
parent "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Tuesday, 16 July 2013 at 18:22:31 UTC, Walter Bright wrote:

 People are much more likely to read your article from links in 
 reddit and hackernews if you put in as a comment some 
 description of it. Don't wait for others to do it for you! They 
 may mischaracterize it, or worse, the opportunity will slip by.


Done.  Thanks for the advice!
Jul 16 2013
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Joseph Rushton Wakeling:


 http://braingam.es/2013/07/complex-networks-in-d/


     size_t vertexCount()  property const pure nothrow
     {
         assert(_sumHead.length == _sumTail.length);
         return _sumHead.length - 1;
     }

Is that better written in a struct/class invariant?


         size_t degreeIn(immutable size_t v) const pure nothrow
         {
             assert(v + 1 < _sumTail.length);
             return _sumTail[v + 1] - _sumTail[v];
         }

Here you are looking for the method pre-condition.

And "in size_t v" is enough compared to "immutable size_t v".


auto neighbours(immutable size_t v) const
{
     return chain(map!(a => 
_tail[_indexHead[a]])(iota(_sumHead[v], _sumHead[v + 1])),
     map!(a => _head[_indexTail[a]])(iota(_sumTail[v], _sumTail[v 
+ 1])));
}

For such kind of code I suggest to use UFCS chains.
Also be careful with the performance of such range-based code, 
writing benchmarks. Unfortunately often DMD doesn't compile it 
efficiently.

Bye,
bearophile
Jul 16 2013
parent reply "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Tuesday, 16 July 2013 at 14:18:02 UTC, bearophile wrote:

     size_t vertexCount()  property const pure nothrow
     {
         assert(_sumHead.length == _sumTail.length);
         return _sumHead.length - 1;
     }

 Is that better written in a struct/class invariant?


Nice thought -- probably; it's a condition that must always hold.


         size_t degreeIn(immutable size_t v) const pure nothrow
         {
             assert(v + 1 < _sumTail.length);
             return _sumTail[v + 1] - _sumTail[v];
         }

 Here you are looking for the method pre-condition.


Ahh, you mean inside in { ... } brackets?  I did consider writing 
it like that.  It wasn't clear to me what the benefits were, 
though, especially as I did consider making this an enforce() 
rather than an assert().


 And "in size_t v" is enough compared to "immutable size_t v".


Does "in" allow for subsequent mutation _within_ the function?


 For such kind of code I suggest to use UFCS chains.


Can you explain in a little more detail?  It's not an aspect of 
programming I'm familiar with.


 Also be careful with the performance of such range-based code, 
 writing benchmarks. Unfortunately often DMD doesn't compile it 
 efficiently.


Yes, this is a concern of mine too.  In benchmarks I've carried 
out, the calls to e.g. neighbours() take up a substantial chunk 
of the overall runtime -- but that said, the number of calls to 
them is very, very large.  It works out as on the order of 
between 1e-9 and 1e-8 seconds per call.

These kinds of range-based solutions seem to be a part of D where 
LDC typically produces the best performance.  But I would not use 
DMD for serious number crunching of any kind -- as it stands it 
can't match either of the other two compilers.

Anyway, thanks very much for the useful feedback :-)
Jul 16 2013
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Joseph Rushton Wakeling:


 It wasn't clear to me what the benefits were, though,


For this function not a lot, but it's a good habit to have.



 especially as I did consider making this an enforce() rather 
 than an assert().


If you want to use enforce then don't put them in pre-conditions.
But usually asserts should suffice.



 And "in size_t v" is enough compared to "immutable size_t v".


 Does "in" allow for subsequent mutation _within_ the function?


"in" implies scoped const. So you can't mutate the argument 
inside the function/method. For reference types "immutable" is 
even stronger.



 For such kind of code I suggest to use UFCS chains.


 Can you explain in a little more detail?  It's not an aspect of 
 programming I'm familiar with.


auto r1 = iota(_sumHead[v], _sumHead[v + 1]).map!(a => 
_tail[_indexHead[a]]);
auto r2 = iota(_sumTail[v], _sumTail[v + 1]).map!(a => 
_head[_indexTail[a]]);
return chain(r1, r2);



 Anyway, thanks very much for the useful feedback :-)


You are welcome,
bye,
bearophile
Jul 16 2013
parent reply "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Tuesday, 16 July 2013 at 15:57:06 UTC, bearophile wrote:

 For such kind of code I suggest to use UFCS chains.


 Can you explain in a little more detail?  It's not an aspect 
 of programming I'm familiar with.


 auto r1 = iota(_sumHead[v], _sumHead[v + 1]).map!(a => 
 _tail[_indexHead[a]]);
 auto r2 = iota(_sumTail[v], _sumTail[v + 1]).map!(a => 
 _head[_indexTail[a]]);
 return chain(r1, r2);


Ahh, OK.  To be sure I understand what you're getting at, is it 
just that it's more elegant to write it this way (I agree:-), or 
is there a performance benefit in the iota().map!() form (or to 
separately generating the ranges and then chaining them)?
Jul 16 2013
parent "bearophile" <bearophileHUGS lycos.com> writes:
Joseph Rushton Wakeling:


 To be sure I understand what you're getting at, is it just that 
 it's more elegant to write it this way (I agree:-), or is there 
 a performance benefit in the iota().map!() form (or to 
 separately generating the ranges and then chaining them)?


It's just more readable.

Bye,
bearophile
Jul 16 2013