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 15:38:36 -0400
Organization: A noiseless patient Spider
Lines: 33
Message-ID: <no2pvt$h4d$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> <no2jmu$qca$1@dont-email.me> <c20e6f88-cca3-47d4-8f28-3283241277ac@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 19:38:37 -0000 (UTC)
Injection-Info: mx02.eternal-september.org; posting-host="2d081e2f7155c28005d4472f67c2f43d"; logging-data="17549"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19s1iCm8IiqkzZ/Oioj6bE7"
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.2.0
In-Reply-To: <c20e6f88-cca3-47d4-8f28-3283241277ac@googlegroups.com>
Cancel-Lock: sha1:CcXUyDBl5NhNOEri/rfH8tj79Rs=
Xref: csiph.com comp.lang.java.programmer:35214

On 8/5/2016 3:16 PM, Eric Douglas wrote:
> On Friday, August 5, 2016 at 1:51:36 PM UTC-4, Eric Sosman wrote:
>>      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);
>> 	}
>
> I like it.  Just manually shifting the unique values then bumping the extra containers off the end should be most efficient.  I think the only thing that could be faster is if you don't need an ArrayList, just return the subList().  I checked the code and subList is just a subset view of the ArrayList.

     It can even be streamlined a little by changing the first loop:

	for (String candidate : a) {...}

I shied away from this at first because there's an Iterator behind the
scenes, and I feared it might throw ConcurrentModificationException
because of all those set() calls.  But it turns out that CME is thrown
only for what the JavaDoc terms "structural" modifications, and
"[...] merely setting the value of an element is not a structural
modification."

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