Hello,
Firstly thanks for pushing in this update as quickly, that's awesome. I tested your fix, It seems that the vector initialization was not the only to blame. With the fix the execution time is still around 300ms.
I checked that you're fix is used, and "timed" the execution of the *shortest_distance* function up to the call to *libgraph_tool_topology.get_dists*.
In the "sub-sample" graph:
- the initialization takes in average 3ms; - the the call to libgraph_tool_topology.get_dists takes in average 11ms.
In the full graph:
- the initialization takes in average 100ms; - the call to libgraph_tool_topology.get_dists takes in average 230ms.
Surprisingly (or not ?) when I change the pmap initialization [link to source https://git.skewed.de/count0/graph-tool/blob/master/src/graph_tool/topology/__init__.py#L1248] to:
vals = numpy.arange(g.num_vertices(), dtype='int') pmap = g.new_vertex_property("int64_t", vals=vals)
The numpy call takes 36ms and creation of the new vertex property takes 103ms.
Best, François.
Le lun. 9 mars 2015 à 16:25, Tiago Peixoto [via Main discussion list for the graph-tool project] ml-node+s982480n4026030h87@n3.nabble.com a écrit :
On 09.03.2015 12:26, François wrote:
Thanks for these clarifications.
I guess that most of the time is spent in the *copy_property* [link to
git https://git.skewed.de/count0/graph-tool/blob/master/src/ graph/graph_properties_copy.cc#L33]. Indeed, when I provide a pre-initialized distance vector through the dist_map parameter, the execution of shortest_distance is only 10ms faster.
If I understood well, the *copy_property *is used to build a vector
initialized with one single value. If so, one would obtain the same result with python and numpy with
x = np.empty(array_size, dtype=float) x.fill(value)
I did try to time this "numpy way initialization" (altough I'm not sure
it corresponds to *copy_property*)
python -m timeit -s "import numpy as np" -n 100 "np.empty(33e6,
dtype=int).fill(1)"
100 loops, best of 3: 34.9 msec per loop
These**34.9ms have to be compared to the 300ms (bake of envelope
calculus) that takes the *copy_property *function.
Am I right about the way that the copy_property function works ? Could
it be improved ? PropertyMap.copy() is slower than a simple numpy initialization because it needs to deal with possible conversions between the values (such as converting from string to double). However, it is possible to include a specialization that avoids this conversion when the types are the same. I have now included this modification in the git version, which significantly improves the time it takes to copy a property without conversion.
Best, Tiago
-- Tiago de Paula Peixoto <[hidden email] http:///user/SendEmail.jtp?type=node&node=4026030&i=0>
graph-tool mailing list [hidden email] http:///user/SendEmail.jtp?type=node&node=4026030&i=1 http://lists.skewed.de/mailman/listinfo/graph-tool
*signature.asc* (836 bytes) Download Attachment
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/attachment/4026030/0/signature.asc
Tiago de Paula Peixoto tiago@skewed.de
If you reply to this email, your message will be added to the discussion below: http://main-discussion-list-for-the-graph-tool-project. 982480.n3.nabble.com/Shortest-distance-complexity-when-used-with-max-dist- tp4026018p4026030.html To start a new topic under Main discussion list for the graph-tool project, email ml-node+s982480n2141189h16@n3.nabble.com To unsubscribe from Shortest_distance complexity when used with max_dist, click here http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=4026018&code=ZnJhbmNvaXMua2F3YWxhQGdtYWlsLmNvbXw0MDI2MDE4fDIxMTQ0MDk4Nzk= . NAML http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml
-- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.