Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #35195 > unrolled thread

DeDup an ArrayList

Back to article view | Back to comp.lang.java.programmer

Contents

  DeDup an ArrayList Roedy Green <inquiry@mindprod.com> - 2016-08-04 18:35 -0700
    Re: DeDup an ArrayList Andreas Leitgeb <avl@logic.at> - 2016-08-05 02:05 +0000
      Re: DeDup an ArrayList Arne Vajhøj <arne@vajhoej.dk> - 2016-08-04 22:41 -0400
      Re: DeDup an ArrayList Lew <lewbloch@gmail.com> - 2016-08-05 15:38 -0700
        Re: DeDup an ArrayList Andreas Leitgeb <avl@logic.at> - 2016-08-06 12:10 +0000
    Re: DeDup an ArrayList Roedy Green <inquiry@mindprod.com> - 2016-08-04 19:06 -0700
      Re: DeDup an ArrayList Eric Douglas <e.d.programmer@gmail.com> - 2016-08-05 05:16 -0700
        Re: DeDup an ArrayList Andreas Leitgeb <avl@logic.at> - 2016-08-05 15:30 +0000
          Re: DeDup an ArrayList Eric Douglas <e.d.programmer@gmail.com> - 2016-08-05 10:10 -0700
            Re: DeDup an ArrayList Eric Sosman <esosman@comcast-dot-net.invalid> - 2016-08-05 13:51 -0400
              Re: DeDup an ArrayList Eric Douglas <e.d.programmer@gmail.com> - 2016-08-05 12:16 -0700
                Re: DeDup an ArrayList Eric Sosman <esosman@comcast-dot-net.invalid> - 2016-08-05 15:38 -0400
              Re: DeDup an ArrayList Marcel Mueller <news.5.maazl@spamgourmet.org> - 2016-08-06 00:47 +0200
      Re: DeDup an ArrayList Arne Vajhøj <arne@vajhoej.dk> - 2016-08-05 09:02 -0400
    Re: DeDup an ArrayList Jan Burse <janburse@fastmail.fm> - 2016-08-05 12:52 +0200
      Re: DeDup an ArrayList Jan Burse <janburse@fastmail.fm> - 2016-08-05 12:53 +0200
        Re: DeDup an ArrayList Jan Burse <janburse@fastmail.fm> - 2016-08-05 13:10 +0200
          Re: DeDup an ArrayList Jan Burse <janburse@fastmail.fm> - 2016-08-13 12:26 +0200
    Re: DeDup an ArrayList Daniel Pitts <usenet@coloraura.com> - 2016-08-05 08:37 -0700
      Re: DeDup an ArrayList Knute Johnson <nospam@rabbitbrush.frazmtn.com> - 2016-08-05 08:58 -0700
        Re: DeDup an ArrayList Knute Johnson <nospam@rabbitbrush.frazmtn.com> - 2016-08-05 09:47 -0700
          Re: DeDup an ArrayList Knute Johnson <nospam@rabbitbrush.frazmtn.com> - 2016-08-05 19:56 -0700
          Re: DeDup an ArrayList Daniel Pitts <usenet@coloraura.com> - 2016-08-06 09:18 -0700
    Re: DeDup an ArrayList Marcel Mueller <news.5.maazl@spamgourmet.org> - 2016-08-06 01:04 +0200
    Re: DeDup an ArrayList Roedy Green <inquiry@mindprod.com> - 2016-08-05 16:31 -0700

Page 2 of 2 — ← Prev page 1 [2]

#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

[toc] | [prev] | [next] | [standalone]

#35220

This is pretty fast but while leaving the strings unchanged it sorts the 
list.  I think one of Roedy's conditions was that the order be unchanged.

import java.util.*;

public class test3 {
     static List<String> list = new ArrayList<>();

     public static void main(String[] args) {
         list.add("hello");
         list.add("world");
         list.add("wOrld");
         list.add("One");
         list.add("two");
         list.add("oNe");
         list.add("three");
         list.add("TWO");
         list.add("onE");
         list.add("ONE");

         Set<String> set = new TreeSet<>(new IgnoreComparator());
         set.addAll(list);

         for (String str : set)
             System.out.println(str);

     }

     static class IgnoreComparator implements Comparator<String> {
         public int compare(String s1, String s2) {
             return s1.compareToIgnoreCase(s2);
         }
         public boolean equals(String s1, String s2) {
             return s1.equalsIgnoreCase(s2);
         }
     }
}

-- 

Knute Johnson

[toc] | [prev] | [next] | [standalone]

#35223

On 8/5/16 9:47 AM, Knute Johnson wrote:
> 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.
Check again, both of my solutions actually keep the case and order the same.

> 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.

My streams one isn't the most optimal, someone else posted one that 
didn't use groupingBy, but reduce instead, and was more elegant IMO. 
Mine could run into issues if there were a large number of duplicates 
(it would create a list of every duplicate.)

In the second "Dedup", I could also use a TreeSet with 
String.CASE_INSENSITIVE_ORDER, which would be safer than my solutions 
for some languages, and faster than yours for most cases.

[toc] | [prev] | [next] | [standalone]

#35218

On 05.08.16 03.35, Roedy Green wrote:
> This looks like trivial task, but every time I work on it, it keeps
> ballooning in complexity.

A correct solution is O(n) in memory and CPU.

> 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.

No. Java Iterator provides an erase() method exactly for such purposes.

But it is even more simple. See my other post.


Marcel

[toc] | [prev] | [next] | [standalone]

#35219

On Thu, 04 Aug 2016 18:35:21 -0700, Roedy Green <inquiry@mindprod.com>
wrote:

>This looks like trivial task, but every time I work on it, it keeps
>ballooning in complexity

I have posted and benchmarked 5 algorithms at
http://mindprod.com/jgloss/deduplication.html

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.java.programmer

csiph-web