Changes between Initial Version and Version 30 of Ticket #30753


Ignore:
Timestamp:
Oct 15, 2020, 9:24:45 AM (2 years ago)
Author:
gh-kliem
Comment:

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #30753

    • Property Status changed from new to needs_review
    • Property Authors changed from David Coudert to David Coudert, Jonathan Kliem
    • Property Cc gh-kliem added
    • Property Dependencies changed from to #30665, #30769
    • Property Branch changed from to public/graphs/30753_subgraph_new
    • Property Commit changed from to 40bacf03c0633affd490bac998856618879ba271

  • Ticket #30753 – Description

    initial v30  
    1 Extra speedup improvements in `subgraph` with a case forgotten in #30510. We also improve the logic in the selection of the default algorithm.
     1We add a fast method `subgraph_given_vertices` to `CGraphBackend`. This method allows fast subgraph creation including copying.
     2Also improvements in `subgraph` with a case forgotten in #30510.
     3
     4Before #30665:
     5
     6{{{
     7sage: G = graphs.Grid2dGraph(100, 100)  # dynamic sparse                                                                                                                           
     8sage: V = list(G)                                                                                                                                                                   
     9sage: %timeit H = G.subgraph(V[:50], algorithm='add')                                                                                                                               
     10280 µs ± 465 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each)
     11sage: %timeit H = G.copy()                                                                                                                                                         
     1230.3 ms ± 72.8 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
     13                                                                                                                                                                             
     14sage: G = G.copy(immutable=True)  # static sparse                                                                                                                                   
     15sage: %timeit H = G.subgraph(V[:50], algorithm='add')                                                                                                                               
     16553 µs ± 373 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each)
     17sage: %timeit H = G.copy(immutable=False)                                                                                                                                           
     1831.6 ms ± 91.6 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
     19                                                                                                                                                                               
     20sage: G = graphs.CompleteGraph(1000)  # dynamic dense                                                                                                                               
     21sage: V = list(G)                                                                                                                                                                   
     22sage: %timeit H = G.subgraph(V[:50], algorithm='add')                                                                                                                               
     2354.2 ms ± 54.6 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
     24sage: %timeit H = G.copy()                                                                                                                                                         
     25527 ms ± 663 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
     26}}}
     27
     28With #30665 and #30769:
     29
     30{{{
     31sage: G = graphs.Grid2dGraph(100, 100)  # dynamic sparse                                                                                                                                                                                                                                                                                                                   
     32sage: V = list(G)                                                                                                                                                                                                                                                                                                                                                         
     33sage: %timeit H = G.subgraph(V[:50], algorithm='add')                                                                                                                                                                                                                                                                                                                     
     34257 µs ± 356 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each)
     35sage: %timeit H = G.copy()                                                                                                                                                                                                                                                                                                                                                 
     3626.4 ms ± 146 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
     37                                                                                                                                                                                                                                                                                                                                                                     
     38sage: G = G.copy(immutable=True)  # static sparse                                                                                                                                                                                                                                                                                                                         
     39sage: %timeit H = G.subgraph(V[:50], algorithm='add')                                                                                                                                                                                                                                                                                                                     
     40521 µs ± 308 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each)
     41sage: %timeit H = G.copy(immutable=False)                                                                                                                                                                                                                                                                                                                                 
     4228.3 ms ± 95.2 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
     43
     44sage: G = graphs.CompleteGraph(1000)  # dynamic dense                                                                                                                                                                                                                                                                                                                     
     45sage: V = list(G)                                                                                                                                                                                                                                                                                                                                                         
     46sage: %timeit H = G.subgraph(V[:50], algorithm='add')                                                                                                                                                                                                                                                                                                                     
     4751.6 ms ± 64.6 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
     48sage: %timeit H = G.copy()                                                                                                                                                                                                                                                                                                                                                 
     49429 ms ± 1.23 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
     50}}}
     51
     52With this ticket:
     53
     54{{{
     55sage: G = graphs.Grid2dGraph(100, 100)  # dynamic sparse                                                                                                                                                                                                                                                                                                                                     
     56sage: V = list(G)                                                                                                                                                                                                                                                                                                                                                         
     57sage: %timeit H = G.subgraph(V[:50], algorithm='add')                                                                                                                                                                                                                                                                                                                     
     5880.9 µs ± 19.1 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
     59sage: %timeit H = G.copy()                                                                                                                                                                                                                                                                                                                                                 
     6015.4 ms ± 10.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
     61
     62sage: G = G.copy(immutable=True)  # static sparse                                                                                                                                                                                                                                                                                                                                           
     63sage: %timeit H = G.subgraph(V[:50], algorithm='add')                                                                                                                                                                                                                                                                                                                     
     64327 µs ± 1.04 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
     65sage: %timeit H = G.copy(immutable=False)                                                                                                                                                                                                                                                                                                                                 
     6620.3 ms ± 23 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
     67
     68sage: G = graphs.CompleteGraph(1000)  # dynamic dense                                                                                                                                                                                                                                                                                                                             
     69sage: V = list(G)                                                                                                                                                                                                                                                                                                                                                         
     70sage: %timeit H = G.subgraph(V[:50], algorithm='add')                                                                                                                                                                                                                                                                                                                     
     711.03 ms ± 10.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
     72sage: %timeit H = G.copy()                                                                                                                                                                                                                                                                                                                                                 
     73269 ms ± 3.08 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
     74}}}