Opened 7 years ago

Closed 5 months ago

Last modified 4 months ago

#16351 closed enhancement (fixed)

Move RecursivelyEnumeratedSet_forest code to sage/sets/recursively_enumerated_set.pyx, remove deprecated classes SearchForest, TransitiveIdeal, TransitiveIdealGraded

Reported by: slabbe Owned by:
Priority: major Milestone: sage-9.2
Component: combinatorics Keywords:
Cc: tscrim, slelievre Merged in:
Authors: Matthias Koeppe Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 908acba (Commits) Commit:
Dependencies: Stopgaps:

Description

Move the code of SearchForest from sage/combinat/backtrack.py to sage/sets/recursively_enumerated_set.pyx into a class named RecursivelyEnumeratedSet_forest.

This is a follow up of #6637.

Change History (32)

comment:1 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:2 Changed 5 years ago by hivert

  • Branch set to u/hivert/move_searchforest_code_to_sage_sets_recursively_enumerated_set_pyx

comment:3 Changed 5 years ago by hivert

  • Commit set to 2effaf76cddfe91175187d8ba47d8bf090e0dec0

I just added some old doc from Nathann and myself which is worth being integrated when cleaning this up.


Last 10 new commits:

7a33037Work in progress on the DOC
168ceaeAdded architecture picture for map_reduce
366fc17More Doc
6c12752Tested timeout option
493bb52Done the doc of Map/Reduce
2534f12Moved map/reduce to sage/parallel
e5b7477Merge 6.10.rc1 + fixed conflict
82fd1e4Fixed links according to deprecation/rebase
68b6530Removed TODO in doc
2effaf7Revert "Removed TODO in doc"

comment:4 Changed 5 years ago by tscrim

  • Dependencies set to #13580
  • Milestone changed from sage-6.4 to sage-7.0

I would like to squeeze out some more speed of the SearchForest code, so I'm interested in this. I made #13580 a dependency since that is likely a lot closer than this is to getting into Sage. If you disagree, then we can reverse the order of the dependencies and I'd do the review once this is ready.

comment:5 follow-up: Changed 5 years ago by slabbe

The actual branch contains many commits from the #13580, so I can't see what is the goal of the branch put here and how it is related to this ticket.

Last edited 5 years ago by slabbe (previous) (diff)

comment:6 Changed 5 years ago by git

  • Commit changed from 2effaf76cddfe91175187d8ba47d8bf090e0dec0 to 1bf8c97ef9e6479ede07b339b11d413819508307

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

f984165Fixed the doc
a5f4d67Improved doc for map-reduce
569de0dMerge branch 'develop' into t/13580/map_reduce
b07dfe2Doc of the two implementationsof ActiveTaskCounter
beebcbc#13580: Added comment on timing in the doc
58eca2e#13580: Removed comment which is now in the doc
1badd8a#13580: Renamed ActiveTaskCounter(Posix)
46cbab913580: Fixed doctests to pass on Darwin
134c1fa13580: doc rereading
1bf8c97Merge branch 'u/hivert/move_searchforest_code_to_sage_sets_recursively_enumerated_set_pyx' of git://trac.sagemath.org/sage into t/13580/map_reduce

comment:7 in reply to: ↑ 5 Changed 5 years ago by hivert

Replying to slabbe:

The actual branch contains many commits from the #13580, so I can't see what is the goal of the branch put here and how it is related to this ticket.

I just rebased this ticket on top of #13580 the code contains only an explanation of what SearchForest does with a nice picture from Nathann, Nicolas and nyself. It should be integrated during the move and the documentation cleanup.

comment:8 Changed 5 years ago by tscrim

Something else that we should do while-we-are-at-it, we should consider using collections.deque since it supports fast popping from both ends (list can become really slow when popping at the front, but deque is still twice as slow popping at the front).

comment:9 follow-up: Changed 4 years ago by nthiery

Now that #13580 is in, the current branch contains just a small self-contained documentation improvement. It seems worth and easy to integrate soon, but somehow unrelated to this ticket, right?

Shall we create a separate ticket for that documentation chunk?

And refocus this one on moving the SearchForest? code to sage/sets/recursively_enumerated_set.pyx (more than by just a single alias)?

comment:10 in reply to: ↑ 9 ; follow-up: Changed 4 years ago by slabbe

Replying to nthiery:

Now that #13580 is in, the current branch contains just a small self-contained documentation improvement. It seems worth and easy to integrate soon, but somehow unrelated to this ticket, right?

Shall we create a separate ticket for that documentation chunk?

Please yes.

And refocus this one on moving the SearchForest? code to sage/sets/recursively_enumerated_set.pyx (more than by just a single alias)?

Yes.

comment:11 Changed 6 months ago by mkoeppe

  • Cc tscrim added
  • Milestone changed from sage-7.0 to sage-9.2

comment:12 in reply to: ↑ 10 Changed 6 months ago by mkoeppe

Replying to slabbe:

Replying to nthiery:

Now that #13580 is in, the current branch contains just a small self-contained documentation improvement. It seems worth and easy to integrate soon, but somehow unrelated to this ticket, right?

Shall we create a separate ticket for that documentation chunk?

Please yes.

This is now #29882.

comment:13 Changed 6 months ago by mkoeppe

  • Branch u/hivert/move_searchforest_code_to_sage_sets_recursively_enumerated_set_pyx deleted
  • Commit 1bf8c97ef9e6479ede07b339b11d413819508307 deleted
  • Dependencies #13580 deleted

comment:14 Changed 6 months ago by mkoeppe

  • Branch set to u/mkoeppe/move_searchforest_code_to_sage_sets_recursively_enumerated_set_pyx

comment:15 Changed 6 months ago by mkoeppe

  • Commit set to 143604d960c5b738d28f465c600aee5b2635e06d

Moved it, now need to clean up some lazy_import business


New commits:

7e1c6d2WIP
143604dWIP: Move SearchForest code to sage/sets/recursively_enumerated_set.pyx

comment:16 Changed 6 months ago by git

  • Commit changed from 143604d960c5b738d28f465c600aee5b2635e06d to 1764ca414390717102378411166d3fd6da457d85

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

364d7b3Move SearchForest code to sage/sets/recursively_enumerated_set.pyx
68f7bd5sage.combinat.integer_vectors_mod_permgroup: Update to use RecursivelyEnumeratedSet_forest
1764ca4Update remaining uses of SearchForest to use RecursivelyEnumeratedSet_forest

comment:17 Changed 6 months ago by mkoeppe

  • Authors set to Matthias Koeppe
  • Status changed from new to needs_review

Let's see what the patchbot has to say.

I have made not made any attempt to cythonize anything; this is really just pure Python code moved into the pyx file.

comment:18 Changed 6 months ago by mkoeppe

Also, I added a lazy_import for SearchForest but it seems that SearchForest was already deprecated -- perhaps now it can be removed completely?

comment:19 Changed 6 months ago by mkoeppe

(deprecation in #6637, 6 years ago)

comment:20 Changed 6 months ago by git

  • Commit changed from 1764ca414390717102378411166d3fd6da457d85 to 1ac0a095626cd70a1b5fabb59474ba3f37f47b12

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

1ac0a09sage.combinat.backtrack: Remove deprecated class SearchForest

comment:21 Changed 6 months ago by mkoeppe

Also TransitiveIdeal and TransitiveIdealGraded were deprecated in #6637.

comment:22 Changed 6 months ago by git

  • Commit changed from 1ac0a095626cd70a1b5fabb59474ba3f37f47b12 to 908acba415758383bbc6092008276b9081ab782d

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

908acbasage.combinat.backtrack: Remove deprecated classes TransitiveIdeal and TransitiveIdealGraded

comment:23 Changed 6 months ago by mkoeppe

  • Summary changed from Move SearchForest code to sage/sets/recursively_enumerated_set.pyx to Move RecursivelyEnumeratedSet_forest code to sage/sets/recursively_enumerated_set.pyx, removed deprecated classes SearchForest, TransitiveIdeal, TransitiveIdealGraded

comment:24 Changed 6 months ago by vdelecroix

It seems to me that with your changes SearchForest does not exist anymore. If so, you must add a lazy import with deprecation warning in backtrack.py. The SearchForest was documented as a deprecated class but was not making any deprecation warning when used.

comment:25 Changed 6 months ago by mkoeppe

That's right, these deprecated classes are deleted.

The deprecation happened in #6637 and announced on the ticket, I guess before deprecation warnings were invented?

comment:26 Changed 6 months ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

This is somehow annoying. Let us hope that nobody uses it in her code.

comment:27 Changed 6 months ago by mkoeppe

Thanks!

comment:28 Changed 5 months ago by slelievre

  • Cc slelievre added
  • Summary changed from Move RecursivelyEnumeratedSet_forest code to sage/sets/recursively_enumerated_set.pyx, removed deprecated classes SearchForest, TransitiveIdeal, TransitiveIdealGraded to Move RecursivelyEnumeratedSet_forest code to sage/sets/recursively_enumerated_set.pyx, remove deprecated classes SearchForest, TransitiveIdeal, TransitiveIdealGraded

comment:29 Changed 5 months ago by slelievre

In the same general area, any interest in #22184 and #27537 anyone?

comment:30 Changed 5 months ago by vbraun

  • Branch changed from u/mkoeppe/move_searchforest_code_to_sage_sets_recursively_enumerated_set_pyx to 908acba415758383bbc6092008276b9081ab782d
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:31 Changed 5 months ago by slabbe

  • Commit 908acba415758383bbc6092008276b9081ab782d deleted

Thanks for finishing this task.I feel ashame I never finished it myself.

As a further todo, I think it will be nice to have

-class RecursivelyEnumeratedSet_forest(Parent):
+class RecursivelyEnumeratedSet_forest(RecursivelyEnumeratedSet_generic):

There are few methods like to_digraph from the generic class that I like to use but are currently not available for the forest type.

comment:32 Changed 4 months ago by slabbe

A follow-up ticket is here: #30238

Note: See TracTickets for help on using tickets.