Changes between Initial Version and Version 2 of Ticket #31117


Ignore:
Timestamp:
Dec 27, 2020, 5:55:18 PM (2 years ago)
Author:
dcoudert
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #31117

    • Property Status changed from new to needs_review
    • Property Commit changed from to a19e27645d4c621f223a93245347a2472ee21a56
    • Property Branch changed from to public/graphs/31117_BFS
  • Ticket #31117 – Description

    initial v2  
    5959}}}
    6060
    61 A possible improvement is to avoid using `in_neighbors` and `out_neighbors` since these methods return lists of vertices and behind we have some mallocs of arrays. So a lot of operations that could be avoided.
     61Another improvement is to avoid using `in_neighbors` and `out_neighbors` since these methods return lists of vertices and behind we have some mallocs of arrays. So a lot of operations that could be avoided. We get significant speed up even on small graphs.
     62{{{
     63sage: comp()                                                                                                                                       
     642D Grid Graph for [5, 5]
     659.93 µs ± 350 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
     6657.3 µs ± 1.62 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
     672D Grid Graph for [10, 10]
     6831.3 µs ± 1.67 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
     69230 µs ± 11.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
     702D Grid Graph for [50, 50]
     71881 µs ± 22.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
     727.26 ms ± 269 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
     732D Grid Graph for [100, 100]
     743.84 ms ± 203 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
     7531.3 ms ± 1.5 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
     762D Grid Graph for [500, 500]
     77120 ms ± 2.65 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
     781.05 s ± 25.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
     792D Grid Graph for [1000, 1000]
     80644 ms ± 18.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
     815.26 s ± 279 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
     82}}}