very minor speedup in edge_labels

[fchapoton]

by creating the list directly

Component: graph theory

Author: Frédéric Chapoton

Branch/Commit: c62e295

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/21345

[fchapoton]

Commit: 16c8698

[fchapoton]

New commits:

16c8698

minor speedup in edge_labels

[fchapoton]

Branch: u/chapoton/21345

[dcoudert]

comment:2

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

[sagetrac-git]

Changed commit from 16c8698 to c3a83e0

[sagetrac-git]

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

c9e7169	Merge branch 'u/chapoton/21345' in 7.4.b2
c3a83e0	trac 21345 even better

[fchapoton]

comment:4

done, thanks

[dcoudert]

comment:5

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

[sagetrac-git]

Changed commit from c3a83e0 to c62e295

[sagetrac-git]

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

c62e295

trac 21345 and better yet

[fchapoton]

comment:7

done, thanks again !

[dcoudert]

comment:8

We can certainly do better accessing directly the backends, but we already have a significant speed up.
Good to go.

[dcoudert]

Reviewer: David Coudert

[vbraun]

Changed branch from u/chapoton/21345 to c62e295