Adding 2 list element by element

Question

I am having 2 Lists and want to add them element by element. Like that:

Is there an easier way and probably much more well performing way than using a for loop to iterate over the first list and add it to the result list?

I appreciate your answer!

Answer 1

Depends on what kind of list and what kind of for loop.

Iterating over the elements (rather than indices) would almost certainly be plenty fast enough.

On the other hand, iterating over indices and repeatedly getting the element by index could work rather poorly for certain types of lists (e.g. a linked list).

Answer 2

My understanding is that you have List1 and List2 and that you want to find the best performing way to find result[index] = List1[index] + list2[index]

My main suggestion is that before you start optimising for performance is to measure whether you need to optimise at all. You can iterate through the lists as you said, something like:

for(int i = 0; i < listSize; i++)
{
    result[i] = List1[i] + List2[i];
}

In most cases this is fine. See NPE's answer for a description of where this might be expensive, i.e. a linked list. Also see this answer and note that each step of the for loop is doing a get - on an array it is done in 1 step, but in a linked list it is done in as many steps at it takes to iterate to the element in the list.

Assuming a standard array, this is O(n) and (depending on array size) will be done so quickly that it will hardly result in a blip on your performance profiling.

As a twist, since the operations are completely independent, that is result[0] = List1[0] + List2[0] is independent of result[1] = List1[1] + List2[1], etc, you can run these operations in parallel. E.g. you could run the first half of the calculations (<= List.Size / 2) on one thread and the other half (> List.Size / 2) on another thread and expect the elapsed time to roughly halve (assuming at least 2 free CPUs). Now, the best number of threads to use depends on the size of your data, the number of CPUs, other operations happening at the same time and is normally best decided by testing and modeling under different conditions. All this adds complexity to your program, so my main recommendation is to start simple, then measure and then decide whether you need to optimise.

Answer 3

Looping is inevitable except you have a matrix API (e.g. OpenGL). You could implement a List<Integer> which is backed by the original Lists:

public class CalcList implements List<Integer> {

    private List<Integer> l1, l2;

    @Override
    public int get(int index) {
        return l1.get(index) + l2.get(index);
    }

}

This avoids copy operations and moves the calculations at the end of your stack:

CalcList<Integer> results1 = new CalcList(list, list1);
CalcList<Integer> results2 = new CalcList(results1, list3);
// no calculation or memory allocated until now.

for (int result : results2) {
    // here happens the calculation, still without unnecessary memory

}

This could give an advantage if the compiler is able to translate it into:

for (int i = 0; i < list1.size; i++) {
    int result = list1[i] + list2[i] + list3[i] + …;

}

But I doubt that. You have to run a benchmark for your specific use case to find out if this implementation has an advantage.

Answer 4

Java doesn't come with a map style function, so the the way of doing this kind of operation is using a for loop. Even if you use some other construct, the looping will be done anyway. An alternative is using the GPU for computations but this is not a default Java feature. Also using arrays should be faster than operating with linked lists.