[SciPy-user] Creating a Matrix from a Sum
Tom K.
tpk@kraussfamily....
Fri Jul 3 20:18:40 CDT 2009
David Warde-Farley-2 wrote:
>
>
> On 3-Jul-09, at 2:45 PM, David Warde-Farley wrote:
>
>> On 2-Jul-09, at 9:25 AM, Lorenzo Isella wrote:
>
> Then you want the max of i and j at each position in the matrix. For
> this, though there may be a more efficient way, you can use mgrid to
> get i and j indices at each position in the matrix and then use
> concatenate and max on them to concatenate along a third axis and then
> do a max along that same axis to recover a 2D array:
>
> idx = np.concatenate([M[:,:,np.newaxis] for M in mgrid[0:len(x),
> 0:len(x)]],axis=2).max(axis=2)
>
David this is interesting however I think the use of mgrid followed by
concatenation into a 3D array here is overkill. The idx array is the same
as the max_ij array that I suggested - a one liner for it is
max_ij = np.maximum(np.arange(len(x))[:,np.newaxis], np.arange(len(x)))
This problem involves O(N) sums and O(N^2) assignments. The vectorized
versions that David and I posted (my version 2) are doing just that much
work - however with overhead of several intermediate arrays. A more
straight-forward approach in python is just a double for-loop, which may be
the most readable and perfectly sufficient unless your N is huge and/or this
function becomes the most significant item in a profile of your application.
sums = np.cumsum(x[::-1])[::-1]
P = np.zeros((len(x), len(x))
for i in range(len(x)):
for j in range(len(x)):
P[i, j] = sums[np.max((i, j))]
#Here it is with list comprehensions:
P = np.array([[sums[np.max((i, j))] for j in range(len(x))] for i in
range(len(x))])
By the way I do NOT recommend using the first method I posted in my earlier
post - I think it is doing O(N^3) adds and O(N^3) assigns!
--
View this message in context: http://www.nabble.com/Creating-a-Matrix-from-a-Sum-tp24306698p24330442.html
Sent from the Scipy-User mailing list archive at Nabble.com.
More information about the SciPy-user
mailing list