#4533: [with patch; needs work] divisors function slow for integers
----------------------+-----------------------------------------------------
Reporter: robertwb | Owner: tbd
Type: defect | Status: new
Priority: major | Milestone: sage-3.2.1
Component: algebra | Resolution:
Keywords: |
----------------------+-----------------------------------------------------
Comment (by was):
> It should be noted that *sorting* the output often takes the majority of
the time
This is perhaps partly because sorting lists of GMP integers is slower
than Python ints, i.e., it takes about twice as long to do a comparison:
{{{
sage: n = ZZ(odd_part(factorial(31)))
sage:
sage: m = divisors(n, sorted=False)
sage: m2 = [int(j) for j in m]
sage: time m.sort()
CPU times: user 0.33 s, sys: 0.00 s, total: 0.34 s
Wall time: 0.34 s
sage: time m2.sort()
CPU times: user 0.16 s, sys: 0.00 s, total: 0.17 s
Wall time: 0.17 s
sage: a = 349; b = 678
sage: timeit('a < b')
625 loops, best of 3: 389 ns per loop
sage: a = int(349); b = int(678)
sage: timeit('a < b')
625 loops, best of 3: 213 ns per loop
}}}
In the timeits at the bottom, probably 100ns is spent just looking up a
and b in the globals...
Anyway, some of the ints for the divisors of n above are beyond long long,
so this word size discussion doesn't apply. However, if we consider 25,
notice that sorted
takes twice as long as computing the divisors:
{{{
sage: n = ZZ(odd_part(factorial(25)))
sage: time m = divisors(n,sorted=False)
CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.01 s
sage: v = [int(a) for a in m]
sage: time v.sort() # no better (see below).
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s
sage: v = numpy.array(m).astype(numpy.int64)
sage: time v.sort()
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
sage: time m.sort()
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s
}}}
However, sorting using an numpy int64 array seems to be much faster than
sorting a list of GMP ints. So if we just use some straightforward sort
on a Cython long long* we should get good results.
Unrelated: I noticed that n.divisors(...) doesn't have a sorted option.
So maybe some code in integer.pyx should be slightly changed.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4533#comment:9>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
