1

我正在阅读成对的数据（xValues, yValues），我想知道存储它们的最佳方式是什么。目前我List<double>, ObservableCollection不需要这样做，因为数据将在程序运行时保持不变。但我需要能够对几个（两个）数据源进行一些操作。由于xValues这两个来源之间可能不一样，因此我需要线性插值。

我读过诸如Dictionary,LinkedList等之类的东西，我对我需要什么以及什么更适合这个小项目感到困惑。

当我开始制作填充缺失数据点的方法时，我遇到了几个困难：

我需要检查 series1 中的每个点是否与 series2xValue中的相同，但是由于 xValues 是有序的，我认为检查整个列表中的每个值都会对性能造成很大的损害，只是说，不，没有那个xValue，让我们插值并插入那个新点。

我怎么能在两个没有给定索引但值（x2>x1）之间准确插入一个点。

我认为当您在编程中使用 2D 数据点时，这是一个常见问题，您是否知道 C# 中是否实现了某些东西，或者是否有代码可以激发我的灵感？

4

1 回答 1

0

您想使用 XY 对的排序列表（List<Tuple<double,double>>这将是合适的类型）。假设您有两个输入列表 series1 和 series2，它们按 X 值排序，并且您正在检查 series2（并且可能是插值）以查找 series1 中存在的 X 值（正如您在问题中所述）。因为您需要检查 series1 中的每个坐标，所以最小复杂度为 O(n)。

保持这种效率的关键是列表是有序的，这意味着您不必在整个 series2 列表中搜索 series1 中的每个 X 值。为此，您可以保留指向 series2 中当前项目的指针，并在遍历 series1 时移动它。这是伪 C# 来说明我的意思。

var s2idx = 0;
foreach(s1 in series1)
{
    // go forward through series2 until you find the next interp target
    while(series2[s2dix].Item1 < s1.Item1 && s2idx < series2.Length)
        s2idx++;
    if(s2idx == series2.Length)
        // all s1 Xs are > the biggest s2 X, so just add the rest of the s1 points to your output 
        // or whatever else you want to do, then quit the foreach loop
    var s2 = series2[s2idx];
    if(s1.Item1 == s2.Item1)
        // Xs are equal, handle this case as you like
    else
        // calculate the interpolated point and put it in your output
}

我已经使用数组列表展示了这一点，但是您可以使用链表同样有效地做到这一点；只需使用“当前”指针来跟踪您在 series2 中的位置而不是索引。

这里的复杂性是 O(m + n)，因为您每个列表都遍历一次（在最坏和 [最可能] 平均情况下）。最好的情况是 O(n)，但这只会发生在退化的实例中（所有 series1 X 值都大于最小的 series2 X 值，或者 series2 为空）。请记住，这需要对两个列表进行排序，因此您正在查看 O(m + n + m log m + n log n) 全部内容。请注意，这种复杂性主要由排序成本决定，这意味着它非常有效。

于 2016-01-06T21:26:39.673 回答