That's great to hear, and thanks for letting us know the outcome.
--Tim
On Thursday, June 04, 2015 04:59:44 PM Seth wrote:
> 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.
