Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Eric Sosman <esosman@comcast-dot-net.invalid>
Newsgroups: comp.lang.java.programmer
Subject: Re: DeDup an ArrayList
Date: Fri, 5 Aug 2016 13:51:25 -0400
Organization: A noiseless patient Spider
Lines: 40
Message-ID: <no2jmu$qca$1@dont-email.me>
References: <21r7qb1srdvnieuufjquie2qrfujso6l7p@4ax.com> <g4t7qb1r1ctt9ea84ji3rf7f66chkl1s9i@4ax.com> <4bc2ec3d-7ee4-4c3a-a769-8268ddfc1cbb@googlegroups.com> <slrnnq9c90.456.avl@login.logic.tuwien.ac.at> <9b29e37c-5a25-493b-8ac1-52db1366b93e@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 5 Aug 2016 17:51:26 -0000 (UTC)
Injection-Info: mx02.eternal-september.org; posting-host="2d081e2f7155c28005d4472f67c2f43d"; logging-data="27018"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18T5bX15nGhX8u++PzgoUvw"
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.2.0
In-Reply-To: <9b29e37c-5a25-493b-8ac1-52db1366b93e@googlegroups.com>
Cancel-Lock: sha1:AZ39+zvLgVeamDEMqkuirO4mqWc=
Xref: csiph.com comp.lang.java.programmer:35212

On 8/5/2016 1:10 PM, Eric Douglas wrote:
> On Friday, August 5, 2016 at 11:30:50 AM UTC-4, Andreas Leitgeb wrote:
>>> Why 2 loops?  If you use another object to compare just loop through once.
>>>           final HashSet<String> b = new HashSet();
>>>           for (int n = 0; n < a.size(); n++) {
>>>                final String v = a.get(n).toUpperCase();
>>>                if (b.contains(v)) {
>>>                     a.remove(n);
>>>                     n--;
>>>                } else {
>>>                     b.add(v);
>>>                }
>>>           }
>>
>> This approach still has quadratic performance characteristics, because
>> removing an element from an arraylist involves shifting back all the
>> following elements.
>
> I was thinking it would take less memory to modify the array.  If it takes much more time to remove an element due to shifting the rest of the array, then similar solution skip the remove part and do the add on a new array, returning the new array or replacing the old array with it after the loop.

     You can avoid quadratic performance, avoid all the "sliding
down," and still use the same ArrayList:

	HashSet<String> b = new HashSet<>();
	int keepers = 0;
	for (int n = 0; n < a.size(); ++n) {
	    String candidate = a.get(n);
	    if (b.add(candidate.toUpperCase())) {
	       a.set(keepers++, candidate);
	    }
	}
	for (int n = a.size(); --n >= keepers; ) {
	    a.remove(n);
	}

(Any conjectures about why removeRange() is protected?)

-- 
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM