6

Java 8 introduced Lambdas, which allow us to efficiently remove all elements from a List. The following removes all instances of 2 from myList.

List<Integer> myList;
...
myList.removeIf(x -> x==2);

If I wanted to remove N number of elements (in this case, three), I would use a for loop.

for (int i = 0; i < 3; i++) {
    myList.remove(Integer.valueOf(2));
}

Is there a way to remove a specified number of elements from a List using Lambdas? If so, is it more efficient than the for loop code?

Naman
  • 27,789
  • 26
  • 218
  • 353
dinorider
  • 191
  • 10
  • 1
    What about - `IntStream.range(0,3).forEach(a-> myList.remove(2))`;? – Most Noble Rabbit May 26 '21 at 14:46
  • @MostNeededRabbit your solution will generate an error if the number of 2 is less than 3 in the list `java.lang.IndexOutOfBoundsException: Index: 2, Size: 2` – Youcef LAIDANI May 26 '21 at 14:57
  • @YCF_L It could be the requested behavior though. – Most Noble Rabbit May 26 '21 at 14:58
  • @MostNeededRabbit no it is not, if your try the simple loop than you will not get this error – Youcef LAIDANI May 26 '21 at 15:01
  • `for (int i = 0; i < 3; i++) { integers.remove(2);}` This will also throw an exception right? – Most Noble Rabbit May 26 '21 at 15:03
  • 1
    @MostNeededRabbit, check [this](https://stackoverflow.com/questions/21795376/java-how-to-remove-an-integer-item-in-an-arraylist), hence OP need to use `Integer.valueOf(2)`. – samabcde May 26 '21 at 15:08
  • @samabcde great catch, I didn't expect this – Most Noble Rabbit May 26 '21 at 15:11
  • Also `x==2` should be `x.equals(2)` according to [this](https://stackoverflow.com/questions/1514910/how-to-properly-compare-two-integers-in-java) – samabcde May 26 '21 at 15:16
  • 2
    @samabcde But they are not two Integers. It is one Integer and one int literal. In which case the Integer will be automatically unboxed, making the comparison int == int, which behaves intuitively. The only potential problem is that if `x` is null, the auto-unbox will NPE, but your code also suffers from that problem. – Michael May 26 '21 at 15:18
  • Java 8 specifically, or would you also consider Java 9+? – VLAZ May 26 '21 at 15:22
  • 1
    @Michael, you are correct, I miss that. And I think it is more safe to use `equals` as OP may pass an Integer instead of int to replace the hardcoded 2 later, == will have problem. – samabcde May 26 '21 at 15:27

4 Answers4

9

When you repeatedly call remove(Object) you get O(n²) time complexity from both, starting the search repeatedly from the beginning (applies to all List types) and from repeatedly copying the elements after the removed one, when the list is an ArrayList or similar.

The time complexity of the search can be avoided by using a dedicated search and remove loop, e.g. using an Iterator and its remove method. But the copying time complexity remains, unless you use removeIf and the list class overrides it with an appropriate implementation (as ArrayList does).

One way of utilizing this advantage for removing n matches would be

int n = 3;
int last = IntStream.range(0, myList.size())
    .filter(ix -> myList.get(ix) == 2)
    .limit(n)
    .reduce((a,b) -> b)
    .orElse(-1);
myList.subList(0, last + 1).removeIf(x -> x == 2);

It’s more complicated and for small lists, it will be more expensive. However, for really large lists where the time complexity matters, it will benefit from the O(n) time complexity.

Note that when the predicate is a simple match operation, you can also use, e.g. removeAll(Collections.singleton(2)) instead of removeIf(x -> x == 2).

Holger
  • 285,553
  • 42
  • 434
  • 765
  • when I rephrased the question, I was thinking over the same line, to get the index of that Nth occurrence and update the sublist, but then I tried looking for `NthindexOf` in JDK... (thought `for` is far better)....and now I can see the implementation of the API I was looking for :) – Naman May 26 '21 at 17:01
  • 1
    How large is really large? Right now the largest list I would use is <400. The function will also be run fairly frequently. – dinorider May 26 '21 at 17:01
  • 1
    As long as `n` stays 3 and the match predicate remains an int comparison, 400 isn’t large. But the actual question must be *can you guaranty that the assumed upper limit will always apply*? That’s one of the most common problems, badly scaling algorithms hitting unexpectedly large problem sizes in production environments. You can look at it from the other side: if this O(n) solution runs sufficiently fast with your current list sizes, you can be confident that it will work well with all sizes. – Holger May 26 '21 at 17:12
  • What happens if `n` was 400? The list I'm working with is fixed size and I'm fully in control of the limit. I'm not at all opposed to using this method, but I just want to make sure that it's not too much for what I need. If the list absolutely would not climb past a few hundred in size, would you suggest to just run a `replace` loop? – dinorider May 26 '21 at 17:30
  • 3
    What do you mean with “`replace` loop”? The question was about removal. Calling `remove` up to 400 times on a list of 400 elements can get in the order of magnitude of performing 160000 operations. That’s what O(n²) means. With such numbers, you’d have crossed the line where using the O(n) version of this answer becomes beneficial when the method is invoked very often. But, as already said, do either, test and measure or just use the code of this answer knowing that it scales well and you don’t have to worry about the actual numbers. – Holger May 26 '21 at 17:58
  • @dinorider you can look at the other answer Holger made [here](https://stackoverflow.com/questions/60048072/removeif-implementation-detail) about some implementation details. The question I asked then, was because we saw a very good decrease in using `removeIf`. Our data sets had > 500 elements and the performance was big. this is a very good answer. – Eugene May 26 '21 at 18:14
  • @Holger Sorry, my brain's a bit fuzzy and I typed the wrong word. Thank you for explaining the number of iterations - it put things in perspective. I think your solution is both elegant, scales well and does what I need. I suspect it works well with smaller ones (20 or so loops), so I'll use it for the sake of simplicity. In this case, I think I'll use your removeAll code vs removeIf. Thank you! – dinorider May 26 '21 at 18:27
0

You can do something close to a for-loop:

IntStream.range(0,3).forEach(a-> integers.remove(Integer.valueOf(2)));

It should be equivalent to a for-loop in terms of performance.

Most Noble Rabbit
  • 2,728
  • 2
  • 6
  • 12
0

Using lambdas:

Runnable runnable = () -> {
    for (int i = 0; i < 3; i++) {
        myList.remove(Integer.valueOf(2));
    }
};
runnable.run();

Just kidding.

ZhekaKozlov
  • 36,558
  • 20
  • 126
  • 155
0

A bit dirty, but requires just one pass:

public static <T extends Comparable<? super T>> List<T> removeFirstN(List<T> list, T t, int N) {
    int[] a = {0};
    return list.stream().filter(p -> !p.equals(t) || ++a[0] > N).collect(toList());
}
Kees Pastinaak
  • 11
  • 2