For example in the code below:
public int commonTwo(String[] a, String[] b)
{
Set common = new HashSet<String>(Arrays.asList(a));
common.retainAll(new HashSet<String>(Arrays.asList(b)));
return common.size();
}
The retainAll() method of ArrayList is used to remove all the array list's elements that are not contained in the specified collection or retains all matching elements in the current ArrayList instance that match all elements from the Collection list passed as a parameter to the method.
For HashSet, LinkedHashSet, and EnumSet, the add(), remove() and contains() operations cost constant O(1) time thanks to the internal HashMap implementation. Likewise, the TreeSet has O(log(n)) time complexity for the operations listed in the previous group.
Note: Time Complexity: ArrayList is one of the List implementations built a top an array. Hence, get(index) is always a constant time O(1) operation. Example: Java.
the elements in a set are sorted, but the add, remove, and contains methods has time complexity of o(log (n)).
util. HashSet. size() method is used to get the size of the HashSet or the number of elements present in the HashSet.
retainAll() method is present in the HashSet class inside the java. util package. It is used to retain all the elements in a HashSet that are specified in the input collection.
Lets take a peruse at the code. The method retainAll
is inherited from AbstractCollection
and (at least in OpenJDK) looks like this:
public boolean retainAll(Collection<?> c) {
boolean modified = false;
Iterator<E> it = iterator();
while (it.hasNext()) {
if (!c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
There is one big this to note here, we loop over this.iterator()
and call c.contains
. So the time complexity is n
calls to c.contains
where n = this.size()
and at most n
calls to it.remove()
.
This important thing is that the contains
method is called on the other Collection
and so the complexity is dependant upon the complexity of the other Collection
contains
.
So, whilst:
Set<String> common = new HashSet<>(Arrays.asList(a));
common.retainAll(new HashSet<>(Arrays.asList(b)));
Would be O(a.length)
, as HashSet.contains
and HashSet.remove
are both O(1)
(amortized).
If you were to call
common.retainAll(Arrays.asList(b));
Then due to the O(n)
contains
on Arrays.ArrayList
this would become O(a.length * b.length)
- i.e. by spending O(n)
copying the array to a HashSet
you actually make the call to retainAll
much faster.
As far as space complexity goes, no additional space (beyond the Iterator
) is required by retainAll
, but your invocation is actually quite expensive space-wise as you allocate two new HashSet
implementations which are actually fully fledged HashMap
.
Two further things can be noted:
HashSet
from the elements in a
- a cheaper collection that also has O(1)
remove from the middle such as an LinkedList
can be used. (cheaper in memory and also build time - a hash table is not built)b.size()
.The implementation can be found in the java.util.AbstractCollection
class. The way it is implemented looks like this:
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
Iterator<E> it = iterator();
while (it.hasNext()) {
if (!c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
So it will iterate everything in your common
set and check if the collection that was passed as a parameter contains this element.
In your case both are HashSet
s, thus it will be O(n), as contains should be O(1) amortized and iterating over your common
set is O(n).
One improvement you can make, is simply not copy a
into a new HashSet
, because it will be iterated anyway you can keep a list.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With