[jira] [Commented] (LANG-1176) Improve ArrayUtils removeElements time complexity to O(n)

["ASF GitHub Bot (JIRA)" <ji...@apache.org>]

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

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

GitHub user PascalSchumacher opened a pull request:

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

    LANG-1176: Improve ArrayUtils removeElements time complexity to O(n)

    patch submitted by Jeffery Yuan

You can merge this pull request into a Git repository by running:

    $ git pull https://github.com/PascalSchumacher/commons-lang LANG-1176

Alternatively you can review and apply these changes as the patch at:

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

To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:

    This closes #144
    
----
commit 0386f0e1db7894fceb70653b35ed3072a4d146ed
Author: pascalschumacher <pa...@gmx.net>
Date:   2016-05-19T19:52:51Z

    LANG-1176: Improve ArrayUtils removeElements time complexity to O(n)
    
    patch submitted by Jeffery Yuan

----


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