Hi Max!



 mzimmer:

Is that really the most efficient way of finding the index of the largest False element of is_le? numel() is probably constant in the size of is_le, but sum() should be linear?


First, yes, sum() is linear.  (But, as an aside, finding the first True
index is also linear, but see below).
The key point is that sum() is implemented as a pytorch tensor
operation, so you get that potentially important benefit.
Note, many libraries offer a find_first type of function for searching
strings or arrays.  I’m not aware that pytorch has such (at least not
in my old version).  One could consider using pytorch’s argmax()
function, but in this case several elements of is_le take on the
maximum value, and I don’t think that pytorch guarantees that
argmax() will return the index of the first maximum element.
Now (other than the initial sort) this entire algorithm is linear.  But
this algorithm looks at the entire sorted vector – whether or not
it needs to.  You only have to calculate your running mean until your
condition is satisfied.  So if your condition is equally likely to be
satisfied anywhere in the vector, then, on average, you would only
have to look at half of sorted and compute only half of the running
mean.  Cheaper, but still linear.
If your condition were strongly-enough biased to occur towards the
beginning of your vector, the algorithm could even become order 1
(“O(1)”), for the average case.  But, given that pytorch doesn’t have
anything built into it that does this for you, you’re almost certainly
better of using the linear – but optimized – pytorch tensor operations,
than writing your own non-tensor loop (even in the hypothetical
average-case O(1) example).
The same comments apply to finding the first True index in is_le.
This, in general, is linear, but could be cheaper in operations if you
run a loop that stops “early” when it finds that index.  But the tensor
operation sum() is likely to be cheaper in time (but not operations),
even in the hypothetical average-case O(1) situation.
Best.
K. Frank