Backward incompatible change for BinaryTree

[Florent Hivert]

Hi there,

I'd like to make a backward incompatible change in Sage's interface:
Currently there is a BinaryTree algorithmic data structure which is imported
in sage.all from sage/misc/sage_ds.pyx. It is used only in
rings/polynomial/polynomial_compiled.pyx. I'd like to unimport it to be able
to import BinaryTree from sage/combinat. The new data structure is a
mathematical/combinatorial object. As such it is immutable and has a parent
namely BinaryTrees(). It is a very important (maybe the most important) object
in combinatorics which, together with Dyck words and ordered trees, appear in
a lot of combinatorial problems. It serve as a basis for various algebraic
object such as the LodayRonco Hopf algebra the Dendriform and OverUnder
operads.

So I'd like to have a vote for either one of those four options:

1. unimport BinaryTree from sage.misc.sage_ds and import them from combinat

2. leave think as such. Find a different name for the mathematical binary
trees (eg: BinaryTreesCombinatorial).

3. rename BinaryTree from sage.misc.sage_ds (eg: BinaryTreesDataStructure)
and import BinaryTree from combinat

4. something else ?

Cheers,

Florent

PS: cc to sage-devel and sage-combinat-devel.

[Nicolas M. Thiery]

On Mon, Jun 13, 2011 at 01:03:07PM +0200, Florent hivert wrote:
> So I'd like to have a vote for either one of those four options:
>
> 1. unimport BinaryTree from sage.misc.sage_ds and import them from combinat
>
> 2. leave think as such. Find a different name for the mathematical binary
> trees (eg: BinaryTreesCombinatorial).
>
> 3. rename BinaryTree from sage.misc.sage_ds (eg: BinaryTreesDataStructure)
> and import BinaryTree from combinat

My vote: 1 or 3. Like most of the sage-combinat people I guess :-)

We most need feedback from the others!

Cheers,
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

[Simon King]

Hi Florent and Nicolas,

On 13 Jun., 13:29, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>
wrote:

> On Mon, Jun 13, 2011 at 01:03:07PM +0200, Florent hivert wrote:
> >    So I'd like to have a vote for either one of those four options:
>
> > 1. unimport BinaryTree from sage.misc.sage_ds and import them from combinat
>
> > 2. leave think as such. Find a different name for the mathematical binary
> >    trees (eg: BinaryTreesCombinatorial).
>
> > 3. rename BinaryTree from sage.misc.sage_ds (eg: BinaryTreesDataStructure)
> >    and import BinaryTree from combinat
>
> My vote: 1 or 3. Like most of the sage-combinat people I guess :-)

I need more information: How do the binary trees from
sage.misc.sage_ds and from combinat compare, performance-wise? In
particular, will there be a performance regression for the "compiled
polynomials"?

If there is a regression then the combinat binary trees should learn
from sage.misc.sage_ds. A backward-incompatible change is out of
question if it is combined with a regression, IMHO.

If there is no regression and if compiled polynomials really is the
only application of sage.misc.sage_ds, then I wouldn't complain about
a change.

Cheers,
Simon

[Florent Hivert]

Hi Simon,

> > On Mon, Jun 13, 2011 at 01:03:07PM +0200, Florent hivert wrote:
> > > � �So I'd like to have a vote for either one of those four options:
> >
> > > 1. unimport BinaryTree from sage.misc.sage_ds and import them from combinat
> >
> > > 2. leave think as such. Find a different name for the mathematical binary
> > > � �trees (eg: BinaryTreesCombinatorial).
> >
> > > 3. rename BinaryTree from sage.misc.sage_ds (eg: BinaryTreesDataStructure)
> > > � �and import BinaryTree from combinat
> >
> > My vote: 1 or 3. Like most of the sage-combinat people I guess :-)
>
> I need more information: How do the binary trees from
> sage.misc.sage_ds and from combinat compare, performance-wise?

Short answer: of course they don't ! See below.

> In particular, will there be a performance regression for the "compiled
> polynomials"?

It seem that I haven't been clear. There will be *NO* performance regression
for polynomials since they will *KEEP* using the binary trees from
sage.misc.sage_ds. I'm *NOT* asking to remove them from sage but from
sage.all. The only question is to decide what kinds of binary tree will be
accessible for the user under the name of BinaryTree (from sage.all).

> If there is a regression then the combinat binary trees should learn
> from sage.misc.sage_ds. A backward-incompatible change is out of
> question if it is combined with a regression, IMHO.

The question of performance regression is somehow meaning less since both kind
of binary trees don't have the same feature:

- sage.misc.sage_ds.BinaryTree is a mutable algorithmic data structure which
is mutable, not hashable, and don't have any parent. Of course this
data-structure is needed if you are writing an algorithm with in-place
modification (eg: AVL set/hash table implementation).

- sage.combinat.binary_tree.BinaryTree is a mathematical object which as such
is immutable, hashable and doesn't support in place modification (though
they use the Prototype/Clone design pattern). They are not suitable for
algorithmic usage with performance in mind since you will need a lot of
copy, but this is a design choice.

> If there is no regression and if compiled polynomials really is the
> only application of sage.misc.sage_ds, then I wouldn't complain about
> a change.

I hope I've made myself clear.

Cheers,

Florent

[Tom Boothby]

Feel free to unimport BinaryTree from everywhere, and only import it
in compiled_polynomial.

> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>