#15820: Implement sequences of bounded integers
--------------------------------------------+------------------------
Reporter: SimonKing | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.2
Component: algebra | Resolution:
Keywords: sequence bounded integer | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
--------------------------------------------+------------------------
Comment (by SimonKing):
For completeness, I have added `Path_v6`, which uses Python's `tuple`
under the hood (which is an obvious way to implement paths, too).
Result:
{{{
sage: %timeit p5*q5
1000000 loops, best of 3: 439 ns per loop
sage: %timeit p5*q25
1000000 loops, best of 3: 542 ns per loop
sage: %timeit p25*q25
1000000 loops, best of 3: 612 ns per loop
sage: %timeit p25*q50
1000000 loops, best of 3: 869 ns per loop
sage: %timeit p50*q50
1000000 loops, best of 3: 1.1 us per loop
sage: %timeit p50*q100
1000000 loops, best of 3: 1.39 us per loop
sage: %timeit p100*q100
1000000 loops, best of 3: 1.41 us per loop
sage: %timeit p100*q1000
100000 loops, best of 3: 5.04 us per loop
sage: %timeit p1000*q1000
100000 loops, best of 3: 11 us per loop
sage: %timeit hash(p5)
1000000 loops, best of 3: 245 ns per loop
sage: %timeit hash(p25)
1000000 loops, best of 3: 532 ns per loop
sage: %timeit hash(p50)
1000000 loops, best of 3: 884 ns per loop
sage: %timeit hash(p100)
1000000 loops, best of 3: 1.63 us per loop
sage: %timeit hash(p1000)
100000 loops, best of 3: 14.6 us per loop
sage: %timeit p5==s5
1000000 loops, best of 3: 885 ns per loop
sage: %timeit p25==s25
1000000 loops, best of 3: 1.71 us per loop
sage: %timeit p50==s50
100000 loops, best of 3: 2.63 us per loop
sage: %timeit p100==s100
100000 loops, best of 3: 4.53 us per loop
sage: %timeit p1000==s1000
10000 loops, best of 3: 39.3 us per loop
sage: %timeit p5==r5
1000000 loops, best of 3: 785 ns per loop
sage: %timeit p25==r25
1000000 loops, best of 3: 829 ns per loop
sage: %timeit p50==r50
1000000 loops, best of 3: 799 ns per loop
sage: %timeit p100==r100
1000000 loops, best of 3: 791 ns per loop
sage: %timeit p1000==r1000
1000000 loops, best of 3: 822 ns per loop
sage: %timeit q5==r5
1000000 loops, best of 3: 1.48 us per loop
sage: %timeit q25==r25
100000 loops, best of 3: 3.72 us per loop
sage: %timeit q50==r50
100000 loops, best of 3: 6.63 us per loop
sage: %timeit q100==r100
100000 loops, best of 3: 12.5 us per loop
sage: %timeit q1000==r1000
10000 loops, best of 3: 116 us per loop
sage: %timeit q1000.startswith(q100)
100000 loops, best of 3: 4.7 us per loop
sage: %timeit q1000.startswith(r100)
100000 loops, best of 3: 4.72 us per loop
}}}
The comparison with the other implementations becomes this:
1. Concatenation
{{{
5x5 50x50 1000x1000
Uncompressed long : 739 ns 885 ns 3.06 us - -
Uncompressed short: 700 ns 808 ns 2.13 us
Uncompressed char : 679 ns 772 ns 1.31 us +
Compressed long : 676 ns 759 ns 1.61 us
Compressed short: 718 ns 722 ns 1.98 us +
Semicompr. long : 684 ns 827 ns 1.42 us
Integer : 645 ns 1.82 us 1.78 us -
GMP mpz_t: 723 ns 799 ns 1.41 us
tuple : 439 ns 1.1 us 11 us + -
}}}
2. Hash
{{{
5 100 1000
Uncompressed long : 135 ns 333 ns 2.09 us +
Uncompressed short: 138 ns 383 ns 2.61 us +--
Uncompressed char : 133 ns 374 ns 2.53 us +
Compressed long : 132 ns 155 ns 466 ns +++
Compressed short: 132 ns 206 ns 951 ns +
Semicompr. long : 148 ns 194 ns 594 ns
Integer : 164 ns 274 ns 1.94 us
GMP mpz_t: 159 ns 266 ns 1.93 us
tuple : 245 ns 1.63 us 14.6 us ---
}}}
3. == for equal paths
{{{
5 100 1000
Uncompressed long : 1.63 us 23 us 212 us ---
Uncompressed short: 1.08 us 14.9 us 137 us
Uncompressed char : 1.08 us 12.5 us 121 us
Compressed long : 710 ns 4.4 us 38 us
Compressed short: 723 ns 5.3 us 47.5 us
Semicompr. long : 498 ns 712 ns 2.4 us
Integer : 667 ns 658 ns 817 ns
GMP mpz_t: 466 ns 485 ns 693 ns +++
tuple : 885 ns 4.5 us 39.3 us
}}}
4. == for "easily" unequal paths
{{{
5 100 1000
Uncompressed long : 634 ns 686 ns 698 ns
Uncompressed short: 613 ns 603 ns 635 ns
Uncompressed char : 581 ns 599 ns 636 ns
Compressed long : 692 ns 729 ns 752 ns
Compressed short: 577 ns 588 ns 607 ns
Semicompr. long : 499 ns 526 ns 545 ns
Integer : 746 ns 731 ns 733 ns
GMP mpz_t: 451 ns 468 ns 482 ns +++
tuple : 785 ns 791 ns 822 ns ---
}}}
5. == for "difficult" unequal paths
{{{
5 100 1000
Uncompressed long : 1.65 us 22 us 213 us ---
Uncompressed short: 1.15 us 12.8 us 140 us
Uncompressed char : 1.06 us 12.7 us 121 us
Compressed long : 706 ns 4.4 us 37.6 us
Compressed short: 754 ns 5.3 us 47.3 us
Semicompr. long : 506 ns 704 ns 2.5 us
Integer : 710 ns 719 ns 755 ns
GMP mpz_t: 448 ns 457 ns 470 ns +++
tuple : 1.48 us 12.5 us 116 us
}}}
6. startswith
{{{
yes no
Uncompressed long : 325 ns 311 ns
Uncompressed short: 336 ns 325 ns
Uncompressed char : 324 ns 315 ns
Compressed long : 272 ns 257 ns +
Compressed short: 272 ns 256 ns +
Semicompr. long : 263 ns 232 ns ++
Integer : 2.46 us 2.45 us
GMP mpz_t: 673 ns 657 ns
tuple : 4.7 us 4.72 us --
}}}
So, using tuples is best for concatenation of short paths, but that's the
only case where it is not too slow.
--
Ticket URL: <http://trac.sagemath.org/ticket/15820#comment:18>
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/groups/opt_out.
