java在列表中组合相邻元素

Question

我想实现Newton interpolation formula。也许这让下面的文字更有意义

我寻找一个列表函数，它将列表中的每两个邻居组合成一个新值。它应该非常快，并且（如果可能的话）不涉及创建新列表。我想连续多次执行下面描述的缩减，但要获取中间的一些数据

Before: a   b   c   d
         \ / \ / \ /
After:    ab  bc  cd

用于组合的二进制函数应可自由切换

到目前为止，我提出了类似的解决方案（但对于阵列）：

double[] before = {4, 3, 7, 1};

while(before.length > 1){
    double[] after = new double[before.length - 1];

    for (int i = 0; i < after.length; i++){
        after[i] = chosenBinaryFunction(before[i], before[i+1]);
    }

    //store after[0]

    before = after;
}

---

答案“没有比你所做的更好的方法”是可以接受的。在这种情况下，请提供如何改进方法的提示（例如，避免在while中创建大量新列表，可能的快捷方式，…）

Answer 1

对于数组，您几乎可以得到它。 唯一的问题是for循环的条件应该是i<；之后length-1或者，当循环索引（i）到达数组中的最后一个位置时，您将得到IndexOutOfBounds异常，因为您将调用数组中不存在的i+1元素

因此，对于使用列表执行上述操作，您首先从一个在之前的列表开始（例如，让它成为一个ArrayList），该列表包含a、b、c、d、e、f、g等元素。。。。 以下是您要做的：

ArrayList<Integer> after;
while(before.size() > 1){
    after = new ArrayList<>();
    for(int i=0;i<(before.size()-1);i++){
        int joinedValue = joinValuesFunction(before.get(i),before.get(i+1));
        after.add(joinedValue);
    }
    before = after;
}

如果要在计算后立即删除before的元素并将其替换为after的元素，则可以通过重用before列表来避免创建新列表。例如：

while(before.size() > 1){
    for(int i=0;i<(before.size()-1);i++){
        int joinedValue = joinValuesFunction(before.get(i),before.get(i+1));
        before.remove(i); //Remove the element at position i
        before.add(i,joinedValue); //Add the joined value at position i. This will shift all elements of this ArrayList (from i to before.getSize()-1) to the right by one position.
    }
    before.remove(before.size()-1); //Removes the last element
}

但不确定哪一个更快。试着给两种方法计时，并让我们知道

希望这有帮助

Answer 2

如果您确实希望能够选择一个二进制函数，请查看BinaryOperator。特别是BinaryOperator<double>。使用此选项，添加以下行：

BinaryOperator<double> b = ...

然后您可以更改此行：

after[i] = chosenBinaryFunction(before[i], before[i+1]);

为此：

after[i] = bo.apply(before[i], before[i+1])

另外，我认为每次循环时创建一个新数组是浪费。我会做更多类似的事情（完整版）：

double newtonInterpolation(double[] before, BinaryOperator<double> bo) {
    double[] after = new double[before.length - 1] // Creates array ONE time

    for (int i = 0; i < after.length; i++) {
        after[i] = bo.apply(before[i], before[i + 1]) // Uses fancy BinaryOperator
    }

    return after
}

免责声明：我还没有测试这段代码，所以它是按“原样”提供的，但我希望这有帮助

Answer 3

当然，可以避免创建新阵列。解决方案非常简单，因为左操作数在第二次计算时不再使用，因此算法可以覆盖它：

double[] before = {4, 3, 7, 1};
int length = before.length;

while (length > 1) {
      length;
     for (int i = 0; i < length; i++){
         before[i] = chosenBinaryFunction(before[i], before[i+1]);
     }
}