Opened 7 years ago
Closed 6 years ago
#17492 closed enhancement (fixed)
Speedup kclosed check
Reported by:  tscrim  Owned by:  tscrim 

Priority:  major  Milestone:  sage6.8 
Component:  matroid theory  Keywords:  kclosed 
Cc:  Stefan, Rudi, chaoxu  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  Rudi Pendavingh 
Report Upstream:  N/A  Work issues:  
Branch:  f4ff999 (Commits, GitHub, GitLab)  Commit:  f4ff999adcb52b3628aab925fe72ca867ed6f9de 
Dependencies:  #18429  Stopgaps: 
Description
Right now, checking for kclosed is slow because it uses Sage sets whereas we only need python sets.
Change History (10)
comment:1 Changed 7 years ago by
 Branch set to u/tscrim/k_closed_speedup17492
 Commit set to 2da089f7f2be369af66a5277eb5c9797dcbc5234
 Status changed from new to needs_review
 Summary changed from Speedup kclosure to Speedup kclosed check
comment:2 Changed 7 years ago by
 Commit changed from 2da089f7f2be369af66a5277eb5c9797dcbc5234 to 6fc7e6e986326b80ef4e32de1ee127ada1dd84b0
Branch pushed to git repo; I updated commit sha1. New commits:
6fc7e6e  Some more speedups.

comment:3 Changed 7 years ago by
 Cc Stefan Rudi added
comment:4 Changed 6 years ago by
 Cc chaoxu added
 Milestone changed from sage6.5 to sage6.8
comment:5 followup: ↓ 6 Changed 6 years ago by
Hi Travis,
I checked out this patch and it all works as advertised. Positive review, except for one thing:
A merge with 'master' was necessary before sage b would successfully build this on my sage 6.7. The logical thing would perhaps be to push the merged branch I created, but I hesitate to do this since my recent experience with git tell me that I might not fully understand how things work when it comes to this. Perhaps there is another, better way, and also I do not want to risk messing up your work.
So please update the branch to something that compiles out of the box, or argue that this is unnecessary. Then feel free to set this to 'positive review'.
comment:6 in reply to: ↑ 5 Changed 6 years ago by
 Reviewers set to Rudi Pendavingh
 Status changed from needs_review to positive_review
Replying to Rudi:
I checked out this patch and it all works as advertised. Positive review, except for one thing:
Thank you for the review.
A merge with 'master' was necessary before sage b would successfully build this on my sage 6.7. The logical thing would perhaps be to push the merged branch I created, but I hesitate to do this since my recent experience with git tell me that I might not fully understand how things work when it comes to this. Perhaps there is another, better way, and also I do not want to risk messing up your work.
So please update the branch to something that compiles out of the box, or argue that this is unnecessary. Then feel free to set this to 'positive review'.
The branch is merged with the latest develop
at merge time, so if this works after merging (cleanly, i.e., without having to handle any merge conflicts) with master
(or now develop
at 6.8.beta0), there should be no problems.
For the record, my usual workflow is to always merge the branch into my current develop
branch as my current spkgs might be incompatible with older versions of Sage. Plus it saves on compilation time. Also if you push it to a different branch and set that, there is no way to corrupt my work on my branch.
Thank you again.
comment:7 Changed 6 years ago by
 Status changed from positive_review to needs_work
comment:8 Changed 6 years ago by
 Commit changed from 6fc7e6e986326b80ef4e32de1ee127ada1dd84b0 to f4ff999adcb52b3628aab925fe72ca867ed6f9de
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
e29cbe1  _intersection_augmentation efficiency tweak

01e11cd  Matroid.is_3connected() can now provide a separation to certify non3connectedness

7d59d68  One more bug

402fdf7  Killed a doctest bug

aa453e7  Merge branch 'do_not_checkout' into public/matroid/add_matroid_connectivity18429

9b55e71  Reviewer changes to docstring formatting and trailing whitespace.

35b5ab6  Merge branch 'public/matroid/add_matroid_connectivity18429' of trac.sagemath.org:sage into u/tscrim/k_closed_speedup17492

b1c4de0  Allow one to specify ring/field for Wheel matroids

750760e  Merge branch 'u/chaoxu/ticket/18427' of trac.sagemath.org:sage into u/tscrim/k_closed_speedup17492

f4ff999  Removed unneeded imports.

comment:9 Changed 6 years ago by
 Dependencies set to #18429
 Status changed from needs_work to positive_review
comment:10 Changed 6 years ago by
 Branch changed from u/tscrim/k_closed_speedup17492 to f4ff999adcb52b3628aab925fe72ca867ed6f9de
 Resolution set to fixed
 Status changed from positive_review to closed
With patch:
Before:
So we are getting a 3x~4x speedup.
New commits:
Speedup kclosure by using python sets.
Removed unnecessary import.
One additional tweak to avoid unnecessary checks.