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] <[email protected]> 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 <[email protected]>
>
>
> ------------------------------
> 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 [email protected]
> 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/Shortest-distance-complexity-when-used-with-max-dist-tp4026018p4026031.html
Sent from the Main discussion list for the graph-tool project mailing list
archive at Nabble.com._______________________________________________
graph-tool mailing list
[email protected]
http://lists.skewed.de/mailman/listinfo/graph-tool
