Implementing and optimizing a simple graph metric

[Joseph Rushton Wakeling]

On Wednesday, 18 September 2013 at 15:17:25 UTC, Joseph Rushton 
Wakeling wrote:
> I think I did give std.array.Array a trial when trying to speed 
> up its performance, and I don't remember it making any 
> difference (if anything it may have slowed things down).  But 
> I'll give it a second look and report back.

I tried rewriting the variable declarations:

     Array!T centrality;
     centrality.length = g.vertexCount;
     centrality[] = to!T(0);
     Array!size_t stack;
     stack.length = g.vertexCount;
     Array!T sigma;
     sigma.length = g.vertexCount;
     Array!T delta;
     delta.length = g.vertexCount;
     Array!long d;
     d.length = g.vertexCount;
     auto q = VertexQueue(g.vertexCount);
     Appender!(size_t[])[] p = new 
Appender!(size_t[])[g.vertexCount];

It results in a moderate slowdown of the code, at a guess because 
it increases the total number of mallocs/deallocs.

I note that there seems to be no way to initialize 
std.container.Array as having a certain length ... ?

I tried instead using std.array.uninitializedArray to initialize 
the arrays in the betweenness() function -- it was a bit 
difficult to judge here: with a relatively small number of calls 
to betweenness() it seems to have resulted in a speedup, but with 
very many calls, it seems to have been slower.