Get max and maxIndex of sum of two lists of floats in java fast

Question

I am trying to calculate the max sum pair of two lists with a faster way than what i've managed below, using "lightweight streams":

 List<Float> pairsSum = new ArrayList<>();
 // Get the list with all the sums
 Stream.range(0, list1.size())
          .forEach(i -> pairsSum.add(list1.get(i) + list2.get(i)));
 // Get the index of the max pair
 maxIndex = pairsSum.indexOf(Stream.of(pairsSum).max(Double::compare).orElse(0f));

Answer 1

The short solution is to use an IntStream and the reduce() method:

int maxIndex = IntStream.range(0, list1.size())
        .reduce((i1, i2) -> list1.get(i1) + list2.get(i1) < list1.get(i2) + list2.get(i2) ? i2 : i1)
        .orElse(-1);

If you want the index, both values and the sum, you can use a custom Result class:

public static class Result {
    private int index;
    private float left;
    private float right;
    private float sum;
    // constructor and getters
}

Use it like this:

Result max = IntStream.range(0, list1.size())
        .mapToObj(i -> new Result(i, list1.get(i), list2.get(i), list1.get(i) + list2.get(i)))
        .max(Comparator.comparing(Result::getSum))
        .orElse(null);

The time complexity in both cases is O(n).

Answer 2

You can create the list of sums in one line by mapping the streams (I did add line breaks for legibility):

    //made some example lists
    List<Float> list1 = Arrays.asList(new Float[]{1F, 2F, 3F});
    List<Float> list2 = Arrays.asList(new Float[]{2F, 3F, 4F});

    // Get the list with all the sums
    List<Float> sums = list1.stream()
            .map( f -> (list2.get(list1.lastIndexOf(f)) + f ) )
            .collect(Collectors.toList());

    // Get the index of the max pair
    int maxIndex = sums.indexOf(sums.stream().max(Float::compareTo).get());

Just stream the first list, and .map it (map is like a foreach but returns a result for each list item).

What's happening in the map: for each item it finds the highest index for the current value f in list 1. That'll be the index of the current item in the first list. Then it gets the value for this index in the second list. list2.get(list1.lastIndexOf(f)). So now you add the current value f to that. This way, for the full length of list 1 you are outputting the sum of the two values that share the same index.

Then you just need to .collect them back into a list.

Finally to find the max index, I would take the exact same approach you did.

Answer 3

List<Float> pairsSum = new ArrayList<>(repLeftForces.size());
// Get the list with all the sums
int maxIndex = -1;
float max = 0F;
for (int i =0; i < repLeftForces.size(); ++i) {
    float sum = list1.get(i) + list2.get(i);
    //pairsSum.add(sub);
    if (maxIndex == -1 || sum > max) {
        maxIndex = i;
        max = sum;
    }
 }

The pairsSum list is not needed actually. But when used, the actual size is known in advance.

As one wants to do a reduce too for a maximum, and receive additionally the maxIndex, best would be a classical loop instead of using a Stream.