MATLAB Answers

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

조회 수: 4(최근 30일)
Tom van den Bosch 2021년 8월 3일
댓글: dpb 2021년 8월 8일
Hi,
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표시숨기기 이전 댓글 수: 5
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 more...in 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
end
##### 댓글 수: 3표시숨기기 이전 댓글 수: 2
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 2021년 8월 3일
편집: Bruno Luong 2021년 8월 3일
You might try
k = discretize(r,b);
if b(k) == r
k = k+1;
end
##### 댓글 수: 1표시숨기기 없음
Tom van den Bosch 2021년 8월 4일
Thanks! I tried but it seems to be about 3-4 times as slow.

댓글을 달려면 로그인하십시오.

R2019a

### Community Treasure Hunt

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

Start Hunting!

Translated by