As other people have mentioned, there's a factor of 2 overhead in the
first loop. I'm not sure why you're indexing from 1 either.
As for writing fast pyrex matrix code, M[i,j] is really slow. Here's
what happens:
- A new (len 2) tuple is allocated
- i and j are converted into Python ints (in the second option, this
happens within the xrange function, though calling xrange and using
the resulting iterator is additional overhead.)
- the tuple is filled
- __getitem__ is (indirectly) called
- matrix __getitem__ extracts the two parts of the tuple, and
extracts the c ints from the resulting python ints
- the matrix calculates and returns the actual entry
You can avoid this overhead by using matrix.get_unsafe(i,j). The
(untested) code would then be
def is_symmetric(self):
"""
Returns True if this is a symmetric matrix.
"""
if self._ncols != self._nrows: return False
cdef Py_ssize_t i,j # could be bigger than an int on a 64-
bit platform, this is the type used for indexing.
for i from 0 <= i < self._nrows:
for j from 0 <= j < i:
if self.get_unsafe(i,j) != self.get_unsafe(j,i):
return False
return True
You will still have the same overhead from object creation for each
entry (in the integer case), but this would be mitigated by the
integer pool and should be much faster.
- Robert
On Jun 28, 2007, at 11:41 PM, Justin C. Walker wrote:
>
> Hi,
>
> I tried the following, added to the Matrix class definition in matrix/
> matrix0.pyx:
>
> def is_symmetric(self):
> """
> Returns True if this is a symmetric matrix.
> """
> if self._ncols != self._nrows: return False
> cdef int i,j
> for i from 1 <= i < self._nrows:
> for j from 0 <= j < self._ncols:
> if self[i,j] != self[j,i]: return False
> return True
>
> While testing and timing this, I tried the following, out of a
> perverse sort of curiosity:
>
> def is_sym3(self):
> """
> Returns True if this is a symmetric matrix.
> """
> if self._ncols != self._nrows: return False
> for i in xrange(1,self._nrows):
> for j in xrange(0,i):
> if self[i,j] != self[j,i]: return False
> return True
>
> Turns out that this, both as a method in the Matrix class and as a
> raw hunk of python code, performs better than the above:
>
> sage: time Doit1(M2,1000)
> CPU times: user 37.21 s, sys: 0.24 s, total: 37.45 s
> Wall time: 38.10
>
> sage: time Doit2(M2,1000)
> CPU times: user 23.50 s, sys: 0.18 s, total: 23.68 s
> Wall time: 24.55
>
> sage: time Doit1(M3,1000)
> CPU times: user 55.87 s, sys: 0.41 s, total: 56.29 s
> Wall time: 58.48
>
> sage: time Doit2(M3,1000)
> CPU times: user 31.52 s, sys: 0.23 s, total: 31.76 s
> Wall time: 32.83
>
> sage: time Doit1(M4,1000)
> CPU times: user 58.94 s, sys: 0.71 s, total: 59.65 s
> Wall time: 63.05
>
> sage: time Doit2(M4,1000)
> CPU times: user 32.64 s, sys: 0.43 s, total: 33.08 s
> Wall time: 35.05
>
>
> Doit1 is a loop that calls ".is_symmetric()", for the given count.
>
> Doit2 is a loop that calls "issym()", for the given count.
>
> M2 is a 200x200 integer symmetric matrix, with entries in the range
> 1..300000.
>
> M3 is a 200x200 integer symmetric matrix, with entries in the range
> 1..200000000000000000.
>
> M4 is a 200x200 integer symmetric matrix, with entries in the range
> 1..2000000000000000000000000000000000000000000000000000000.
>
> Expected? Unexpected?
>
> Justin
>
> --
> Justin C. Walker, Curmudgeon-at-Large
> () The ASCII Ribbon Campaign
> /\ Help Cure HTML Email
>
>
>
>
>
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
