get index of maximum in matrix (with gen?)
This has been asked before, but there doesn't seem to be a clean and efficient way to get the index/coordinates of the maximum in a jitter matrix.
In my case it's from a 1D matrix output by jit.histogram, to get the mode of the histogram. With ftm, it used to be as simple as:[ftm.jitter fmat]
|
(($1 rowref) maxi)
I wonder if this can be done in jit.gen, outputting the running max index, but I don't even know how to have a local variable to store the current maximum. Something like
if (in1 > max)
{
max = in1;
maxi = norm;
}
out1 = maxi;
Any help appreciated. Cheers!
salut Diemo,
jit.spill=> maximum does the job.
Not sure this is the most efficient way though...
not sure...
1. how can `maximum` give me the index/coordinates of where the maximum value is in the matrix?
2. copying to a max list is definitely not efficient
I think (I may be wrong here) the output of jit.gen is always a matrix, so if you're looking for an integer output, you may be out of luck. Even if it output a matrix like [0 0 0 0 1 0 0 0], you'd still have to spill it....
another reason we miss FTM!
\M
the output of jit.gen is always a matrix
that's one of the few things I understood about jit.gen =-) I though of generating an output matrix the same size as the input with the running current max and index, so the final result is in the last cell.
The problem is, I'd have to write AND read this matrix, which I don't know if it is possible at all.
No jit.gen expert myself, I believe it really just thinks in terms of entire vectors, so I don't even know if your idea is possible -- I'll let someone more knowledgable than I am to weigh in on that.
I've been in several situations over the years where I've wanted to be able to get a cell address that matched some criterion, and Jitter really isn't designed to think that way, unfortunately -- I always wound up going back to zl objects if it was a 1-d problem. Does it have to be in a Jitter matrix? if you can store your values in a buffer~ you could use [mxj buf.Op] & send it the 'max' message, which returns the index and value of the maximum sample....
\M
I would say as Mattyo, I think jit.gen does process entire vectors, so even if it could theoretically be possible to use the "sample" operator in a codebox's loop to search the max, I suspect this operation would be repeated for each vector, so even less efficient. That said, I'm not entirely sure of this and would be glad to be proven wrong.
If you really need to remain in the jit.matrix domain, the overlooked "jit.dimop" object can return the maximum (more efficiently than jit.3m, that is)... but no coords, so you would then need to compare it against you input matrix and AND it with a coordinate matrix.... so most probably less efficiently than jit.spilling it in the end...
I wonder if it might be faster to create the matrix you are sending your data to in js, and do the max in there? just a whacky idea....
\M
is there a jit.matrix to buffer~ thingy? (I don't even dare to ask for it to be efficient anymore...)
jit.buffer~ ?
This is a kind of map-reduce class of problem that something like jit.gen isn't primarily designed for -- (jit.gen is really focused on data-parallel processing, which is the map part, whereas the reduce part is a serial process).
That said, there *is* a way to do it. Since you only want one vector output (the matrix coordinates), pass a 1x1 matrix into the jit.gen left input. The output matrix will thus also be 1x1.
Pass the matrix you want to search in the right input. (Maybe this requires @adapt 0, I can't remember and can't test right now).
Inside the gen you can make a codebox with for loops over the dimensions of the 2nd input, reading each value using the `nearest` operator.
In graphics terms, you are rendering a single pixel, and for that pixel you are looping over every texel of the texture at input 2.
Graham
Here's an example:
Slick!
\M
ha, that's smart!
I was curious to see how much the gain with this solution, and oddly enough, this is about exactly the same as jit.spilling and using [maximum]. Of course, for larger matrices, you'd hit the zlmaxsize soon.
And for a single dimension it appears to be much slower. (⊙＿⊙')
Or am I missing something here ?
Ouch! I got 45.559 _seconds_ using gen, and 33ms with zl.
If you're only using a 1D matrix, then don't use a 2D algorithm!
With the 1D-version patcher below, I get 33ms using [maximum], and 17ms using jit.gen :-)
I'd guess the problem with the 1D patch is that h = swiz(in1, 1) from a 1 elem vector in1 will repeat w, and so do 10000 x 10000 iterations.
For me, the jit.gen solution is ~10% slower than jit.spill, which is astounding, but the winner is ... wait for it ... the ftm solution, which is twice as fast!!!
Now, can gen run faster on the GPU?
@graham : you're right, that's a bit faster with the correct code adapation, my bad!
@diemo : do you mean there exists a working version of ftm for Max8 ?
Hi Diemo,
Just using old-fashioned handwork with gen is about equally fast as ftm on my machine. 30 ms is used by noise generation by the way, so the difference in finding the maximum is even more dramatic than you mentioned.
You see that I also jumped to gen as you advised.
Best, Hans.
Hi all, thanks for your great responses! I put everything together in a proper benchmark.
There are worst/avg/best cases for the input (which don't make a difference).
FTM and jit.buffer are 4x as fast as jit.spill, which is 2x faster than jit.gen.
Can this be due to additional internal matrix copies?
@Graham: the jit.gen solution spends 50% CPU copying the result to the two 1x1 output matrices.
@Hans: great tip! but I don't get correct results after my adaptation below
@vincent: sure, ftm works on 64bit Intel Max, but not M1: https://forum.ircam.fr/projects/releases/ftm/
Cheers!
Here's another approach, using jit.3m, jit.==, and xray.jit.cellcoords. I didn't benchmark this but I suspect it would be pretty performant. An advantage to this approach is that you derive the indices of all cells in the matrix that are the maximum value, output as a list.
Hi Jesse, thanks for remining me of which xray object could be used here.
Unfortunately, for finding the first max, that approach is far from the theoretical optimum of one in-place iteration, as it does 3 iterations and at least 2 copies (jit.3m, jit.==, xray.jit.cellcoords), and thus it is 10x slower than the two fastest solutions.
Even for finding all the indices, the theoretical optimum would only need two in-place iterations (and no copy).
Here's the updated benchmark (also replacing timer by the slightly more accurate cpuclock):
This might be a bit more convincing if the jit.buffer~ example was producing correct results... on my machine it consistently spits out indices that are incorrect.
If you don't have to use jit.gen to do this, there are often basic objects meant for this kind of thing.
jit.findbounds might be what you're looking for (1d or 2d)?
It can be used to find bounding boxes, or single cells in matrices.
Very simple workflow,
use jit.dimop @step -1 -1 @op max, or jit.3m, to get max value,
then set min-max attributes in jit.findbounds, with your max value.
then output matrix to jit.findbounds, which gives you the 1d/2d coordinates.
Haven't tested speed, but I suspect it to do fine, especially for larger matrices, since it should be a more general approach, not limited by zl listlength limits etc.
Most jitter objects should use some type of SIMD optimization, while zl does not as far as I know.
Another fast approach for matrix downsampling or finding averages, could be using shader mipmaps? jit.gl for GPU processing.
Possibly fast summed area tables, or integral images, O(log n) time?
Not the exact same usecase but useful none the less.
Thanks for this solution, using built-in jitter objects, @Gussi. It is 10 x slower than jit.buffer~ with gen.
Below is the updated shoot-out patch. It would indeed be interesting (in theory, because for practical applications it is largely fast enough...) to see if this problem could be solved on GPU (parallel search for max value per sub-block of the matrix).