TIntArrayList::retainAll() and removeAll() are implemented using an O(n^2) algorithm
Issue #78
new
Hi guys. I’m a bit of a noob here. But I noticed a performance problem with TIntArrayList::retainAll() and removeAll(). It’s implemented using an O(n^2) algorithm. I had a list of 2,400,000 int’s, and ‘collection’ was just 10, and as you can imagine, the method never completed.
The current code is:
public boolean retainAll(TIntCollection collection) { if (this == collection) { return false; } else { boolean modified = false; TIntIterator iter = this.iterator(); while(iter.hasNext()) { if (!collection.contains(iter.next())) { iter.remove(); modified = true; } } return modified; } }
My suggestion is:
public boolean retainAll(TIntCollection collection) { if (this == collection) return false; TIntArrayList survivors = new TIntArrayList(); boolean modified = false; TIntIterator iter = this.iterator(); while (iter.hasNext()) { int val = iter.next(); if (collection.contains(val)) survivors.add(val); else modified = true; } this._data = survivors._data; this._pos = survivors._pos; return modified; }
And then same problem with removeAll(). Can someone address this issue? Maybe my fix is good, maybe not, but we can’t use these methods as things currently stand.