TIntArrayList::retainAll() and removeAll() are implemented using an O(n^2) algorithm

Issue #78 new
Tim Cooper created an issue

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.

Comments (0)

  1. Log in to comment