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

Groups > comp.lang.java.programmer > #35223

Re: DeDup an ArrayList

Show all headers | View raw

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.

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web