Opened 13 years ago
Closed 6 months ago
#6604 closed enhancement (fixed)
Polish the use of iterators in C graphs
Reported by:  rlm  Owned by:  rlm 

Priority:  major  Milestone:  sage9.5 
Component:  graph theory  Keywords:  
Cc:  ghkliem, tscrim  Merged in:  
Authors:  David Coudert  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  c7dc1b1 (Commits, GitHub, GitLab)  Commit:  c7dc1b1f01ad53ef1e7e1e1be3e926ae714d18f5 
Dependencies:  Stopgaps: 
Change History (15)
comment:1 Changed 13 years ago by
 Description modified (diff)
comment:2 Changed 13 years ago by
 Cc ncohen added
 Report Upstream set to N/A
comment:3 Changed 12 years ago by
comment:4 Changed 12 years ago by
 Type changed from defect to enhancement
comment:5 Changed 9 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:6 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:7 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:8 Changed 8 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:9 Changed 6 months ago by
 Branch set to public/graphs/6604_iterators
 Cc ghkliem tscrim added; ncohen removed
 Commit set to 07d52d955bd71c87bcb175814b155c5d0c57b3a6
 Milestone changed from sage6.4 to sage9.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
 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 randomseed=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 randomseed=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
 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
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
Actually, this random error in klyachko.py
has already been reported in #32773.
comment:14 Changed 6 months ago by
 Status changed from needs_review to positive_review
Thank you. LGTM.
comment:15 Changed 6 months ago by
 Branch changed from public/graphs/6604_iterators to c7dc1b1f01ad53ef1e7e1e1be3e926ae714d18f5
 Resolution set to fixed
 Status changed from positive_review to closed
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...