求周期长度

比较简便的做法是用 FFT,然后根据能量分布估计就有结果了。这里用了个诡异的做法。如果我们有个周期的范围,比如 \mathcal{T} = \{ 2, 4, 6, ..., 10\},然后我们需要选择最合适的,那么我们可以构造一个 queue,比如 size 是 T = 2 \max \{ t \in \mathcal{T}\},这样我们令 q_i 代表这里面的元素。当 t \leq T,我们仅仅做积累工作,之后我们更新。我们为每个可能的周期计算对应的 cost:

\displaystyle C(t) = \frac{1}{T - t}\sum_{i = 1}^{T - t} \ell (q_i, q_{i + t})

其中的差异函数 \ell 可以用诸如 L^1 距离等。如果我们选择的周期比较合适,q_iq_{i + t} 的差就会比较小。你说这样做的好处是什么?嗯,好处是可以使用增量式更新:

\displaystyle C(t) \gets C(t) - \frac{1}{T - t} \big(\ell(q_0, q_{t-1}) - \ell (q_{T-t}, q_T) \big)

其中 q_0 是出队的那个元素值。这个方法 work 吗?我们看看数据哈

数据

我们这个方法如果使用 30 长度的 queue,得到的结果还是很不错的:

[debug] 30: 11 estimated
[debug] 31: 11 estimated
[debug] 32: 12 estimated
[debug] 33: 12 estimated
[debug] 34: 12 estimated
[debug] 35: 12 estimated
[debug] 36: 12 estimated
[debug] 37: 12 estimated
[debug] 38: 12 estimated
[debug] 39: 12 estimated
[debug] 40: 12 estimated
[debug] 41: 12 estimated
[debug] 42: 12 estimated
[debug] 43: 12 estimated
[debug] 44: 11 estimated
[debug] 45: 11 estimated
[debug] 46: 11 estimated
[debug] 47: 11 estimated
[debug] 48: 11 estimated
[debug] 49: 11 estimated
[debug] 50: 11 estimated
[debug] 51: 11 estimated
[debug] 52: 11 estimated
[debug] 53: 11 estimated
[debug] 54: 11 estimated
[debug] 55: 11 estimated
[debug] 56: 11 estimated
[debug] 57: 11 estimated
[debug] 58: 11 estimated
[debug] 59: 11 estimated
[debug] 60: 11 estimated
[debug] 61: 11 estimated
[debug] 62: 11 estimated
[debug] 63: 11 estimated

其实还有一个更直接的策略,数波峰波谷数!比如数据是 a_i, i = 1, \ldots, 64,然后计算差分 b_i = a_i - a_{i + 1},然后相邻相乘 c_i = \mathrm{sign}\, b_i b_{i + 1},我们在结果里面数数连续 -1 的个数即可。像以上数据得到的是 13。

——————
Then Abimelech called Abraham, and said to him, What have you done to us? and what have I offended you, that you have brought on me and on my kingdom a great sin? you have done deeds to me that ought not to be done.

Advertisements
求周期长度

一个有关“求周期长度”的想法

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s