py3: replacing some .vertices() by .vertex_iterator()

[fchapoton]

mainly inside loops.

• This is faster
• This does not sort the vertices

Inspired by ##22349

Found using

git grep "for.*\.vertices()" src/sage/quivers/
git grep "for.*\.vertices()" src/sage/combinat/

CC: @tscrim @jm58660 @dcoudert

Component: combinatorics

Author: Frédéric Chapoton

Branch/Commit: 03972bf

Reviewer: David Coudert

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

[fchapoton]

Branch: u/chapoton/25832

[fchapoton]

Commit: a17fd63

[fchapoton]

New commits:

2a5d00c	trac 25817: add "conjugate" explicitly to maxima_lib translation dictionary, since automatic discovery doesn't always work.
a17fd63	replacing some .vertices() by .vertex_iterator(), in combinat and quivers

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

4ad879a

replacing some .vertices() by .vertex_iterator(), in combinat and quivers

[sagetrac-git]

Changed commit from a17fd63 to 4ad879a

[fchapoton]

Changed author from frederic chapoton to Frédéric Chapoton

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

29fe2aa

replacing some .vertices() by .vertex_iterator(), in combinat and quivers

[sagetrac-git]

Changed commit from 4ad879a to 29fe2aa

[tscrim]

comment:5

Needs review?

[jm58660]

comment:6

Replying to @tscrim:

Needs review?

I guess no, this fails several tests.

[sagetrac-git]

Changed commit from 29fe2aa to 2d6322d

[sagetrac-git]

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

2d6322d

trac 25832 undo wrong change to vertex_iterator

[sagetrac-git]

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

be764c5

trac 25832 another fix

[sagetrac-git]

Changed commit from 2d6322d to be764c5

[fchapoton]

comment:9

There remains failing doctests in species. Probably we can just change the doctests.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

db32dbe

replacing some .vertices() by .vertex_iterator(), in combinat and quivers

[sagetrac-git]

Changed commit from be764c5 to db32dbe

[fchapoton]

comment:11

I have undone the change in species, that was making some doctests return random results.

[tscrim]

comment:12

Perhaps the thing to do would be to run sorted in each of those places (e.g., in defining var_mapping) as progress towards #22349.

[fchapoton]

comment:13

Hmm, what do you mean ? Using "sorted" in species ?

[tscrim]

comment:14

Yes, that is correct.

[tscrim]

comment:15

Well, ideally we would write doctests that do not depend on the output order, but sometimes that is harder than its worth.

[fchapoton]

comment:16

oh, well. Maybe we can just keep that for another ticket, no ?

[dcoudert]

comment:18

A few comments in quiver.py:

• Apparently, you can replace set(frozen).issubset(set(data.vertex_iterator())) by set(frozen).issubset(data.vertex_iterator()).

sage: G = graphs.PetersenGraph()
sage: set([1,2]).issubset(G.vertex_iterator())
True
sage: set([1,10]).issubset(G.vertex_iterator())
False

• I don't know the size of mlist in this code, but it might be interesting to first convert it to a set before doing nlist = self._nlist = sorted(x for x in data.vertex_iterator() if x not in mlist)

• if any((a,a) in edges for a in data.vertex_iterator()): -> if data.has_loops():. Furthermore, the list edges could be turned to a set for the next test (2-cycles).

• There are places where you could replace edges() by edge_iterator(), but may be you prefer to let that for another ticket.

• and finally, the following block

if dg.has_multiple_edges():
    multi_edges = {}
    for v1,v2,label in dg.multiple_edges():
        ...

could be changed to

multiple_edges = dg.multiple_edges()
if multiple_edges:
    multi_edges = {}
    for v1,v2,label in multiple_edges:
        ....

Indeed, the cost of has_multiple_edges is almost the same as multiple_edges, that is visiting all the edges. So we can save one call.

[sagetrac-git]

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

976e0f5

trac 25832 some suggested changes in quiver.py

[sagetrac-git]

Changed commit from db32dbe to 976e0f5

[dcoudert]

comment:20

To avoid converting frozen to set and later to list again, and also to benefit from the set, I suggest to do:

            elif isinstance(frozen, list):
                s_frozen = set(frozen)
                if not s_frozen.issubset(data.vertex_iterator()):
                     raise ValueError("the optional list of frozen elements"
                                      " must be vertices of the digraph")
                 else:
                    mlist = self._mlist = frozen
                    nlist = self._nlist = sorted(x for x in data.vertex_iterator() if x not in s_frozen)

[fchapoton]

comment:22

I am not sure of what is exactly the point of converting to set. I can see that it can handle bad input, namely duplicate elements in the given frozen list, in which case we do not want to use the bad input itself. But you seem to say that by itself it will be faster in the loop ? Is this just by being a set instead of a list ?

[dcoudert]

comment:23

Testing if an element is in a list takes time O(n) while in a set it takes time O(1). Of course, converting a list to a set has a cost, but if you to several test, it's interesting

sage: L = list(range(1000))
sage: S = set(L)
sage: %timeit [i for i in range(10000) if i in L]
10 loops, best of 3: 137 ms per loop
sage: %timeit [i for i in range(10000) if i in S]
1000 loops, best of 3: 877 µs per loop
sage: %timeit S = set(L)
10000 loops, best of 3: 21.3 µs per loop

I agree it's a minor improvement compared to other modifications.

[fchapoton]

comment:24

In the quiver.py file, we are mostly dealing with digraphs with a small number of vertices. Probably almost never above 50. So these 'optimizations" are not really useful, I think.

[dcoudert]

comment:25

I agree that it's not really useful, but as you have to convert frozen to set, you just have to do:

nlist = self._nlist = sorted(x for x in data.vertex_iterator() if x not in frozen)
mlist = self._mlist = list(frozen)

[sagetrac-git]

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

f1a9689	Merge branch 'u/chapoton/25832' in 8.3.rc1
03972bf	trac 25832 more details in quiver.py

[sagetrac-git]

Changed commit from 976e0f5 to 03972bf

[fchapoton]

comment:27

ok, done. Thanks

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:28

LGTM

[vbraun]

Changed branch from u/chapoton/25832 to 03972bf