commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (LANG-1176) Improve ArrayUtils removeElements time complexity to O(n)
Date Sun, 22 May 2016 15:26:12 GMT

    [ https://issues.apache.org/jira/browse/LANG-1176?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15295599#comment-15295599
] 

ASF GitHub Bot commented on LANG-1176:
--------------------------------------

Github user asfgit closed the pull request at:

    https://github.com/apache/commons-lang/pull/144


> 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)

Mime
View raw message