Opened 13 years ago

Closed 6 months ago

Polish the use of iterators in C graphs

Reported by: Owned by: rlm rlm major sage-9.5 graph theory gh-kliem, tscrim David Coudert Travis Scrimshaw N/A c7dc1b1 c7dc1b1f01ad53ef1e7e1e1be3e926ae714d18f5

comment:1 Changed 13 years ago by rlm

• Description modified (diff)

comment:2 Changed 13 years ago by ncohen

• Report Upstream set to N/A

comment:3 Changed 12 years ago by rlm

I am right now watching a talk on closures in Cython, which are all but finished. Then, yield statements in Cython will soon follow! So don't work on this ticket for now...

comment:4 Changed 12 years ago by jason

• Type changed from defect to enhancement

comment:5 Changed 9 years ago by jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

comment:6 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

comment:7 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

comment:8 Changed 8 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

comment:9 Changed 6 months ago by dcoudert

• Authors set to David Coudert
• Branch set to public/graphs/6604_iterators
• Cc gh-kliem tscrim added; ncohen removed
• Commit set to 07d52d955bd71c87bcb175814b155c5d0c57b3a6
• Milestone changed from sage-6.4 to sage-9.5
• Status changed from new to needs_review

It seems there is little remaining to do for iterators in backends now, so let's do it.

Before

```sage: a = DiGraph(graphs.CompleteGraph(100))
sage: b = a._backend
sage: %timeit L = list(b.iterator_nbrs(30))
28.3 µs ± 1.44 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
```

After

```sage: a = DiGraph(graphs.CompleteGraph(100))
sage: b = a._backend
sage: %timeit L = list(b.iterator_nbrs(30))
18.6 µs ± 698 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
```

New commits:

 ​07d52d9 `trac #6604: polish some iterators in backends`

comment:10 Changed 6 months ago by tscrim

• Reviewers set to Travis Scrimshaw

That is quite a decent speedup and will likely have effects in other methods. Looks like some trivial failures due to slight differences in how the iteration is done:

```sage -t --long --random-seed=210304412354021215508062896360889570175 src/sage/graphs/generic_graph.py
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 10654, in sage.graphs.generic_graph.GenericGraph.neighbor_iterator
Failed example:
list(D.neighbor_iterator(0))
Expected:
[1, 2, 3]
Got:
[3, 1, 2]
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 17591, in sage.graphs.generic_graph.GenericGraph.?
Failed example:
list(D.depth_first_search(1, ignore_direction=True, edges=True))
Expected:
[(1, 4), (4, 5), (5, 6), (5, 2), (4, 3)]
Got:
[(1, 3), (3, 4), (4, 5), (5, 6), (5, 2)]
```

This one I am not sure if it is because of the random seed or this ticket:

```sage -t --long --random-seed=210304412354021215508062896360889570175 src/sage/schemes/toric/sheaf/klyachko.py
**********************************************************************
File "src/sage/schemes/toric/sheaf/klyachko.py", line 950, in sage.schemes.toric.sheaf.klyachko.KlyachkoBundle_class.random_deformation
Failed example:
Vtilde.cohomology(dim=True, weight=(0,))
Expected:
(1, 0)
Got:
(0, 0)
```

in either case, it should be a trivial fix.

comment:11 Changed 6 months ago by git

• Commit changed from 07d52d955bd71c87bcb175814b155c5d0c57b3a6 to c7dc1b1f01ad53ef1e7e1e1be3e926ae714d18f5

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

 ​c7dc1b1 `trac #6604: fix doctests in genenric_graph.py`

comment:12 Changed 6 months ago by dcoudert

I fixed the doctests in `generic_graph.py`.

I cannot reproduce the error in `klyachko.py`. It occurs in method `random_deformation`. Some help might be helpful here.

comment:13 Changed 6 months ago by dcoudert

Actually, this random error in `klyachko.py` has already been reported in #32773.

comment:14 Changed 6 months ago by tscrim

• Status changed from needs_review to positive_review

Thank you. LGTM.

comment:15 Changed 6 months ago by vbraun

• Branch changed from public/graphs/6604_iterators to c7dc1b1f01ad53ef1e7e1e1be3e926ae714d18f5
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.