Better Patter Meter

又一个（大概会更准确的）乐曲速度检测，基于 HTML/JavaScript
Yet another probably-more-precise music tempo analysis based on HTML/JavaScript
さらにもう一つのテンポアナライザ、おそらくより正確になります。HTML/JavaScript に基づきます

✔️ Alpha version released

啊啊啊不要在意这混乱的代码(/_<) 有空一定会整理的！(/_<)

算法

咦这里有一篇大大们的论文qwq

田 垅,刘宗田.最小二乘法分段直线拟合[J].计算机科学,2012,39(Z6):482-484

（话说泥萌给了个算法都不分析复杂度啊啊啊啊啊

然后窝们发现可以还可以改进。。用 DP 解决全局最小值。。。嗯

动态规划

假设窝们收到了 n 次拍击。

用 est[i, j] 和 err[i, j] 分别表示 i .. j 号点的 SLR 斜率值和误差值（取 1 - PCC⁶）。
用 f[i, k] 表示 0 .. i 号点分成 k 段的最小代价（误差值总和）。

那末有边界条件：f[-1, 0] = 0（还好 JavaScript 支持负下标ww）

然后使用 push 类型的状态转移方程：
f[i, k] + err[i + 1, j] --min-→ f[j, k + 1]
对于每个 i, k，枚举 j = i + 8 .. N - 1 转移即可（+8 是为了防止各种乱入的小段）

最后对每一个 k，对 f[n - 1, k] 进行一下估价 Eval(k, f[n - 1, k]) 然后取最优值就可以啦～
其实只要取 f[n - 1, k] 的最小值就可以了…
状态转移的时候记录下前驱就可以方便地得到转移路线从而获得具体分段方案～

时间复杂度 O(n² · k_max)

普通地优化一下

窝们发现前面拍击的时候程序一直闲着没事做 = =
让它一边接受拍击一边算 DP 吧！

普通地瞄了一眼之后发现转移方程可以改成 pull：
f[i, k] = min[0 <= j < i - 8] { f[j, k - 1] + err[j + 1, i] }

然后窝们就可以愉快地在第 i 次拍击之后算出 f[i, *] 的值啦～单次拍击处理过程时间复杂度 O(n · k_max)

实现的时候为避免段间衔接时出现奇怪的误差，计算所有 err 的时候都截去了头尾各两个记录点

线性回归

est 和 err 的值怎么办捏？
显然也可以在拍击的同时计算嘛。用数组存存就好了。

单次拍击需要计算 O(n) 次线性回归，每次的时间复杂度都是 O(n)
单次时间复杂度 O(n²)，总空间复杂度 O(n²)
于是乎敲了大概几百下之后就会卡得不行。。内存也会爆炸。。。

呃。。其实由于这里线性回归的 x 值就是 0 ~ n-1，所以平均值啊什么 Σ_x__iy_i 啊都是可以用前缀和计算的。。。
普通地往普通的 SLR 里面塞了好几种前缀和之后发现斜率和 PCC 值都可以在 O(1) 时间内算出来了。。而且这样一来也不用 O(n²) 的数组存了。。
（一股黑科技的气息迎面袭来）

然后发现还可以在第 i 次拍击的同时就算出所有 est[j, i] 和 err[j, i]，时间复杂度 O(n)
嘛然后就愉快地解决啦

最终渐进时间复杂度 O(n² · k_max)，但是单次拍击的处理时间为 O(n · k_max)。
空间复杂度 O(n · k_max)。
具体实现中取 k_max=10。（窝不觉得会有某首曲子有10段以上不同速度的段 > <）
可以顺利处理大约 50,000 次拍击的规模。（无聊的人(tes-)类(ter)们啊这么多够不。。）