Changes between Initial Version and Version 7 of Ticket #10885


Ignore:
Timestamp:
Mar 11, 2011, 4:51:06 AM (12 years ago)
Author:
ncohen
Comment:

Greaaaaat !! Thank you for your help ! I still have many tricks to learn :-)

Passes all tests, does its job even faster... Niiiiice !

Nathann

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #10885

    • Property Cc jason rlm mvngu added
    • Property Status changed from new to positive_review
    • Property Authors changed from Nathann Cohen to Nathann Cohen, Yann Laigle-Chapuy
    • Property Reviewers changed from to Nathann Cohen, Yann Laigle-Chapuy

  • Ticket #10885 – Description

    initial v7  
    22
    33The performance improvement is obvious for the ``all_pairs_shortest_path`` method which used by default the Python implementation
    4 {{{
    5 sage: g = graphs.PetersenGraph()
    6 sage: %timeit g.shortest_path_all_pairs()
    7 625 loops, best of 3: 555 µs per loop
    8 sage: %timeit g.shortest_path_all_pairs(by_weight=True)
    9 125 loops, best of 3: 6.44 ms per loop
    10 sage: g = graphs.Grid2dGraph(5,5)
    11 sage: %timeit g.shortest_path_all_pairs()
    12 125 loops, best of 3: 3.77 ms per loop
    13 sage: %timeit g.shortest_path_all_pairs(by_weight=True)
    14 5 loops, best of 3: 133 ms per loop
    15 sage: g = graphs.Grid2dGraph(15,15)
    16 sage: %timeit g.shortest_path_all_pairs()
    17 5 loops, best of 3: 753 ms per loop
    18 sage: %timeit g.shortest_path_all_pairs(by_weight=True)
    19 (still running)
    20 }}}
     4
     5
     6
    217The new implementation is now the default.
    228