Re: The Upper Limit of Perl's Native Data Structures

...graphs with ~3000 nodes and ~1.5million edges.

Building a graph with Graph::Directed doesn't put all the edges into one big hash. It creates an adjacency list for each vertex, so the size of each individual hash should only be about equal to the number of vertices. A 3000-element hash should be no problem, unless you're looking for trouble.

As I insert this large graph into the Graph::Directed module I note what appears to be an exponential slowdown as I insert edges.

I don't see a slowdown until the graph gets big enough to fill available ram and start swapping, so it sounds like tye is right. Graph::Directed's graph representation is designed to be flexible rather than compact. To handle big graphs, you might need to use a different representation.

does anyone know the big-O notation complexity of inserting edges and nodes into the data structures used by Graph::Directed

It looks like it should be close enough to O(n) as to make no difference.

Aside to Abigail: Ha ha, but exp($n/1_000_000) is still exponential.

Comment on Re: The Upper Limit of Perl's Native Data Structures

Replies are listed 'Best First'.
Re: The Upper Limit of Perl's Native Data Structures by Abigail-II (Bishop) on May 21, 2003 at 18:48 UTC
Aside to Abigail: Ha ha, but exp($n/1_000_000) is still exponential. And you think the OP noticed that? Abigail	[reply]
Re: Re: The Upper Limit of Perl's Native Data Structures by no_slogan (Deacon) on May 21, 2003 at 19:25 UTC
And you think the OP noticed that? Yes. It sounds to me like he ran a series of tests that looked something like this: `edges time --------- ----- 500_000 1 min 1_000_000 2 min 1_500_000 4 min` [download] And he recognized that as an exponential progression. In any case, there's no cause for making snide remarks about what he did or didn't notice.	[reply] [d/l]