Apparently, corner[i,j] is a lot faster than corner[i][j]. With this
modification, the two versions are roughly equally fast. I don't get it,
though, because the second version should be doing a lot more work.
Martin
Am Montag, 11. September 2017 16:23:07 UTC+2 schrieb Martin R:
>
> I don't understand the following timings:
>
> sage: A = AlternatingSignMatrices(6)
> sage: lC = [a.corner_sum_matrix() for a in A]
> sage: timeit("[from_corner_sum_1(corner) for corner in lC]", number=1,
> repeat=1)
> 1 loops, best of 1: 63 s per loop
> sage: timeit("[from_corner_sum_2(corner) for corner in lC]", number=1,
> repeat=1)
> 1 loops, best of 1: 23.3 s per loop
>
> The first implementation, from_corner_sum_1, computes each entry of the
> result matrix using just array access to four elements in the given matrix
> "corner".
> The second, from_corner_sum_2, computes the same, using a caching version
> of a naive algorithm. (I was unaware of the first relation when I coded
> it.)
>
> Why is the second version so much faster? This looks insane to me! I
> hope I have misunderstood something very basic!
>
> Martin
>
> def from_corner_sum_1(corner):
> n = len(list(corner))-1
> asm = [[corner[i+1][j+1]+corner[i][j]-corner[i][j+1]-corner[i+1][j]
> for j in range(n)]
> for i in range(n)]
> return AlternatingSignMatrix(asm)
>
> def from_corner_sum2(corner):
> asm_list = []
> n = len(list(corner)) - 1
> for k in range(n):
> asm_list.append([])
> S = [0]*n
> C = [0]*n
> for i in range(n):
> R = 0
> for j in range(n):
> y = corner[i+1][j+1] - S[j] - C[j] - R
> S[j] += R
> C[j] += y
> R += y
> asm_list[i].append(y)
> return AlternatingSignMatrix(asm_list)
>
>
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
