Changes between Version 3 and Version 4 of Ticket #28895


Ignore:
Timestamp:
12/19/19 06:25:07 (2 years ago)
Author:
gh-kliem
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #28895 – Description

    v3 v4  
    66
    77-  #28896: Graphs: Move common methods of backends to CGraph
    8 -  #28897: BipartiteGraph blindly trusts generic graphs
     8-  #28897: BipartiteGraph blindly trusts generic graphs
     9
     10Here are some timings we try to improve along the way:
     11
     12{{{
     13sage: def test_speed(n):
     14....:     for struct in ('dense', 'sparse'):
     15....:         print("\nnow doing {}".format(struct))
     16....:         G = Graph(n, data_structure=struct)
     17....:         edges = itertools.combinations(range(n), 2)
     18....:         print("adding edges")
     19....:         %time G.add_edges(edges)
     20....:         print("copy to dense")
     21....:         %time _ = copy(G)
     22....:         print("copy to sparse")
     23....:         %time _ = G.copy(sparse=True)
     24....:         print("copy to statice sparse")
     25....:         %time H = G.copy(immutable=True)
     26....:         edges = itertools.combinations(range(n), 2)
     27....:         print("delete edges")
     28....:         %time G.delete_edges(edges)
     29....:     
     30....:         print("copying static sparse to {}".format(struct))
     31....:         %time _ = H.copy(data_structure=struct)
     32....:   
     33}}}
     34{{{
     35sage: test_speed(1000)
     36
     37now doing dense
     38adding edges
     39CPU times: user 169 ms, sys: 4 µs, total: 169 ms
     40Wall time: 169 ms
     41copy to dense
     42CPU times: user 2.14 s, sys: 0 ns, total: 2.14 s
     43Wall time: 2.14 s
     44copy to sparse
     45CPU times: user 2.44 s, sys: 0 ns, total: 2.44 s
     46Wall time: 2.44 s
     47copy to statice sparse
     48CPU times: user 2.75 s, sys: 3.61 ms, total: 2.75 s
     49Wall time: 2.75 s
     50delete edges
     51CPU times: user 613 ms, sys: 0 ns, total: 613 ms
     52Wall time: 613 ms
     53copying static sparse to dense
     54CPU times: user 282 ms, sys: 0 ns, total: 282 ms
     55Wall time: 282 ms
     56
     57now doing sparse
     58adding edges
     59CPU times: user 434 ms, sys: 0 ns, total: 434 ms
     60Wall time: 435 ms
     61copy to dense
     62CPU times: user 619 ms, sys: 0 ns, total: 619 ms
     63Wall time: 619 ms
     64copy to sparse
     65CPU times: user 747 ms, sys: 3.84 ms, total: 750 ms
     66Wall time: 750 ms
     67copy to statice sparse
     68CPU times: user 997 ms, sys: 0 ns, total: 997 ms
     69Wall time: 997 ms
     70delete edges
     71CPU times: user 896 ms, sys: 0 ns, total: 896 ms
     72Wall time: 896 ms
     73copying static sparse to sparse
     74CPU times: user 582 ms, sys: 0 ns, total: 582 ms
     75Wall time: 582 ms
     76}}}
     77{{{
     78sage: test_speed(2000)
     79
     80now doing dense
     81adding edges
     82CPU times: user 672 ms, sys: 0 ns, total: 672 ms
     83Wall time: 671 ms
     84copy to dense
     85CPU times: user 16.1 s, sys: 0 ns, total: 16.1 s
     86Wall time: 16.1 s
     87copy to sparse
     88CPU times: user 17.4 s, sys: 34.7 ms, total: 17.5 s
     89Wall time: 17.5 s
     90copy to statice sparse
     91CPU times: user 18.9 s, sys: 51.6 ms, total: 18.9 s
     92Wall time: 18.9 s
     93delete edges
     94CPU times: user 2.49 s, sys: 0 ns, total: 2.49 s
     95Wall time: 2.49 s
     96copying static sparse to dense
     97CPU times: user 1.18 s, sys: 0 ns, total: 1.18 s
     98Wall time: 1.18 s
     99
     100now doing sparse
     101adding edges
     102CPU times: user 1.87 s, sys: 0 ns, total: 1.87 s
     103Wall time: 1.87 s
     104copy to dense
     105CPU times: user 2.64 s, sys: 0 ns, total: 2.64 s
     106Wall time: 2.64 s
     107copy to sparse
     108CPU times: user 3.21 s, sys: 47.8 ms, total: 3.26 s
     109Wall time: 3.26 s
     110copy to statice sparse
     111CPU times: user 4.25 s, sys: 36 ms, total: 4.28 s
     112Wall time: 4.28 s
     113delete edges
     114CPU times: user 3.86 s, sys: 0 ns, total: 3.86 s
     115Wall time: 3.86 s
     116copying static sparse to sparse
     117CPU times: user 2.55 s, sys: 0 ns, total: 2.55 s
     118Wall time: 2.55 s
     119}}}