Java 8 stream-performance improvement

I am implementing a method that takes an integer value k (which represents the amount of "vacancies") and two lists (p and q) of Integer and performs some operations.

Using stream, I check which elements of the list p have value >= than the values of the list q. If it exists, I need to store the position (index + 1) of each item in another list. However this third list can only have a number of elements k passed by parameter.

The implemented code is below, however I need to improve the performance of it (I believe that the existing 2 forEach are worsening the performance).

public static List<Integer> kthPerson(int k, List<Integer> p, List<Integer> q) {

        List<Integer> busList = new ArrayList<>();

        q.stream().forEach(time -> {
            List<Integer> lista = new ArrayList<>();

            IntStream.range(0, p.size()).filter(i -> (p.get(i) >= time && lista.size() < k)).forEach(i -> lista.add(i+1) );
            int size = lista.size();
            if(size < k){
               busList.add(0);
            }else{
                if (lista != null && !lista.isEmpty()) {
                    busList.add(lista.get(size - 1));
                }
            }
        });
        return busList;

    }

}
Author: hkotsubo, 2020-04-01

2 answers

Given your description, I think your code is not right:

I check which elements of the list p have value >= than the values of the list q. If it exists, I need to store the position (index + 1) of each item in another list. However this third list can only have a number of elements k

I tested your code with the lists below:

List<Integer> p = Arrays.asList(10, 20, 30, 40, 50, 60, 70, 80, 90);
List<Integer> q = Arrays.asList(10, 20, 30, 40, 50);
System.out.println(kthPerson(3, p, q));

And the result was:

[3, 4, 5, 6, 7]

Only that position 3 (which corresponds to index 2) of p is the number 30, which is not greater than the values of q (since q has the values 40 and 50, which are greater than 30). Also, the result has 5 elements, which is greater than k.

Anyway, it was not very clear what it is to do. I understood it in two ways:

  1. check the elements of p that are greater than all elements of q
  2. check the elements of p that are greater than the element of q which is in the same position

We will see solutions for each case.


Option 1

If the idea is to check the elements of p that are larger than all elements of q, then you don't have to scroll through q several times. Just find the largest element of q and check which elements of p are greater than or equal to it. Then just take the first k elements and return the list:

public static List<Integer> kthPersonOpcao1Stream(int k, List<Integer> p, List<Integer> q) {
    // encontrar o maior elemento de q
    int maxQ = Collections.max(q);
    return IntStream
        // iterar pelos índices de p
        .range(0, p.size())
        // pegar os elementos maiores ou iguais a maxQ
        .filter(i -> p.get(i) >= maxQ)
        // pegar somente os k primeiros
        .limit(k)
        // somar 1 ao índice
        .map(i -> i + 1)
        // converter os valores int para Integer
        .boxed()
        // coletar os valores em uma List
        .collect(Collectors.toList());
}

But if the concern is performance, maybe you shouldn't use streams, since they are slower than a traditional loop . Of course for a few small lists it won't make that much difference, but anyway, the solution without stream would be pretty simple:

public static List<Integer> kthPersonOpcao1Loop(int k, List<Integer> p, List<Integer> q) {
    int maxQ = Collections.max(q);
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < p.size() && result.size() < k; i++) {
        if (p.get(i) >= maxQ) {
            result.add(i + 1);
        }
    }
    return result;
}

Notice the condition of the for (i < p.size() && result.size() < k), which checks if I have already compared all elements of p and if the result list has k elements. Thus it already covers also the cases in which they are found less than k elements (since k is the maximum size the result list can have, but nothing guarantees that it will always find k elements).


Option 2

If the idea is to compare each element of p with the element of q that is in the same position, we first need to know which of the lists is smaller (for example, if p has 10 elements and q has 4, I don't need to check the 10 elements of p, just check the first 4).

O code is very similar to Option 1, the difference is that instead of comparing the elements of p with the largest element of q, I compare only with those that are in the same position:

// com stream
public static List<Integer> kthPersonOpcao2Stream(int k, List<Integer> p, List<Integer> q) {
    // só preciso iterar até o tamanho da menor das listas
    int size = Math.min(p.size(), q.size());
    return IntStream
        // iterar pelos índices até "size"
        .range(0, size)
        // pegar os elementos de p maiores ou iguais ao elemento de q na mesma posição
        .filter(i -> p.get(i) >= q.get(i))
        // pegar somente os k primeiros
        .limit(k)
        // somar 1 ao índice
        .map(i -> i + 1)
        // converter os valores int para Integer
        .boxed()
        // coletar os valores em uma List
        .collect(Collectors.toList());
}

// sem stream
public static List<Integer> kthPersonOpcao2Loop(int k, List<Integer> p, List<Integer> q) {
    int size = Math.min(p.size(), q.size());
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < size && result.size() < k; i++) {
        if (p.get(i) >= q.get(i)) {
            result.add(i + 1);
        }
    }
    return result;
}
 3
Author: hkotsubo, 2020-04-29 13:15:31

I found a good solution to this problem in this question how to find all K-th elements for each expiration time, the best time obtained was using Arrays instead of List/Streams. If the problem provides the data in List is just make a parse for Array and in the end performs another parse back to List, only in this way I managed to pass in all test cases.

public static int[] kth(int k, int[] t, int[] e) {
        int[] kth = new int[e.length];

        if (k > t.length)
            return kth;

        Arrays.sort(e);
        int c = 0;

        for (int i = 0; i < e.length; i++) {            
            for (int j = 0; j < t.length; j++) {
                if (t[j] >= e[i])
                    c++;

                if (c >= k) {
                    kth[i] = j + 1;
                    break;
                }
            }

            if (c < k)
                break;

            c = 0;
        }

        return kth;
}
 1
Author: Marcos Antônio, 2020-05-26 12:37:45