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: sage-7.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 chapoton

  • Branch set to u/chapoton/21345
  • Commit set to 16c8698d749ee8a5b6033e5a8a8697553c531474
  • Status changed from new to needs_review

New commits:

16c8698minor speedup in edge_labels

comment:2 Changed 3 years ago by dcoudert

  • 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 git

  • Commit changed from 16c8698d749ee8a5b6033e5a8a8697553c531474 to c3a83e06a89934456f36c49608f9408b80461c38

Branch pushed to git repo; I updated commit sha1. New commits:

c9e7169Merge branch 'u/chapoton/21345' in 7.4.b2
c3a83e0trac 21345 even better

comment:4 Changed 3 years ago by chapoton

  • Status changed from needs_work to needs_review

done, thanks

comment:5 Changed 3 years ago by dcoudert

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 git

  • Commit changed from c3a83e06a89934456f36c49608f9408b80461c38 to c62e29530213087592fecee2c82b7b17a1615a08

Branch pushed to git repo; I updated commit sha1. New commits:

c62e295trac 21345 and better yet

comment:7 Changed 3 years ago by chapoton

done, thanks again !

comment:8 Changed 3 years ago by dcoudert

  • 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 vbraun

  • 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.