Changes between Version 12 and Version 14 of Ticket #31154
- Timestamp:
- Jan 2, 2021, 10:33:14 PM (2 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
Ticket #31154
-
Property
Summary
changed from
Report distances in Breadth First Search in c_graph.pyx
toEdges and report distances in Breadth First Search in c_graph.pyx
-
Property
Summary
changed from
-
Ticket #31154 – Description
v12 v14 1 1 Currently, reporting of distances is reported in the python implementation only. We enable this in the cython implementation in `c_graph.pyx`. 2 3 Likewise for returning the edges of the BFS tree. 2 4 3 5 To compare: … … 10 12 ....: %timeit _ = list(G.breadth_first_search(start=(0, 0), report_distance=False)) 11 13 ....: %timeit _ = list(G.breadth_first_search(start=(0, 0), report_distance=True)) 14 ....: %timeit _ = list(G.breadth_first_search(start=(0, 0), edges=True)) 12 15 }}} 13 16 14 17 Before: 15 18 16 {{{ 19 {{{ 17 20 sage: comp() 18 21 2D Grid Graph for [5, 5] 19 22 5.69 µs ± 67 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 20 36.3 µs ± 67 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) 23 36.2 µs ± 411 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) 24 35.8 µs ± 465 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) 21 25 2D Grid Graph for [10, 10] 22 26 16.2 µs ± 22.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 23 143 µs ± 945 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) 27 140 µs ± 639 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) 28 138 µs ± 326 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) 24 29 2D Grid Graph for [50, 50] 25 30 492 µs ± 5.91 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 26 4.32 ms ± 48.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 31 4.15 ms ± 26 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 32 4.07 ms ± 18 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 27 33 2D Grid Graph for [100, 100] 28 34 2.68 ms ± 24.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 29 18.6 ms ± 81.1 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) 35 18.1 ms ± 41.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 36 17.9 ms ± 13.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 30 37 2D Grid Graph for [500, 500] 31 38 89.4 ms ± 665 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) 32 655 ms ± 4.93 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 39 649 ms ± 5.74 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 40 618 ms ± 7.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 33 41 2D Grid Graph for [1000, 1000] 34 42 452 ms ± 5.52 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 35 3.26 s ± 57.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 43 3.17 s ± 11.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 44 3.12 s ± 91 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 36 45 }}} 37 46 38 47 After: 39 48 {{{ 40 sage: comp() 49 sage: comp() 41 50 2D Grid Graph for [5, 5] 42 5.51 µs ± 9.43 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 43 6.11 µs ± 38.4 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 51 5.76 µs ± 7.01 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 52 6.3 µs ± 52.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 53 7.25 µs ± 19.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 44 54 2D Grid Graph for [10, 10] 45 15.7 µs ± 126 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 46 18.1 µs ± 67.9 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 55 15.5 µs ± 17.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 56 18.2 µs ± 138 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 57 21.8 µs ± 13.4 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) 47 58 2D Grid Graph for [50, 50] 48 461 µs ± 5.53 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 49 542 µs ± 3.52 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 59 461 µs ± 1.87 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 60 535 µs ± 1.61 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 61 703 µs ± 3.01 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 50 62 2D Grid Graph for [100, 100] 51 2.55 ms ± 12.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 52 3.24 ms ± 43.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 63 2.55 ms ± 12.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 64 3.19 ms ± 10.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 65 4.11 ms ± 10.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 53 66 2D Grid Graph for [500, 500] 54 86.4 ms ± 951 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) 55 156 ms ± 1.15 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) 67 86.3 ms ± 441 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) 68 159 ms ± 973 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) 69 139 ms ± 337 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) 56 70 2D Grid Graph for [1000, 1000] 57 435 ms ± 3.41 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 58 664 ms ± 4.56 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 71 456 ms ± 3.09 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 72 694 ms ± 4.35 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 73 703 ms ± 1.79 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 59 74 }}} 60 75