Tim,
Thank you very much. I didn't realized there were heaps in Collections.
I've tested them and they're much faster / memory efficient than either of
the ones in DataStructures:
julia> g = readgraph("/Users/seth/Downloads/pgp2.jgz")
{39796, 301498} directed graph
julia> @time z = betweenness_centrality(g);
1238 seconds (3769 M allocations: 272 GB, 18.38% gc time)
This means that betweenness centrality in LightGraphs is on par with igraph
and faster than graph-tool, which is a huge deal.
Thanks again!
On Thursday, June 4, 2015 at 2:34:01 PM UTC-7, Tim Holy wrote:
>
> My default answer to such questions is to suggest profiling (I don't
> really
> know/remember the DataStructures code very well).
>
> You can also try the binary heap in Base.Collections. I've not compared
> them
> directly.
>
> Best,
> --Tim
>
> On Thursday, June 04, 2015 12:43:34 PM Seth wrote:
> > I created an issue
> > <https://github.com/JuliaLang/DataStructures.jl/issues/95> in
> > DataStructures.jl but was unsure whether or not that was the right
> > approach. In any case, I'll restate the question here with apologies for
> > any inappropriate duplication.
> >
> > I've been using mutable_binary_minheap for a Dijkstra calculation and am
> > getting reasonable performance for betweenness centrality (which
> basically
> > does all-pairs Dijkstra) in a large graph:
> >
> > julia> g = readgraph("/Users/seth/Downloads/pgp2.jgz")
> > {39796, 301498} directed graph # {number of vertices, number of edges}
> > julia> @time z = betweenness_centrality(g);
> > 1426 seconds (3768 M allocations: 328 GB, 21.91% gc time)
> >
> > Realizing that I really didn't need the mutability (I'm just push!ing
> and
> > pop!ping), I switched over to binary_minheap, thinking that I'd get at
> > least the same, but possibly better, performance. However:
> >
> > julia> @time z = betweenness_centrality(g);
> > 1743 seconds (8469 M allocations: 385 GB, 28.40% gc time
> >
> > These results are repeatable (I ran each test 3 times in clean
> > environments).
> >
> > Why would binary_minheap be so much slower than its mutable counterpart,
> > and why would it require more than twice the number of allocations (note
> > that the amount of memory allocated is also different, but maybe not
> > significantly so)?
> >
> > Thanks for any assistance / insight.
>
>
