Объединить соседние элементы в списке

Question

Я хочу реализовать Newton interpolation formula. Возможно, это дает следующий текст больше смысла.

Я ищу список-функцию, которая объединяет каждый из двух соседей в списке с новым значением. Это должно быть довольно быстро и (если возможно) не включать создание новых списков. Я хочу выполнить сокращение, описанное ниже несколько раз подряд, но захватить некоторые данные между ними.

Бинарная функция, с которой она объединена, должна быть свободно переключаемой.

До сих пор я придумал что-то вроде этого (но для массивов):

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

Определенно можно избежать создания новых массивов. Решение довольно просто, так как левый операнд больше не используется, как только он используется для второго вычисления таким образом, алгоритм может перезаписать:

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 , Конкретно 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

Вы в значительной степени получили его для массивов. Единственное условие вашего цикла for должно быть i < after.length-1, или если индекс цикла (i) достигнет последней позиции в вашем массиве, вы получите исключение IndexOutOfBounds, поскольку вы будете вызывать элемент i + 1 в вашем массиве, который не существует.

Так что для выполнения вышеописанных вещей со списками вы начинаете со списком до (пусть это будет ArrayList, например), то есть элементы а, б, в, г, д, е, г,. ... Вот что вы делаете:

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 
} 

Не уверен, что быстрее. Попытайтесь примерить оба подхода и сообщите нам об этом.

Надеюсь, это поможет.