[
https://issues.apache.org/jira/browse/KAFKA-15139?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
hudeqi updated KAFKA-15139:
---------------------------
Description:
This is the hint of `removeAll` method in `Set`:
_This implementation determines which is the smaller of this set and the
specified collection, by invoking the size method on each. If this set has
fewer elements, then the implementation iterates over this set, checking each
element returned by the iterator in turn to see if it is contained in the
specified collection. If it is so contained, it is removed from this set with
the iterator's remove method. If the specified collection has fewer elements,
then the implementation iterates over the specified collection, removing from
this set each element returned by the iterator, using this set's remove method._
That's said, assume that M is the number of elements in the set and N is the
number of elements in the List, if the type of the specified collection is
`List`, and M<=N, then the time complexity of `removeAll` is O(MN) (because the
time complexity of searching in List is O(N)), on the contrary, if N<M, it will
search in `Set`, the time complexity is O(N).
In
> Optimize the performance of `Set.removeAll(List)` in
> `MirrorCheckpointConnector`
> --------------------------------------------------------------------------------
>
> Key: KAFKA-15139
> URL: https://issues.apache.org/jira/browse/KAFKA-15139
> Project: Kafka
> Issue Type: Improvement
> Components: mirrormaker
> Affects Versions: 3.5.0
> Reporter: hudeqi
> Assignee: hudeqi
> Priority: Major
>
> This is the hint of `removeAll` method in `Set`:
> _This implementation determines which is the smaller of this set and the
> specified collection, by invoking the size method on each. If this set has
> fewer elements, then the implementation iterates over this set, checking each
> element returned by the iterator in turn to see if it is contained in the
> specified collection. If it is so contained, it is removed from this set with
> the iterator's remove method. If the specified collection has fewer elements,
> then the implementation iterates over the specified collection, removing from
> this set each element returned by the iterator, using this set's remove
> method._
> That's said, assume that M is the number of elements in the set and N is the
> number of elements in the List, if the type of the specified collection is
> `List`, and M<=N, then the time complexity of `removeAll` is O(MN) (because
> the time complexity of searching in List is O(N)), on the contrary, if N<M,
> it will search in `Set`, the time complexity is O(N).
> In
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
