MATLAB Answers

Looking for a faster way of finding the first element larger than a given number in a sorted array

3 ビュー (過去 30 日間)
Tom van den Bosch
Tom van den Bosch 2021 年 8 月 3 日
コメント済み: dpb 2021 年 8 月 8 日
I have a vector
a = [1 1 1.01 1 1.05 1 .... 1]
which is basically all numbers >=1. I also have a vector b that is the cummulative sum of this vector (and thus sorted), so each increment in this vector is at least 1 and sometimes (often) more than 1.
I also have a random number r between 0 and the total sum of a. Now, I need to find the first element k in b that is larger than r.
I am currently using a simple find comment:
k = find(b>r, 1)
However, I feel like it should be possible for this to be faster. Since I know that k should be at least floor(r) as increments in the cumsum vector are at least 1, I have tried
n = floor(r)
k = find(b(n:end)>r, 1) + n-1
But this seems to be slower despite skipping searching the first n enties of b. Is there an build-in option in matlab for starting the search at a certain index? If not, is there any other faster way? This function takes about 65% of my total computing time. a Is a vector of size 10.000 but it changes very often and I have to make this call millions of times.
  6 件のコメント
Tom van den Bosch
Tom van den Bosch 2021 年 8 月 4 日
Thanks for the suggestions all!
I tried sum(b<r) but this was about 30% slower.
I am unsure how the matlab C/C++ compiler works, although I do not doubt that the fastest possible method is through a C++. However, the accepted answer by dpb is sufficient for now as this step is no longer a bottleneck and only takes about 7% of total runtime.



dpb 2021 年 8 月 3 日
With the JIT compiler, loops are pretty quick any fact, with the starting point as the beginning loop index, that may, indeed, be the fastest option. I'd use a counted loop and break though, not the while I think, although you can compare...
for k=floor(r):numel(b)
if b(k)>r, break, end
  3 件のコメント
dpb 2021 年 8 月 8 日
I had a machine failure so have been offline since -- glad to hear that seems to help; I had one additional idea that might be better than the straight loop which would be a binary search starting at the known minimum location. I haven't tried coding it to test; I just got MATLAB reloaded on the new machine and have a lot more to go to get it rebuilt but I just came to check out briefly before going on...


その他の回答 (1 件)

Bruno Luong
Bruno Luong 2021 年 8 月 3 日
編集済み: Bruno Luong 2021 年 8 月 3 日
You might try
k = discretize(r,b);
if b(k) == r
k = k+1;
  1 件のコメント
Tom van den Bosch
Tom van den Bosch 2021 年 8 月 4 日
Thanks! I tried but it seems to be about 3-4 times as slow.





Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by