Changes between Version 12 and Version 14 of Ticket #31154


Ignore:
Timestamp:
Jan 2, 2021, 10:33:14 PM (2 years ago)
Author:
gh-kliem
Comment:

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #31154

    • Property Summary changed from Report distances in Breadth First Search in c_graph.pyx to Edges and report distances in Breadth First Search in c_graph.pyx

  • Ticket #31154 – Description

    v12 v14  
    11Currently, reporting of distances is reported in the python implementation only. We enable this in the cython implementation in `c_graph.pyx`.
     2
     3Likewise for returning the edges of the BFS tree.
    24
    35To compare:
    … …  
    1012....:         %timeit _ = list(G.breadth_first_search(start=(0, 0), report_distance=False))
    1113....:         %timeit _ = list(G.breadth_first_search(start=(0, 0), report_distance=True))
     14....:         %timeit _ = list(G.breadth_first_search(start=(0, 0), edges=True))
    1215}}}
    1316
    1417Before:
    1518
    16 {{{                                                                                                                                                                         
     19{{{ 
    1720sage: comp()                                                                                                                                                                                                                                                                                                                                                               
    18212D Grid Graph for [5, 5]
    19225.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)
     2336.2 µs ± 411 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
     2435.8 µs ± 465 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
    21252D Grid Graph for [10, 10]
    222616.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)
     27140 µs ± 639 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
     28138 µs ± 326 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
    24292D Grid Graph for [50, 50]
    2530492 µ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)
     314.15 ms ± 26 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
     324.07 ms ± 18 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
    27332D Grid Graph for [100, 100]
    28342.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)
     3518.1 ms ± 41.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
     3617.9 ms ± 13.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
    30372D Grid Graph for [500, 500]
    313889.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)
     39649 ms ± 5.74 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
     40618 ms ± 7.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
    33412D Grid Graph for [1000, 1000]
    3442452 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)
     433.17 s ± 11.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
     443.12 s ± 91 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
    3645}}}
    3746
    3847After:
    3948{{{
    40 sage: comp()                                                                                                                                                                                                                                                                                                                                                               
     49sage: comp()
    41502D 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)
     515.76 µs ± 7.01 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
     526.3 µs ± 52.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
     537.25 µs ± 19.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
    44542D 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)
     5515.5 µs ± 17.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
     5618.2 µs ± 138 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
     5721.8 µs ± 13.4 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
    47582D 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)
     59461 µs ± 1.87 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
     60535 µs ± 1.61 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
     61703 µs ± 3.01 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
    50622D 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)
     632.55 ms ± 12.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
     643.19 ms ± 10.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
     654.11 ms ± 10.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
    53662D 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)
     6786.3 ms ± 441 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
     68159 ms ± 973 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
     69139 ms ± 337 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
    56702D 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)
     71456 ms ± 3.09 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
     72694 ms ± 4.35 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
     73703 ms ± 1.79 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
    5974}}}
    6075