リスト内の隣接要素を結合する

Question

Newton interpolation formulaを実装したいと思います。たぶん、以下のテキストが意味をなさないでしょう。

私はリストの2つの隣人を新しい値に結合するList-Functionを探します。それはかなり速くなければならず（可能であれば）、新しいリストを作成する必要はありません。私は、以下に説明する削減を複数回連続して実行したいが、間にあるデータの一部を取得したい。それが合成される

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

新しい配列の作成を避けることは間違いありません。アルゴリズムはそれを上書きすることができますので、それが第2の演算用で使われていたら、左のオペランドがもう使用されないように、溶液は非常に簡単です：あなたは本当にBinaryOperatorを見て、バイナリ機能を選択できるようにしたい場合は

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]); 
    } 
} 

Answer 2

。特にBinaryOperator<double>。これに

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

：また

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

が、私はそれはあなたが新しい配列を作成することは無駄だと思う

BinaryOperator<double> b = ... 

はその後あなたがこの行を変更することができます。これを利用して、この行を追加します。あなたがループを通過するたびに。それは、「現状のまま」提供されますので、私は、まだこのコードをテストしていませんが、私は、これは助けを願って：

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

あなたはかなり多くの配列を手に入れました。 唯一のことは、forループの条件がであることです。< after.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; 
} 

あなたはできるだけ早く後の要素と前の要素を削除し、代わる場合は、前にリストを再利用して新しいリストを作成しないようにすることができますあなたはそれらを計算します。例：

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 
} 

どちらが速いかわかりません。両方のアプローチに時間をかけて、私たちに知らせてください。

これが役に立ちます。