#17979: Reimplementation of IntegerListsLex
-------------------------------------+-------------------------------------
Reporter: aschilling | Owner:
Type: defect | Status: needs_work
Priority: blocker | Milestone: sage-6.6
Component: combinatorics | Resolution:
Keywords: days64 | Merged in:
Authors: Bryan Gillespie, | Reviewers: Nathann Cohen, Jeroen
Anne Schilling, Nicolas M. Thiery | Demeyer, Travis Scrimshaw
Report Upstream: N/A | Work issues:
Branch: | Commit:
public/ticket/17979 | a993265c284c12b96f777104ee6dba6d1eee4a9e
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by nthiery):
On Wed, Apr 01, 2015 at 08:15:51AM -0000, sage-trac wrote:
> I know that it has not changed.
Then please discuss this in another ticket to not delay this one.
> If you modify the constructor to return list, the list is copied
> twice instead of once. I would not call that a solution.
It's trivial to introduce a special case to avoid the copy if the
element constructor is known to be safe. In fact it's done now.
> Most importantly, that was not my point. It makes no sense that a plain
> Python iterator inherit from Parent. It is a question of design, not of
> timings. The thing is that tuples and lists are the standard Python
> objects. This is the way the Python module `itertools` behaves.
Ideally,
> the `IntegerListLex` should be plainly Python compatible.
(for the record, the iterator itself does not inherit from Parent).
I would go even further than you: IntegerListsLex uses nothing
specific of Python either. It would be best implemented as a
standalone C++ library. It could then be reused by software outside of
the Python world, be templated by whatever structure we want to use
for the lists, possibly benefit from further low level optimizations
(silk, special processor instructions), etc.
But this discussion belongs to later tickets. Here the goal is to get
a correct algorithm. The next step is to get an algorithm with
reasonably optimal complexity (while further clarifying its
structure). And then should come the rewriting in a low level
language.
> > The overhead comes from the containment test that we do in the
``check``
> > method:
> > {{{
> > # ClonableArray, with check made trivial
> > sage: sage: L = IntegerListsLex(50, min_part=1, max_slope=0)
> > sage: sage: it = iter(L)
> > sage: sage: %timeit x = it.next()
> > 10000 loops, best of 3: 135 µs per loop
> > }}}
> >
> > I am not sure this containment check is useful. We could just disable
> > it. What do you think?
>
> Definitely!
Done. Easy to revert if anyone is uncomfortable with this.
> Right. But why is it nested? It will be a mess with Cythonization.
At the end, it's all about stylistic preference. It's instantaneous to
change if/when desired. Whoever will work next on this can change to
his own preferred style. I am not discussing this further.
> Having two classes in a file called `IntegerListLex` and
> `IntegerListLexIterator` is rather explicit. I am not sure that
following
> the Parent/Element direction is the best here. As I said before, it
would
> be cool if this file would be Python compatible.
Nested classes are a feature of plain Python, and of many other
programming languages. It turns out that Cython does not support them
now, but I don't see any theoretical obstruction (and it can be easily
emulated).
Altogether I see no compelling reason not to use this feature when it
helps better structure the code.
> It is reasonable to keep it in the ticket. But what if I do remove
> it in another ticket?
I don't have an objection if someone takes the responsibility for this
backward incompatible change in a later ticket :-)
Or maybe, if the use case emerges, one should actually go the other
way round: make it syntactically trivial to have variants of
IntegerListsLex, graded by any or both of the length and size
parameters: it's not as generic as DisjointUnionEnumeratedSets, but
this could save on time by sharing quite some stuff between the graded
components (e.g. the parsing of the arguments, the upper and lower
envelopes, ...).
Cheers,
Nicolas
--
Ticket URL: <http://trac.sagemath.org/ticket/17979#comment:305>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
