I found some info related to the dictionary lookup: [" https://wiki.python.org/moin/TimeComplexity";]
The worst case scenario is O(n). Does this sound right? Thanks very much for the help, -Ahmed On Mon, Jan 5, 2015 at 4:25 PM, Ahmed Abdeen Hamed <[email protected]> wrote: > Thanks you, Dr. Nepusz! > > I did mean the Python implementation yes. If this is the case, what the > runtime complexity for 2 vertices if we use g.vs.find("name")? I am > asking because I have designed a new algorithm that uses this feature. The > runtime analysis is needed for a publication and I am trying to be as > accurate as possible. > > Thanks again! > > -Ahmed > > > > On Mon, Jan 5, 2015 at 4:16 PM, Tamas Nepusz <[email protected]> wrote: > >> Hi, >> >> > What the runtime analysis for retrieving the index of a node by its >> name? >> >> It depends. If you are using the C core directly, you are on your own -- >> looking up a vertex by name would involve scanning the vertices and >> comparing >> their name attribute with the name you are looking for. Or you can >> implement >> your own data structure (e.g., a hash table) to speed up the lookups. If >> you >> are using the Python interface, the situation is a bit better because the >> "name" attribute is indexed behind the scenes so looking up a vertex by >> name >> should be as fast as a Python dictionary lookup. (But watch out for a >> caveat: >> g.vs.find("name") is fast but g.vs.find(name="name") is slow; this is a >> bug >> that will be rectified soon). I cannot tell anything about the R >> interface, >> though, because I'm not familiar with its internals. >> >> -- >> T. >> >> _______________________________________________ >> igraph-help mailing list >> [email protected] >> https://lists.nongnu.org/mailman/listinfo/igraph-help >> > >
_______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
