#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 | aa89bb267303a9c424d6e6883ee35b2d7e592d7c
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by 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:
{{{
# ClonableArray
sage: L = IntegerListsLex(50, min_part=1, max_slope=0)
sage: it = iter(L)
sage: %timeit x = it.next()
10000 loops, best of 3: 148 µs per loop
# plain lists
sage: L = IntegerListsLex(50, min_part=1, max_slope=0,
element_constructor=list)
sage: it = iter(L)
sage: %timeit x = it.next()
10000 loops, best of 3: 134 µs per loop
}}}
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?
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):
{{{
sage: sage: L = IntegerListsLex(50, min_part=1, max_slope=0)
sage: l = range(1000)
sage: %timeit x =list(l)
100000 loops, best of 3: 2.4 µs per loop
sage: c = L.element_class
sage: %timeit x = c(L, l)
100000 loops, best of 3: 2.85 µs per loop
sage: %timeit [x[i] for i in range(100)]
100000 loops, best of 3: 6.84 µs per loop
sage: %timeit [l[i] for i in range(100)]
100000 loops, best of 3: 5.61 µs per loop
}}}
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.
> 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.
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.
> 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.
> 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).
With that, it's natural to cache error-free runs (error runs won't be
cached) to not redo the work in later iterator constructions.
Cheers,
Nicolas
--
Ticket URL: <http://trac.sagemath.org/ticket/17979#comment:293>
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.
