Opened 3 years ago
Closed 3 years ago
#21345 closed enhancement (fixed)
very minor speedup in edge_labels
Reported by:  chapoton  Owned by:  

Priority:  minor  Milestone:  sage7.4 
Component:  graph theory  Keywords:  
Cc:  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  c62e295 (Commits)  Commit:  c62e29530213087592fecee2c82b7b17a1615a08 
Dependencies:  Stopgaps: 
Description
by creating the list directly
Change History (9)
comment:1 Changed 3 years ago by
 Branch set to u/chapoton/21345
 Commit set to 16c8698d749ee8a5b6033e5a8a8697553c531474
 Status changed from new to needs_review
comment:2 Changed 3 years ago by
 Status changed from needs_review to needs_work
We can easily do better.
Previous code:
sage: G = graphs.PetersenGraph() sage: %timeit G.edge_labels() The slowest run took 5.12 times longer than the fastest. This could mean that an intermediate result is being cached. 100000 loops, best of 3: 11.9 µs per loop sage: G = graphs.Grid2dGraph(50,50) sage: %timeit G.edge_labels() 100 loops, best of 3: 6.98 ms per loop
Your code (almost the same):
sage: G = graphs.PetersenGraph() sage: %timeit G.edge_labels() The slowest run took 4.17 times longer than the fastest. This could mean that an intermediate result is being cached. 100000 loops, best of 3: 11.8 µs per loop sage: G = graphs.Grid2dGraph(50,50) sage: %timeit G.edge_labels() 100 loops, best of 3: 6.8 ms per loop
using instead return list(l for _,_,l in self.edge_iterator())
seems more efficient.
sage: G = graphs.PetersenGraph() sage: %timeit G.edge_labels() 100000 loops, best of 3: 10.1 µs per loop sage: G = graphs.Grid2dGraph(50,50) sage: %timeit G.edge_labels() 100 loops, best of 3: 2.81 ms per loop
comment:3 Changed 3 years ago by
 Commit changed from 16c8698d749ee8a5b6033e5a8a8697553c531474 to c3a83e06a89934456f36c49608f9408b80461c38
comment:5 Changed 3 years ago by
Hello. It is much better to use edge_iterator
. We don't need to build the list of edges first and then iterate over that list.
sage: G = graphs.Grid2dGraph(50,50) sage: %timeit [l for _, _, l in G.edges()] 100 loops, best of 3: 7.59 ms per loop sage: %timeit [l for _, _, l in G.edge_iterator()] 100 loops, best of 3: 3.34 ms per loop
comment:6 Changed 3 years ago by
 Commit changed from c3a83e06a89934456f36c49608f9408b80461c38 to c62e29530213087592fecee2c82b7b17a1615a08
Branch pushed to git repo; I updated commit sha1. New commits:
c62e295  trac 21345 and better yet

comment:7 Changed 3 years ago by
done, thanks again !
comment:8 Changed 3 years ago by
 Reviewers set to David Coudert
 Status changed from needs_review to positive_review
We can certainly do better accessing directly the backends, but we already have a significant speed up. Good to go.
comment:9 Changed 3 years ago by
 Branch changed from u/chapoton/21345 to c62e29530213087592fecee2c82b7b17a1615a08
 Resolution set to fixed
 Status changed from positive_review to closed
Note: See
TracTickets for help on using
tickets.
New commits:
minor speedup in edge_labels