Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Knute Johnson <nospam@rabbitbrush.frazmtn.com>
Newsgroups: comp.lang.java.programmer
Subject: Re: DeDup an ArrayList
Date: Fri, 5 Aug 2016 09:47:50 -0700
Organization: A noiseless patient Spider
Lines: 107
Message-ID: <no2fvm$cb3$1@dont-email.me>
References: <21r7qb1srdvnieuufjquie2qrfujso6l7p@4ax.com> <no2bs0$u7g$1@dont-email.me> <no2d2n$284$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 5 Aug 2016 16:47:50 -0000 (UTC)
Injection-Info: mx02.eternal-september.org; posting-host="fc10d1b501433caa198830294d826923"; logging-data="12643"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18BWsiIMcKcdDREmQ1Iqe7c"
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.2.0
In-Reply-To: <no2d2n$284$1@dont-email.me>
Cancel-Lock: sha1:WeDOlX4w9hl1j3DX2LqLFvj3IL4=
Xref: csiph.com comp.lang.java.programmer:35209

On 8/5/2016 08:58, Knute Johnson wrote:
> On 8/5/2016 08:37, Daniel Pitts wrote:
>> On 8/4/16 6:35 PM, Roedy Green wrote:
>>> This looks like trivial task, but every time I work on it, it keeps
>>> ballooning in complexity.
>>>
>>> I wish to deDup an ArrayList.  Any two strings equalIgnoreCase are
>>> considered dups. One should be removed.  The order of the items should
>>> be otherwise be undisturbed.
>>>
>>> Part of the trouble is removing an element from an ArrayList makes you
>>> lose track of where you are.
>>>
>>
>> Stream version:
>>
>> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>>
>>
>> import java.util.*;
>> import java.util.stream.Collectors;
>>
>> public class Dedup {
>>
>>     public static void main(String[] args) {
>>         final List<String> list = new ArrayList<>(Arrays.asList(
>>             "First",
>>             "Second",
>>             "first",
>>             "Third",
>>             "third",
>>             "second",
>>             "Last"));
>>
>>
>>         final List<String> result =
>>             list.stream()
>>                 .collect(
>>                     Collectors.groupingBy(
>>                         String::toLowerCase,
>>                         LinkedHashMap<String, List<String>>::new,
>>                         Collectors.toList()
>>                     )
>>                 )
>>                 .entrySet()
>>                 .stream()
>>                 .map(Map.Entry::getValue)
>>                 .map(l -> l.get(0))
>>                 .collect(Collectors.toList());
>>
>>         result.forEach(System.out::println);
>>     }
>> }
>>
>>
>> ************************************************************************************************
>>
>>
>>
>> In-place non-stream version:
>>
>> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>>
>>
>>
>>
>> import java.util.*;
>>
>> public class Dedup {
>>
>>     public static void main(String[] args) {
>>         final List<String> list = new ArrayList<>(Arrays.asList(
>>             "First",
>>             "Second",
>>             "first",
>>             "Third",
>>             "third",
>>             "second",
>>             "Last"));
>>
>>         final Set<String> exists = new HashSet<>();
>>         for (final Iterator<String> i = list.iterator(); i.hasNext();) {
>>             if (!exists.add(i.next().toLowerCase())) {
>>                 i.remove();
>>             }
>>         }
>>
>>         list.forEach(System.out::println);
>>     }
>> }
>>
>> ************************************************************************************************

My solutions were staggeringly slow and yours were extremely fast.  Your 
solution with the streams took 0.078 seconds to scan 100,000 strings 
with .08% dups, the HashSet solution took only 0.015 seconds for the 
same scan, about 5 times as fast.  The only wrinkle I see is that the 
original element is permanently changed to lower case.

I did see some discussions prior to Java 8 that the developers were 
originally going to create a distinct method for streams that would take 
a Comparable for an argument.


-- 

Knute Johnson