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));

Maybe the pairsSum list is not needed and the calculation of sum and max could be done on the fly, but i couldn't figure it out, so i'm generally asking for an optimization on the above code. — angelos_lex, Apr 03 '19 at 14:23
Possible duplicate of https://stackoverflow.com/questions/30730861/how-to-get-the-index-and-max-value-of-an-array-in-one-shot ? — Dominic Fischer, Apr 03 '19 at 14:54
@DominicFischer That's about one array, not the sum of two arrays — angelos_lex, Apr 03 '19 at 14:58

score 3 · Answer 1 · answered Apr 03 '19 at 14:05

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.

score 2 · Accepted Answer · answered Apr 03 '19 at 15:44

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).

score 1 · Answer 3 · answered Apr 03 '19 at 14:44

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.

That solution is not faster than the solution provided by OP, because `List.indexOf()` has a time complexity of _O(n). So your solution has a time complexity of _O(n²)_. — Samuel Philipp, Apr 03 '19 at 15:07

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

3 Answers3