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] to:
The numpy call takes 36ms and creation of the new vertex property takes 103ms.vals = numpy.arange(g.num_vertices(), dtype='int')pmap = g.new_vertex_property("int64_t", vals=vals)
Best,
François.
Le lun. 9 mars 2015 à 16:25, Tiago Peixoto [via Main discussion list for the graph-tool project] <[hidden email]> 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.PropertyMap.copy() is slower than a simple numpy initialization because>
> Am I right about the way that the copy_property function works ? Could it be improved ?
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]>
_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool
--
Tiago de Paula Peixoto <[hidden email]>
If you reply to this email, your message will be added to the discussion below:To start a new topic under Main discussion list for the graph-tool project, email [hidden email]
To unsubscribe from Shortest_distance complexity when used with max_dist, click here.
NAML
signature.asc (836 bytes)