Re: Re: Re: Complexity of method Graph::getNode(String id)

[guilhelm savin <guilhelm.savin AT gmail.com>]

You can easily manipulate a big graph of about 1 million nodes in such that the access time will not be significant. But it depends of your needs of course : nodes count, and access count.

I make some benchmark on my laptop (2.60GHz CPU) over a 1million nodes graph, and the average access time, for one node, is about 1µs, vs. 3ns with indexes.

2013/12/4 <simone.davico AT usi.ch>

You're right, it's a stupid idea.

My problem is that the graph is static, but when I have to retrieve a node I
don't know what the index of the node is, I only know what is its ID in the
case that the node is present.

The graph could be very huge, as I am performing instrumentation of Java
bytecode, and the nodes are representing methods. For reasons I'm not
explaining because it would take too long, it could be possible that some
methods I encounter are not in the graph, so before taking action I have to
ensure that they are by calling getNode(methodID), where ID is a unique String
based on the method signature.

Honestly I can't think of a way of knowing in advance what the corresponding
index for my ID would be, so I'm probably forced to keep complexity O(n).

--
Guilhelm Savin
PhD Student of Computer Science

LITIS, University of Le Havre
\/\/\/\/\/\/

http://gsavin.lewub.org

http://d3-project.org
http://iscn.univ-lehavre.fr
http://graphstream-project.org
/\/\/\/\/\/\