我有一个算法,但它非常慢。由于我的算法/问题非常简单,我预计这种算法可能已经存在(且速度快),并且可能还有一个名称。在开始开发更快的算法之前,我想先在这里询问一下(我不想重新发明轮子)。
问题很简单:我有一个实验的时间序列,它非常大(约5GB)。事实上,大多数数据点都位于一条线上,例如:
(t=0.0, y=0.0), ... , (t=1.0, y=0.5), ... , (t=2.0, y=1.0)
可以通过用一条直线插值第一个和最后一个点来简化这个问题。原则上,我可以测试一个区间内的点是否可以在某个误差范围内用一条直线逼近,并抛弃其中的点(我不需要无损压缩)。
我的当前算法如下:
1. 我有一个区间[a,b]内的点,并在第一个和最后一个点之间创建一个线性插值(称为f)。 2. 然后,在每个时间序列点处计算误差Abs(f(t) - y),并选择具有最大误差的点(称为tmax)。 3. 将区间[a,b]分裂成[a,tmax]和[tmax,b]。 4. 在子区间上重复我的算法,直到达到容差或区间仅包含一个或两个点。返回区间边界。
这个算法在逼近信号方面表现出色,但速度非常慢。正如我所说的,我相信已经存在一些可以做同样事情或解决我的问题的方法。
如果有任何不清楚的地方,请随时问我。
问题很简单:我有一个实验的时间序列,它非常大(约5GB)。事实上,大多数数据点都位于一条线上,例如:
(t=0.0, y=0.0), ... , (t=1.0, y=0.5), ... , (t=2.0, y=1.0)
可以通过用一条直线插值第一个和最后一个点来简化这个问题。原则上,我可以测试一个区间内的点是否可以在某个误差范围内用一条直线逼近,并抛弃其中的点(我不需要无损压缩)。
我的当前算法如下:
1. 我有一个区间[a,b]内的点,并在第一个和最后一个点之间创建一个线性插值(称为f)。 2. 然后,在每个时间序列点处计算误差Abs(f(t) - y),并选择具有最大误差的点(称为tmax)。 3. 将区间[a,b]分裂成[a,tmax]和[tmax,b]。 4. 在子区间上重复我的算法,直到达到容差或区间仅包含一个或两个点。返回区间边界。
这个算法在逼近信号方面表现出色,但速度非常慢。正如我所说的,我相信已经存在一些可以做同样事情或解决我的问题的方法。
如果有任何不清楚的地方,请随时问我。