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;
}
}
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 listq
. 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:
- check the elements of
p
that are greater than all elements ofq
- check the elements of
p
that are greater than the element ofq
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;
}
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;
}