[Haskell-cafe] Inductive graphs memory usage
oddron at gmail.com
Thu Jul 10 18:32:38 EDT 2008
On Thu, Jul 10, 2008 at 4:57 PM, Andre Nathan <andre at digirati.com.br> wrote:
> I'm trying to create a directed graph using the Data.Graph.Inductive.
> The graph is a random graph using the G(n, p) model, that is, each of
> the n nodes is linked to every other node with probability p.
So the average degree of a single node is p * n, and the expected
number of edges in the entire graph will grow as O(n ^2).
> I'm seeing a large increase of memory usage when n grows (this is using
> p = 0.1):
> n = 1000 -> 96MB
> n = 2000 -> 283MB
> n = 3000 -> 760MB
> So, I'm probably doing something very stupid :)
Your ratios are about 1 : 3 : 8.
That pretty close to quadratic growth, 1 : 4 : 9, so I think all is well.
More information about the Haskell-Cafe