Refactor `_compute_diagonal` in `stumpy.stump`

[seanlaw]

In these lines of _compute_diagonal:

https://github.com/TDAmeritrade/stumpy/blob/1d98e48d45eee7988a8df946b0c1c40857470ee7/stumpy/stump.py#L157-L161

These terms:

a = ((T_A[i + k + m - 1] - M_T_m_1[i + k])
b = (T_B[i + m - 1] - μ_Q_m_1[i])
c = (T_A[i + k - 1] - M_T_m_1[i + k])
d = (T_B[i - 1] - μ_Q_m_1[i]))

can technically be pre-computed. We just need to figure out how to align them properly with any i, k, pair and pre-compute them in stumpy._stump and pass in a, b, c, d as pre-computed vectors for re-use. This should speed up the performance of larger inputs.

[seanlaw]

@mexxexx I'm rather bad at this kind of index tracking. Any chance you could help take a look?

[seanlaw]

Never mind, it took a little bit of patience but I figured it out:

a = T_A[m - 1:] - M_T_m_1[:-1]
b = T_B[m - 1:] - μ_Q_m_1[:-1]
c = np.roll(T_A, 1)
c = c[:M_T_m_1.shape[0]] - M_T_m_1[:]
d = np.roll(T_B, 1)
d = d[:μ_Q_m_1.shape[0]] - μ_Q_m_1[:]

And then the covariance line simplifies to something that is much, much nicer to read:

cov = cov + constant * ( a[i + k] * b[i] -  c[i + k] * d[i])

[seanlaw]

This change seems to make things around 20%-25%+ faster for times series that are 100K+

n: 131072  stump_old: 50.2567s  stump_new: 40.751s  stump/stump_opt: 1.23x
n: 262144  stump_old: 195.2141s  stump_new: 152.8601s  stump/stump_opt: 1.28x

And, as a result, our unit tests seem to be completing faster too! Yay!

[mihailescum]

That's impressive, great you could figure it out! It would have taken me a lot more time to understand what is going on 😃