#17979: Reimplementation of IntegerListsLex
-------------------------------------+-------------------------------------
Reporter: aschilling | Owner:
Type: defect | Status: needs_review
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 | dcbad454879b348c727b87a46b0fef0e360f0471
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by vdelecroix):
Replying to [comment:293 nthiery]:
> Salut Vincent!
>
> Thanks for the feedback.
>
> On Tue, Mar 31, 2015 at 12:46:35PM -0000, sage-trac wrote:
> > There are several things that I do not quite understand. Could you
explain
> > or modify it:
> >
> > 1. The iterator `IntegerListLex` aims to be fast and low-level. What
is
> > the point of using the `Parent`/`Element` stuff? Why `ClonableArray`
are
> > better than Python lists?
>
> We haven't changed this aspect (in this ticket we focused on
> refactoring without changing the API): internally, Python lists are
> used; by default, they are converted to ClonableArray upon being
> yielded. The element constructor can be customized to return plain
> lists if so desired.
>
> In the current state of affairs, this does not really make a
> difference:
>
> ...
>
> For the record: using the parent/element protocol does not necessarily
> cause a large overhead; ClonableArray is almost as fast as list
> (timings to be of course taken with a grain of salt given how small
> values we are speaking about here):
I know that it has not changed. If you modify the constructor to return
list, the list is copied twice instead of once. I would not call that a
solution.
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.
> 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!
> In the long run, when `IntegerListsLex` will be cythonized, the
> relative situation may change, since we can hope for speedups of
> 10-100. Note in particular that we most likely will want to use arrays
> of ints internally; `ClonableIntArray` might be a good candidate for
> this. Or just STL vectors.
Note that in Python 3 there are arrays of int (as in numpy in Python 2):
https://docs.python.org/3/library/array.html
But I do not think that `itertools` will use that.
> > 2. Having a nested class seems overkill. The class `_Iter` is created
only
> > once in `__iter__`. Moreover, all methods in it starts with `p =
> > self.parent`. Why do you need to create this extra `_Iter` class? Why
does
> > it need to be a nested class?
>
> The class is needed because the iterator has an internal state. So we
> need to create a separate object for each concurrently running
> iterator.
Right. But why is it nested? It will be a mess with Cythonization.
> I find that using a nested class `IntegerListsLex._Iter`, rather than
> `IntegerListsLexIter` makes the relation between the two classes
> explicit (`_Iter` is for internal use for IntegerListsLex`). It's also
> consistent with what we do elsewhere (`Element`, ...). And there is no
> overhead in doing so.
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.
> > 3. Do you have a use case for
> > {{{
> > sage: IntegerListsLex(NN, max_length=3)
> > Disjoint union of Lazy family (<lambda>(i))_{i in Non negative
integer
> > semiring}
> > }}}
> > The feature only appears once in the doc in a place which does not
> > appear in the reference manual.
>
> It does appear in the reference manual: see section `Input list or
> iterable for the sum` of the main `IntegerListLex` class.
>
> The feature of iterating by increasing sum is certainly useful.
> Whether we want the above syntactic sugar -- instead of just using
> DisjointUnionEnumeratedSets -- is indeed questionable. The feature was
> already there, so we kept it to not change the API in this ticket.
It is reasonable to keep it in the ticket. But what if I do remove it in
another ticket?
> > 4. Why `_check_lexicographic_iterable` is a cached method? And I do
not
> > get why is it called from `_Iter` and not at the initialization of
> > `IntegerListsLex`.
>
> We discussed this with Jeroen in some earlier comment. Putting it in
> the iterator let the user create the `IntegerListsLex` object, even if
> it's not finite/iterable. This could be useful for other things than
> iteration, like membership testing or building the corresponding
> polytopes (once #17920 will be available).
Right. (And counting).
Vincent
--
Ticket URL: <http://trac.sagemath.org/ticket/17979#comment:296>
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.
