[
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.
