On 29.06.2017 11:58, François Kawala wrote: > On my typical ~7e6 vertices graph, for a typical search that reach about 1e5 > vertices, the improvement is about 20%. We have 83ms (average over 100 runs) > for the 2.22 release versus 69ms for commit bf174831. Interestingly, the > bf174831 version is more stable with std = 4ms versus 6ms for the 2.22 > release.
I wonder how much time is spent in the actual search vs. initialization. If you use something like cProfile you can see how much time is spent in the actual C++ function vs. the rest. This would give us an idea of how much actual improvement can be done. > What I understand from the boost thread > <https://groups.google.com/forum/#%21topic/boost-list/7nCzvkkEXCk> is that > we could have only initialization for the whole lifespan of the program. If > I get it right, their proposal would, prior to a search, to "re-set" the > values from distances vector and predecessors vector only for the reached > vertices of the last search. I think it worth a try because, from what I > timed the python side of initialization could cost around 18ms (5ms for > distance map, 13ms for predecessor map) see timeit snipet below. In order for this to work, the function would need to keep and return a list of reached vertices. This is is not difficult to do, but I wonder how much it would actually improve... Best, Tiago -- Tiago de Paula Peixoto <[email protected]>
signature.asc
Description: OpenPGP digital signature
_______________________________________________ graph-tool mailing list [email protected] https://lists.skewed.de/mailman/listinfo/graph-tool
