commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Joachim Rudolph (JIRA)" <j...@apache.org>
Subject [jira] Commented: (COLLECTIONS-302) CollectionUtils.subtract() should not use ArrayList to improve speed
Date Fri, 24 Oct 2008 11:49:45 GMT

    [ https://issues.apache.org/jira/browse/COLLECTIONS-302?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12642451#action_12642451
] 

Joachim Rudolph commented on COLLECTIONS-302:
---------------------------------------------

I did some tests myself, I just underestimated the speed of System.arraycopy()

In my problem the resulting collection would be almost empty. 
For this case the following code models the algorithm :

{code:title=Bar.java|borderStyle=solid}
    private static final int REPS = 50;
    @SuppressWarnings("unchecked")
    public static void test(int n) throws InterruptedException {
        Collection a = new ArrayList(n);
        for(int i=0; i<n; i++) {
            a.add("bob"+i);
        }
        
        for (int r = 0; r < REPS; ++r) {
            ArrayList c = new ArrayList(a);
            long t1 = System.currentTimeMillis();
            while( c.size() > 0 ){
                c.remove(0);
            }
            long t2 = System.currentTimeMillis();
            System.err.println("T" + n + ": " + (t2-t1)+ " ms");
        }
    }
{code} 

In this testcase for n = 200000, System.arraycopy() is called 200000 times with an average
of 100000 references to be moved.
The code runs on my machine within 12.3 seconds/iteration which is about 6.5 GBytes/sec, much
better than I expected.
So I will use Arraylists on many other problems where I was worried about the O(N^2) performance
before.

I should have done my profiling before... sorry.




> CollectionUtils.subtract() should not use ArrayList to improve speed
> --------------------------------------------------------------------
>
>                 Key: COLLECTIONS-302
>                 URL: https://issues.apache.org/jira/browse/COLLECTIONS-302
>             Project: Commons Collections
>          Issue Type: Improvement
>          Components: Collection
>            Reporter: Joachim Rudolph
>            Priority: Minor
>   Original Estimate: 2h
>  Remaining Estimate: 2h
>
> The implementation of version 3.2.1 is
> public static Collection subtract(final Collection a, final Collection b) {
>         ArrayList list = new ArrayList( a );
>         for (Iterator it = b.iterator(); it.hasNext();) {
>             list.remove(it.next());
>         }
>         return list;
>     }
> when a and b are large and similar the subtract implementation will call ArrayList.remove()
frequently which copies a potentially large part of the list using system.arraycopy.
> Suggestion : use LinkedList ( at least for large lists )

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


Mime
View raw message