通常如何实现数据集的线性插值? [英] How is linear interpolation of data sets usually implemented?

问题描述

假设给定了(x，y)值中的一堆点，并且您需要通过在x轴上的两个最接近的值之间线性插值来生成点，那么最快的实现方法是什么?

Suppose if you are given a bunch of points in (x,y) values and you need to generate points by linearly interpolate between the 2 nearest values in the x axis, what is the fastest implementation to do so?

我四处搜寻，但找不到满意的答案，我之所以这样，是因为我没有寻找正确的单词.

I searched around but I was unable to find a satisfactory answer, I feel its because I wasnt searching for the right words.

例如，如果给定我(0,0)(0.5，1)(1，0.5)，那么我想得到一个0.7的值；它应该是(0.7-0.5)/(1-0.5)*(0.5-1)+1;但是什么样的数据结构可以让我找到两个最接近的键值以在两者之间进行插补?如果我有很多键值，那么最好的方法就是简单的线性搜索/二进制搜索吗?

For example, if I was given (0,0) (0.5 , 1) (1, 0.5), then I want to get a value at 0.7; it would be (0.7-0.5)/(1-0.5) * (0.5-1) + 1; but what data structure would allow me to find the 2 nearest key values to interpolate in between? Is a simple linear search/ binary search if I have many key values the best I could do?

推荐答案

我通常实现O(1)插值的方式是通过附加的数据结构，我将其称为IntervalSelector，这样在O(1)的时间给出必须内插的序列的两个周围值.

The way I usually implement O(1) interpolation is by means of an additional data structure, which I call IntervalSelector that in time O(1) will give the two surrounding values of the sequence that have to be interpolated.

IntervalSelector是一个类，当给定sequence为n时，横坐标会生成并记住一个table，它将把任何给定的x值映射到索引i，从而使在时间O(1)中.

An IntervalSelector is a class that, when given a sequence of n abscissas builds and remembers a table that will map any given value of x to the index i such that sequence[i] <= x < sequence[i+1] in time O(1).

注意:在下面的数组中，基于1的数组.

Note: In what follows arrays are 1 based.

构建表的算法如下:

1. 找到delta为横坐标输入sequence中两个连续元素之间的最小距离.
2. 设置count := (b-a)/delta + 1，其中a和b分别是(升序)sequence和/的第一个和最后一个，代表除法的整数商.
3. 将table定义为count个元素的Array.
4. 对于1和n之间的i，设置table[(sequence[j]-a)/delta + 1] := j.
5. 将在4中访问过的table的每个条目重复到紧随其后的未访问位置.

1. Find delta to be the minimum distance between two consecutive elements in the input sequence of abscissas.
2. Set count := (b-a)/delta + 1, where a and b are respectively the first and last of the (ascending) sequence and / stands for the integer quotient of the division.
3. Define table to be an Array of count elements.
4. For i between 1 and n set table[(sequence[j]-a)/delta + 1] := j.
5. Repeat every entry of table visited in 4 to the unvisited positions that come right after it.

在输出中，如果(j-1)*d <= sequence[i] - a < j*d.

这里是一个例子:

由于元素3 ^rd 和4 ^th 是最接近的元素，因此我们将间隔划分为该最小长度的子间隔.现在，我们记得在table中每个deta-间隔的左端位置.稍后，当给出输入x时，我们将x的delta-间隔计算为(x-a)/delta + 1，并使用该表推导序列中的相应间隔.如果x位于第i个序列元素的左侧，则选择第(i-1)个.

Since elements 3^rd and 4^th are the closest ones, we divide the interval in subintervals of this smallest length. Now, we remember in the table the positions of the left end of each of these deta-intervals. Later on, when an input x is given, we compute the delta-interval of such x as (x-a)/delta + 1 and use the table to deduce the corresponding interval in the sequence. If x falls to the left of the ith sequence element, we choose the (i-1)th.

更准确地说:

给出a和b之间的任何输入x，计算j := (x-a)/delta + 1和i := table[j]..如果x < sequence[i]放i := i - 1.然后，索引i满足sequence[i] <= x < sequence[i+1]；否则，这两个连续元素之间的距离将小于delta，而不是.

Given any input x between a and b calculate j := (x-a)/delta + 1 and i := table[j]. If x < sequence[i] put i := i - 1. Then, the index i satisfies sequence[i] <= x < sequence[i+1]; otherwise the distance between these two consecutive elements would be smaller than delta, which is not.

备注:请注意，如果sequence中连续元素之间的最小距离delta太小，则表中的条目将太多.我在这里给出的简单描述忽略了这些病理情况，这需要额外的工作.

Remark: Be aware that if the minimum distance delta between consecutive elements in sequence is too small the table will have too many entries. The simple description I've presented here ignores these pathological cases, which require additional work.

这篇关于通常如何实现数据集的线性插值?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！