목록의 인접 요소 결합

Question

Newton interpolation formula을 구현하고 싶습니다. 어쩌면 다음 텍스트가 더 이해할 수 있습니다.

목록의 두 이웃을 새로운 값으로 결합하는 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

확실히 새로운 배열 생성을 피할 수 있습니다. 알고리즘을 덮어 쓸 수 있도록이 두 번째 계산에 의해 사용 된 후에는 왼쪽 피연산자 더 이상 이용되지 않는 한 해결책은 아주 간단합니다 : 당신이 정말 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 
} 

어떤 것이 더 빠르는지 확실하지 않습니다. 두 가지 방법을 모두 시도하고 알려주십시오.

희망이 도움이됩니다.