Overlapping time-intervals WITHOUT for/while loops? (2024)

This exercise forms a small part of a high-frequency trading system I am building, based on lead/lag linkages across stock index futures markets. This is one of my postdoctoral projects, and is certainly not "a HW".

Doing it with nested while-loops is easy, but array tools will enable better parallelism and possibly move onto the GPU later. This is why I ask the question here.

I appreciate your hints, but it is not an answer. Therefore, in this case I cannot click "accept" or "vote" in favor of what you have written. You may wish to delete your answer so that others can have an opportunity to contribute. Many thanks for your guidance. Best wishes.

Ok, my apologize for the mistake; you write " solution cannot contain for/while loops", which looks quite much like the HW statements that we often see here. I guess that it is the reason why you got no answer before I decided to post a few hints. I updated my original list of hints with an answer based on c*msUM.

Many thanks for your contribution. The code runs well for large arrays and faster than my nested while loops. However, there is a problem with your code. If you pass in another test set, suppose

then your program yields

whereas the correct solution given by the nested loop is

Note that "overlaps" contains "oo", but this is not always true particularly for large arrays. Note also that "overlaps" in this case contains zeros and fours. Adding a leading 0 to A and B mitigates this problem, but still yields incorrect intervals. I have not had time to go through the code in detail, but I would say your solution comes VERY close to solving this puzzle. I thank you for that.

The best I can do at this point is to explain how the code works, so you can tailor it to your needs.

The principle is to create vectors of time interval IDs with a step of one ID per second (as boundaries seem to be integers), and to extract unique configurations when we pair these vectors for a and b.

Taking

we want to build the following vector of 10 interval IDs:

Note that we should works with column vectors, but I make examples using row vectors because it is simpler to display on the forum. One way to achieve this (intId_a) is to create a vector of zeros ans set to 1 elements that correspond to interval boundaries. For that, we can use a+1 as an index (as a starts at 0):

and compute a cumulative sum of its elements:

Doing the same for b, we get:

Now if we CAT them together:

you realize that it is roughly your solution, but that we should eliminate (at least) columns that appear multiple times. We can do this using UNIQUE on the transpose of this array, setting it up to return unique rows:

You see that this solution is valid if a and b both start at the same instant and that this instant is t=0 (we use a+1 and b+1 for this reason). We also used the same length of 10 for both vectors intId_a and intId_b, which is the overall max time boundary+1. Finally, you see that the end of the intervals is given an ID (5) in this process.

The difference between this example and my solution is that in the latter I compute this 10 as m=1+max([a,b]) and I use linear indexing in a 2D array of zeros in place of CAT-ing intermediary variables, which hopefully makes it more efficient.

Now it's easy to tailor this to your needs, e.g. if the assumption that both a and b start at t=0 falls, or even worse, that they don't start at the same instant. One way to achieve this could be..

now this code will make it possible to work with negative times, or very large initial times, but it will leave ID=0 at the beginning if both time ranges start at different times. This is a good behavior as it tells that for an interval in a given vector there is no vis-a-vis in the other vector. Running it with e.g.

gives

which makes sense as the intervals [100-101[, [101-102[, and a chunk of [102-103[ in a have no vis-a-vis in b. The same happens at the end of intervals and in some sense you don't want the smallest of the upper boundaries to be given an interval ID. So we have to filter these 'boundary cases' out.

There are three options for that: pre-processing the inputs to prevent boundary cases to create unwanted solutions, trying to complexify a bit the code that described above so the computation manages boundary cases, and last, post-processing the output to eliminate unwanted cases.

Here is an example how to code the first option, where we reduce a and b to their contiguous part and eliminate the upper boundaries so they don't add interval IDs.

This code outputs:

respectively for the first and second cases that you submitted.

Note that a feature (maybe unwanted) of this solution is that interval IDs start (at 1) at the first overlap, so intervals of b that cover times before the lowest boundary of a would not be counted.

If you fully understand what we've done here, it won't be complicated to finalize tailoring this approach to your needs.

Many thanks for your answer!

My pleasure!

Note that I added 'stable' in the call to UNIQUE (which prevents this function to order its output) and I am not sure that you need/want it.

I just realized that with the preprocessing, you can get a little improvement by replacing the line

with

Thank you for the link, it is always interesting to see in which context what we help coding is finally used!

Best wishes,

Cedric

Cedric, a further MATLAB challenge awaits you, if you feel up to it!

Best wishes, Hamad

It's your homework problem. Don't you feel up to it? Why challenge Cedric to do it for you? At least put some effort into it and show some attempt at solving it, and then we can correct that or suggest improvements to it. Anyway, I did give you a hint. It's your move now.

Yes, but you have to add the correct offsets when building intId, for example

The best way to understand the approach is to run my original example and to display intId before the call to c*msUM and after. Running

we get

This shows that we built an array of zeros with 1s at locations where the interval changes. Then, by using c*msUM along dimension 1, we get interval IDs (see the doc of c*msUM to understand why if needed):

which outputs:

Now this output has duplicates (each row that has no interval change has the same values as the row above), so we pass it to UNIQUE (by row) to get only the rows with changes.

Back to the first block of code, we see that one way to place the 1s without computing the row/col indices of each 1 (which is easy to do but unnecessary), is to use vectors a and b as linear indices (again, seach for that topic online if you are not familiar). For this, however, we must add an offset to b to get values that index linearly the second column of intId, and this offset is the number of rows, m. If we needed a 3rd, 4th, etc column, for extra vectors c, d, etc., we would just have to add the correct offsets (2*m , 3*m, etc.), which is what the expression at the top of this comment does.

Now if vectors don't all start at 0 or have different lengths, it is no big deal but you have to undertsand the approach and update the code a bit, as illustrated in my comments to Hamad.

Thank you Cedric! Your code works. I appreciete your time on this question.