Implementing and optimizing a simple graph metric
Joseph Rushton Wakeling
joseph.wakeling at webdrake.net
Thu Sep 19 01:59:43 PDT 2013
On Wednesday, 18 September 2013 at 17:13:28 UTC, bearophile wrote:
> How many times or how often do you need to call betweenness()?
> If it's called only few times or once in a while then using the
> GC is good enough. But if you have to call it many millions of
> times, all those GC array allocations could cost some time,
> even if they are small arrays. In this case allocating them on
> the stack (or not allocating them, using externally allocated
> buffers) helps.
I think millions of times is excessive. In my test code I have an
example with a 50-node network calculating betweenness centrality
10000 times, which takes under 1.5 seconds. So obviously if you
scale up to millions, small improvements could make a difference,
but it's not going to be on such a scale that it's worth
prioritizing, at least for now. I think even 10000 calculations
is excessive for any practical case I can think of.
You're right to call for the opportunity to pass a buffer,
though, and I've enabled that. In the current test code it
doesn't seem to improve anything, but that may be simply a matter
More information about the Digitalmars-d-announce