CODEWITHSUNDEEP
javaarraysvectorization
James L
James L

Reputation: 138

How to perform element-wise addition of n arrays without simply using a for loop in Java

As the title suggests, I am wondering how to use Java to sum n (where n is an arbitrary number greater than 2) arrays together, in a way that scales as n increases.

It's probably easiest to explain with an example. I used the following code to produce 20 length-5 arrays.

int n = 20;
int k = 5;

Random rand = new Random();
ArrayList<Integer[]> tuplesList = new ArrayList<>();

for (int i = 0; i < n; i++) {
    Integer[] tuple = new Integer[k];
    Arrays.setAll(tuple, index -> rand.nextInt(30));
    tuplesList.set(i, tuple);
}

Now to the bit I am hoping can be improved. My current method of adding arrays together element-wise consists of simply looping through each array and adding their elements to a cumulative sum. 

int[] cumSum = new int[k];

for (Integer[] tup : tuplesList) {
    Arrays.setAll(cumSum, ind -> cumSum[ind] + tup[ind]);
}

System.out.println(Arrays.toString(cumSum));

This is of course trivial with only 20 arrays, but can be pretty time-consuming if we had 1,000,000. Is there a better way to do this? I have a vectorised way of summing two arrays element-wise using the Arrays.setAll function, but can this be genericised to adding n arrays together? Note that there is no requirement for the list of arrays don't have to be stored as an ArrayList<Integer[]>, that's just where my mind first went to.

P.S. If anyone wants some example numbers, here's what I got when I ran through my script:

[12, 20, 12, 22, 14]
[1, 10, 23, 9, 27]
[3, 2, 17, 24, 11]
[6, 11, 22, 5, 15]
[7, 26, 28, 27, 8]
[10, 23, 2, 15, 7]
[13, 5, 19, 3, 9]
[21, 23, 17, 16, 24]
[4, 20, 6, 14, 14]
[19, 4, 16, 24, 4]
[27, 14, 28, 0, 17]
[27, 20, 3, 8, 29]
[2, 21, 0, 24, 26]
[3, 2, 1, 23, 23]
[11, 11, 15, 26, 17]
[10, 26, 10, 8, 3]
[3, 27, 11, 13, 28]
[1, 29, 26, 3, 14]
[20, 1, 10, 29, 8]
[11, 25, 29, 28, 5]

Output:
[211, 320, 295, 321, 303]

Upvotes: 0

Views: 407

Answers (1)

Andreas
Andreas

Reputation: 159106

If you have 1,000,000 arrays, you might want to think about saving memory by using a ArrayList<int[]> instead, or maybe an int[][].

If you did change to int[][], the absolute most efficient way to do it is like this:

static int[] sum(int[]... input) {
    int maxLen = 0;
    for (int[] arr : input)
        if (arr.length > maxLen)
            maxLen = arr.length;
    int[] sum = new int[maxLen];
    for (int[] arr : input)
        for (int i = 0; i < arr.length; i++)
            sum[i] += arr[i];
    return sum;
}

The first half can of course be replaced with maxLen = input[0].length if it is absolutely guaranteed that all arrays are equal length. Since the performance impact of that code is minimal compared to the second half of the code, we might as well keep the first half, even with such a guarantee (defensive programming).

Test

System.out.println(Arrays.toString(sum(
        new int[] { 12, 20, 12, 22, 14 },
        new int[] { 1, 10, 23, 9, 27 },
        new int[] { 3, 2, 17, 24, 11 },
        new int[] { 6, 11, 22, 5, 15 },
        new int[] { 7, 26, 28, 27, 8 },
        new int[] { 10, 23, 2, 15, 7 },
        new int[] { 13, 5, 19, 3, 9 },
        new int[] { 21, 23, 17, 16, 24 },
        new int[] { 4, 20, 6, 14, 14 },
        new int[] { 19, 4, 16, 24, 4 },
        new int[] { 27, 14, 28, 0, 17 },
        new int[] { 27, 20, 3, 8, 29 },
        new int[] { 2, 21, 0, 24, 26 },
        new int[] { 3, 2, 1, 23, 23 },
        new int[] { 11, 11, 15, 26, 17 },
        new int[] { 10, 26, 10, 8, 3 },
        new int[] { 3, 27, 11, 13, 28 },
        new int[] { 1, 29, 26, 3, 14 },
        new int[] { 20, 1, 10, 29, 8 },
        new int[] { 11, 25, 29, 28, 5 }
)));

Output

[211, 320, 295, 321, 303]

Upvotes: 2

Related Questions