[
https://issues.apache.org/jira/browse/LANG-1176?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15293600#comment-15293600
]
ASF GitHub Bot commented on LANG-1176:
--------------------------------------
Github user PascalSchumacher commented on the pull request:
https://github.com/apache/commons-lang/pull/144#issuecomment-220645637
pull request updated to include the other `removeElements()` methods as
suggested by Sebb
> Improve ArrayUtils removeElements time complexity to O(n)
> ---------------------------------------------------------
>
> Key: LANG-1176
> URL: https://issues.apache.org/jira/browse/LANG-1176
> Project: Commons Lang
> Issue Type: Improvement
> Components: lang.*
> Affects Versions: 3.4
> Reporter: jefferyyuan
> Priority: Minor
> Fix For: 3.5
>
> Original Estimate: 24h
> Remaining Estimate: 24h
>
> The current ArrayUtils removeElements implementation is not efficient when
> try to get all indexes that needed to be removed.
> It's O(m*n): n is the length of origin array, m is the unique count of
> toBeRemoved.
> {code:java}
> final BitSet toRemove = new BitSet();
> for (final Map.Entry<Byte, MutableInt> e : occurrences.entrySet()) {
> final Byte v = e.getKey();
> int found = 0;
> for (int i = 0, ct = e.getValue().intValue(); i < ct; i++) {
> found = indexOf(array, v.byteValue(), found);
> if (found < 0) {
> break;
> }
> toRemove.set(found++);
> }
> }
> {code}
> We can just scan the origin array once to get all indexes that needed to be
> removed.
> {code:java}
> final BitSet toRemove = new BitSet();
> // the only change here, time complexity changed to O(n)
> for (int i = 0; i < array.length; i++) {
> final int key = array[i];
> final MutableInt count = occurrences.get(key);
> if (count != null) {
> count.decrement();
> if (count.intValue() == 0) {
> occurrences.remove(key);
> }
> toRemove.set(i);
> }
> }
> {code}
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
