Summing arrayelements up with init, elements, steps-CodePudding

Hi Im searching a fast dynamic programming / formula solution. For following algorithm, example:

init := 1

elements := 4

steps := 3

step 1. [1,1,1,1] init is placed in each index

step 2. [1,2,3] index i is calculated by sum of former step index 0 until inclusive step 1 index i, arraysize get's decremented by one.

step 3. [1,3] Same procedere like step 2 but using step 2 as base.

final step solution := 4 final step is summing up last stepelements.

Is there a faster way than summing up manually?

Sample Code:

long calc(int init,int elements,int steps){
  int[] dp1 = new int[elements-1];
  Arrays.fill(dp1, init);
  int[] dp2 = new int[elements-1];

  for(int i = 0; i < steps-1; i  ){
    for(int j = 0,cur = 0; j < elements-i-1; j  ){
      dp2[j] = cur = cur   dp1[j];
    }
    System.arraycopy(dp2,0,dp1,0,elements-i-1);
    Arrays.fill(dp2, 0);
  }
  return Arrays.stream(Arrays.copyOf(dp1,elements-steps 1)).sum();
}

CodePudding user response：

You're doing a lot of copying and filling where none is necessary. Try it like this.

static long myCalc(int init, int elements, int steps) {
    if (steps > elements 1) {
        System.out.println("Steps too large for # of elements");
        return -1;
    }
    int[] dp1 = new int[elements - 1];
    Arrays.fill(dp1, init);
    int len = dp1.length;
    for (int j = 0; j < steps - 1; j  ) {
        for (int i = 1; i < len; i  ) {
            dp1[i] = dp1[i - 1]   dp1[i];
        }
        len--;
    }
    return Arrays.stream(dp1).limit(len 1).sum();
}

Added improvement. For each step, one less value is added. So adjust the for loop iterations to accommodate.

CodePudding user response：

You might want to look at the Arrays.parallelPrefix method. From the java doc:

Cumulates, in parallel, each element of the given array in place, using the supplied function. For example if the array initially holds [2, 1, 0, 3] and the operation performs addition, then upon return the array holds [2, 3, 3, 6]. Parallel prefix computation is usually more efficient than sequential loops for large arrays.

So something like below might be what you are looking for :

long calc(int init,int elements,int steps){
    int[] arr = new int[elements];
    Arrays.fill(arr,init);

    int[] curr = arr;
    for (int i = 1; i < steps; i  ){
        Arrays.parallelPrefix(curr, Integer::sum);
        curr = Arrays.copyOf(curr,curr.length-1);
        System.out.println(Arrays.toString(curr)); // just to check the sub steps, remove if I get the discription of the steps right
    }
    return Arrays.stream(curr).sum();
}