#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:
Authors: Simon King | Work issues:
Report Upstream: N/A | Commit:
Branch: | 47c639d55d3c07670b8b52a629f7cf86a8beb7ce
u/SimonKing/ticket/15820 | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by SimonKing):
Let us compare the performance tests from comment:83 (also adding tests
for
pickling) with the new code version (I am testing on the same laptop,
thus,
hopefully a comparison makes sense):
{{{
sage: from sage.misc.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.15 µs per loop
sage: %timeit x = BoundedIntegerSequence(16, L1)
1000000 loops, best of 3: 1.35 µs per loop
sage: %timeit x = BoundedIntegerSequence(32, L2)
1000000 loops, best of 3: 1.88 µs per loop
sage: %timeit x = BoundedIntegerSequence(32, L3)
10000 loops, best of 3: 70.5 µs per loop
}}}
--> Became all faster
{{{
sage: %timeit x = list(S0)
1000000 loops, best of 3: 1.43 µs per loop
sage: %timeit x = list(S1)
100000 loops, best of 3: 1.84 µs per loop
sage: %timeit x = list(S2)
100000 loops, best of 3: 4.41 µs per loop
sage: %timeit x = list(S3)
1000 loops, best of 3: 304 µs per loop
sage: %timeit x = S0.list()
1000000 loops, best of 3: 666 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.77 µs per loop
sage: %timeit x = S3.list()
10000 loops, best of 3: 112 µs per loop
}}}
--> Became faster at least for short sequences, which is the case I am
mainly
interested in
{{{
sage: timeit("x=S0[:-1]", number=100000)
100000 loops, best of 3: 1.49 µs per loop
sage: timeit("x=S1[:-1]", number=100000)
100000 loops, best of 3: 1.52 µs per loop
sage: timeit("x=S2[:-1]", number=100000)
100000 loops, best of 3: 1.52 µs per loop
sage: timeit("x=S3[:-1]", number=100000)
100000 loops, best of 3: 2.29 µs per loop
}}}
--> Became all faster
{{{
sage: timeit("x=S2[:-1:2]", number=10000)
10000 loops, best of 3: 2.5 µs per loop
sage: timeit("x=S3[:-1:2]", number=10000)
10000 loops, best of 3: 62.2 µs per loop
}}}
--> Became faster for the shorter sequence
{{{
sage: timeit("x=S0[1]", number=1000000)
1000000 loops, best of 3: 340 ns per loop
sage: timeit("x=S0[4]", number=1000000)
1000000 loops, best of 3: 339 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: 345 ns per loop
}}}
--> Became all faster
{{{
sage: L0x = [randint(0,7) for i in range(5)]
sage: L1x = [randint(0,15) for i in range(15)]
sage: L2x = [randint(0,31) for i in range(50)]
sage: L3x = [randint(0,31) for i in range(5000)] # verified that they
differ from L0,L1,L2,L3
sage: S0x = BoundedIntegerSequence(8, L0x)
sage: S1x = BoundedIntegerSequence(16, L1x)
sage: S2x = BoundedIntegerSequence(32, L2x)
sage: S3x = BoundedIntegerSequence(32, L3x)
sage: S1y = BoundedIntegerSequence(16, L1)
sage: S2y = BoundedIntegerSequence(32, L2)
sage: S3y = BoundedIntegerSequence(32, L3)
sage: S1y==S1!=S1x, S1y is not S1
(True, True)
sage: S0z1 = S0+S0
sage: S0z2 = S0+S0x
sage: S1z1 = S1+S1
sage: S1z2 = S1+S1x
sage: S2z1 = S2+S2
sage: S2z2 = S2+S2x
sage: S3z1 = S3+S3
sage: S3z2 = S3+S3x
sage: timeit("S0z2.startswith(S0)", number=1000000)
1000000 loops, best of 3: 210 ns per loop
sage: timeit("S0z2.startswith(S0x)", number=1000000)
1000000 loops, best of 3: 211 ns per loop
sage: timeit("S0x in S0z2", number=1000000)
1000000 loops, best of 3: 368 ns per loop
sage: timeit("S1z2.startswith(S1)", number=1000000)
1000000 loops, best of 3: 200 ns per loop
sage: timeit("S1z2.startswith(S1x)", number=1000000)
1000000 loops, best of 3: 199 ns per loop
sage: timeit("S1x in S1z2", number=1000000)
1000000 loops, best of 3: 542 ns per loop
sage: timeit("S2z2.startswith(S2)", number=1000000)
1000000 loops, best of 3: 219 ns per loop
sage: timeit("S2z2.startswith(S2x)", number=1000000)
1000000 loops, best of 3: 205 ns per loop
sage: timeit("S2x in S2z2", number=1000000)
1000000 loops, best of 3: 2.33 µs per loop
sage: timeit("S3z2.startswith(S3)", number=1000000)
1000000 loops, best of 3: 963 ns per loop
sage: timeit("S3z2.startswith(S3x)", number=1000000)
1000000 loops, best of 3: 201 ns per loop
sage: timeit("S3x in S3z2", number=1000)
1000 loops, best of 3: 2.36 ms per loop
}}}
--> All but the last became faster, which is excellent for my
applications, as
I am using subsequent containment tests fairly often.
Additional timings for pickling, comparing Python lists with bounded
integer
sequences:
{{{
sage: %timeit loads(dumps(L0))
10000 loops, best of 3: 39.5 µs per loop
sage: %timeit loads(dumps(L1))
10000 loops, best of 3: 43.9 µs per loop
sage: %timeit loads(dumps(L2))
10000 loops, best of 3: 65.5 µs per loop
sage: %timeit loads(dumps(L3))
100 loops, best of 3: 2.13 ms per loop
sage: %timeit loads(dumps(S0))
10000 loops, best of 3: 68.7 µs per loop
sage: %timeit loads(dumps(S1))
10000 loops, best of 3: 72.1 µs per loop
sage: %timeit loads(dumps(S2))
10000 loops, best of 3: 87 µs per loop
sage: %timeit loads(dumps(S3))
1000 loops, best of 3: 1.06 ms per loop
}}}
--> Pickling of short bounded integer sequences has an overhead, but
longer
sequences are pickled faster, due to the more compact representation.
I think that one can say that the code results in an overall performance
gain,
and I suppose it is less frightening now.
--
Ticket URL: <http://trac.sagemath.org/ticket/15820#comment:157>
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.
