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.