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 <tiago@skewed.de>