#11740: reading integers from a file takes quadratic time
--------------------------------+-------------------------------------------
Reporter: zimmerma | Owner: AlexGhitza
Type: defect | Status: new
Priority: major | Milestone: sage-4.7.2
Component: basic arithmetic | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
--------------------------------+-------------------------------------------
Comment(by nbruin):
I think it's python's string-to-int routine, which we hit because
preparsing transforms
"100" :-> "Integer(100)"
If instead we do
"100" :-> "Integer('100')" we don't observe the slowdown:
{{{
sage: for j in range(10):
....: s = '1'*(100000*2^j)
....: t = cputime()
....: si = eval("".join(["Integer('",s,"')"]))
....: cputime(t)
0.0069990000000004216
0.014998000000000289
0.038993999999998863
0.078988000000000724
0.18397200000000069
0.44893199999999922
1.0758369999999999
2.2736540000000023
5.2492010000000029
13.029020000000003
}}}
If you do {{{ si = int(s) }}} you get the quadratic behaviour as well. I
see the following solutions:
- fix python's string-to-int to run in O(input size)
- change the preparser to generate Integer('100') instead of
Integer(1000)
Option number one has the biggest benefit because that has a chance of
improving python for everyone.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11740#comment:3>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
