Java 8 stream - performance improvement

Question

I am implemented a method that receives an integer value k (representing the amount of "vacancies") and two lists (p and q) of Integer and perform some operations.

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

The implemented code is below, but I need to improve its performance (I believe the 2 forEach existing are worsening 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;

    }

}

Answer 1

Given your description, I don’t think your code is right:

check which elements of the list p have value >= the list values q. If available, I need to store the position (index + 1) of each item in another list. However, this third list may only have a quantity of elements <= the value 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 the heading 3 (corresponding to index 2) of p is number 30, which is no higher than the values of q (since q has values 40 and 50, which are greater than 30). In addition, the result has 5 elements, which is greater than k.

Anyway, it wasn’t very clear what to do. I understood two ways:

1. verify the elements of p which are larger than all the elements of q
2. verify the elements of p which are larger than the element of q who is in the same position

We will see solutions for each case.

---

Option 1

If the idea is to check the elements of p which are larger than all the elements of q, so you don’t have to go through q several times. Just find the biggest element of q and check which elements of p are larger or equal to it. Then just take the first k elements and return to 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 loop traditional. Of course for a few small lists it won’t make that much difference, but anyway, the solution without stream it would be quite 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 for (i < p.size() && result.size() < k), which checks whether I have compared all the elements of p and whether the list of results has k elements. Thus it already covers also the cases in which are found less than k elements (as k is the maximum size that the results list can have, but nothing guarantees that you will always find k elements).

---

Option 2

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

The code is very similar to option 1, the difference is that instead of comparing the elements of p with the greatest element of q, I compare only with those 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;
}

Answer 2

I found a good solution to this problem in this nonsense 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 you the data in List just do a parse for Array and in the end performs another parse back to List, only this way I was able 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;
}