#15820: Implement sequences of bounded integers
-------------------------------------+-------------------------------------
Reporter: SimonKing | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: algebra | Resolution:
Keywords: sequence bounded | Merged in:
integer | Reviewers: Simon King
Authors: Simon King, | Work issues:
Jeroen Demeyer | Commit:
Report Upstream: N/A | e9c779ae629dbec356bb8546e3974e2a67050051
Branch: | Stopgaps:
u/SimonKing/ticket/15820 |
Dependencies: #17195, #17196 |
-------------------------------------+-------------------------------------
Comment (by SimonKing):
I repeated the timings from commit:157, but still with the `item<=bound`
test (so, initialisation time might improve).
{{{
sage: from sage.data_structures.bounded_integer_sequences import
BoundedIntegerSequence
sage: L0 = [randint(0,7) for i in range(5)]
sage: L1 = [randint(0,15) for i in range(15)]
sage: L2 = [randint(0,31) for i in range(50)]
sage: L3 = [randint(0,31) for i in range(5000)]
sage: T0 = tuple(L0); T1 = tuple(L1); T2 = tuple(L2); T3 = tuple(L3)
sage: S0 = BoundedIntegerSequence(8, L0)
sage: S1 = BoundedIntegerSequence(16, L1)
sage: S2 = BoundedIntegerSequence(32, L2)
sage: S3 = BoundedIntegerSequence(32, L3)
}}}
{{{
sage: %timeit x = BoundedIntegerSequence(8, L0)
1000000 loops, best of 3: 1.45 µs per loop
sage: %timeit x = BoundedIntegerSequence(16, L1)
100000 loops, best of 3: 2.1 µs per loop
sage: %timeit x = BoundedIntegerSequence(32, L2)
100000 loops, best of 3: 4.28 µs per loop
sage: %timeit x = BoundedIntegerSequence(32, L3)
1000 loops, best of 3: 300 µs per loop
}}}
--> Became much slower
{{{
sage: %timeit x = list(S0)
1000000 loops, best of 3: 1.44 µs per loop
sage: %timeit x = list(S1)
100000 loops, best of 3: 2.18 µs per loop
sage: %timeit x = list(S2)
100000 loops, best of 3: 4.29 µs per loop
sage: %timeit x = list(S3)
1000 loops, best of 3: 286 µs per loop
sage: %timeit x = S0.list()
1000000 loops, best of 3: 697 ns per loop
sage: %timeit x = S1.list()
1000000 loops, best of 3: 1.2 µs per loop
sage: %timeit x = S2.list()
100000 loops, best of 3: 2.78 µs per loop
sage: %timeit x = S3.list()
10000 loops, best of 3: 135 µs per loop
}}}
--> not much conclusive
{{{
sage: timeit("x=S0[:-1]", number=100000)
100000 loops, best of 3: 815 ns per loop
sage: timeit("x=S1[:-1]", number=100000)
100000 loops, best of 3: 846 ns per loop
sage: timeit("x=S2[:-1]", number=100000)
100000 loops, best of 3: 845 ns per loop
sage: timeit("x=S3[:-1]", number=100000)
100000 loops, best of 3: 1.62 µs per loop
sage: timeit("x=S2[:-1:2]", number=10000)
10000 loops, best of 3: 1.55 µs per loop
sage: timeit("x=S3[:-1:2]", number=10000)
10000 loops, best of 3: 49.8 µs per loop
}}}
--> Became ''much'' faster
{{{
sage: timeit("x=S0[1]", number=1000000)
1000000 loops, best of 3: 354 ns per loop
sage: timeit("x=S0[4]", number=1000000)
1000000 loops, best of 3: 355 ns per loop
sage: timeit("x=S3[1]", number=1000000)
1000000 loops, best of 3: 339 ns per loop
sage: timeit("x=S3[4500]", number=1000000)
1000000 loops, best of 3: 346 ns per loop
}}}
--> Became perhaps slower.
What does that all mean?
For my applications not very much, actually, because what I care about is
not
initialisation from lists and direct item access and not slices with step
different from one, but:
- Testing for subsequence containment, comparison and hash
- Slicing with step one
- Concatenation.
So, I leave it up to you whether clarity of code is more important than
the
above slow-down...
--
Ticket URL: <http://trac.sagemath.org/ticket/15820#comment:292>
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.
