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 1 of 2  [1] 2  Next page →

#35195 — DeDup an ArrayList

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.

[toc] | [next] | [standalone]

#35196

Roedy Green <inquiry@mindprod.com> 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.

Copy to a LinkedHashMap (using the toUpperCase()'d string as key, and
the original String as value), and finally copy back to a new ArrayList...

The LinkedHashMap will take care of maintaining the ordering, except
of course, where dups are left out.

Not sure if hashing on the uppercase version of a String is strictly
equivalent to pairwise equalIgnoreCase, though. Maybe not, maybe close
enough, maybe exactly same...  The performance advantage (from n-squared
to roughly n) might be worth a little slack in some corner cases.

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

#35198

On 8/4/2016 10:05 PM, Andreas Leitgeb wrote:
> Roedy Green <inquiry@mindprod.com> 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.
>
> Copy to a LinkedHashMap (using the toUpperCase()'d string as key, and
> the original String as value), and finally copy back to a new ArrayList...
>
> The LinkedHashMap will take care of maintaining the ordering, except
> of course, where dups are left out.

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.stream.Collectors;

public class ListDeDup {
	public static void main(String[] args) {
		List<String> lst = new ArrayList<>();
		lst.add("Aa");
		lst.add("Bb");
		lst.add("Cc");
		lst.add("cC");
		lst.add("bB");
		lst.add("aA");
		System.out.println(lst);
		List<String> res = lst.stream().collect(Collectors.toMap(o -> 
o.toLowerCase(), o -> o, (o1,o2) -> o1, 
LinkedHashMap::new)).values().stream().collect(Collectors.toList());
		System.out.println(res);
	}
}

> Not sure if hashing on the uppercase version of a String is strictly
> equivalent to pairwise equalIgnoreCase, though. Maybe not, maybe close
> enough, maybe exactly same...  The performance advantage (from n-squared
> to roughly n) might be worth a little slack in some corner cases.

There is always the "Turkish problem", but ...

Arne

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

#35216

Andreas Leitgeb wrote:
> 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.
> 
> Copy to a LinkedHashMap (using the toUpperCase()'d string as key, and
> the original String as value), and finally copy back to a new ArrayList...

Two different lower-case strings can upper-case to the same string, and be considered duplicates even though they aren't, in certain languages.

For example, "ß" and "ss" in German (traditionally) both upper-case to "SS".

> The LinkedHashMap will take care of maintaining the ordering, except
> of course, where dups are left out.
> 
> Not sure if hashing on the uppercase version of a String is strictly
> equivalent to pairwise equalIgnoreCase, though. Maybe not, maybe close
> enough, maybe exactly same...  The performance advantage (from n-squared
> to roughly n) might be worth a little slack in some corner cases.

In Greek, '"ς" and "σ", two versions of the Greek sigma, both capitalise to "Σ". '
http://inform7.com/learn/man/WI_20_4.html

-- 
Lew

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

#35222

Lew <lewbloch@gmail.com> wrote:
>> Copy to a LinkedHashMap (using the toUpperCase()'d string as key, and
>> the original String as value), and finally copy back to a new ArrayList...
> Two different lower-case strings can upper-case to the same string, and
> be considered duplicates even though they aren't, in certain languages.
> For example, "ß" and "ss" in German (traditionally) both upper-case to "SS".

You're right, but then again, equalsIgnoreCase just isn't transitive, so
the problem is already flawed from the outset.

If "ß", "ss", "SS", (ditto for "ς", "σ" and "Σ") were all in the original
List, then it is a matter of pure chance (well, depending on original
ordering), whether "ß" and "ss" both remain, or just one or even none of
them remains.

> In Greek, '"ς" and "σ", two versions of the Greek sigma, both capitalise to "Σ". '
Ksereis ta Ellhnika, h ksereis mono ta grammata;

> http://inform7.com/learn/man/WI_20_4.html
Nice summary of some of the caveats.  Not sure what Glulx and Z-machine 
were referring to, though, and not interested enough to research. ;-)

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

#35197

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

Here is my best code so far:

    /**
     * Remove duplicates if match equalIgnoreCase
     * a ArrayList to deDup
     */
    private static void deDup( final ArrayList<String> a )
        {
        // outer loop works down
        int n = a.size();
        for ( int i = n - 1; i >= 1; i-- )
            // inner partial loop works up
            {
            inner:
            for ( int j = 0; j < i; j++ )
                {
                if ( a.get( j ).equalsIgnoreCase( a.get( i ) ) )
                    {
                    a.remove( i );
                    break inner;
                    }
                }
            }
        // deduped result is left in a
        }

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

#35203

On Thursday, August 4, 2016 at 10:06:30 PM UTC-4, Roedy Green wrote:
>     private static void deDup( final ArrayList<String> a )
>         {
>         // outer loop works down
>         int n = a.size();
>         for ( int i = n - 1; i >= 1; i-- )
>             // inner partial loop works up
>             {
>             inner:
>             for ( int j = 0; j < i; j++ )
>                 {
>                 if ( a.get( j ).equalsIgnoreCase( a.get( i ) ) )
>                     {
>                     a.remove( i );
>                     break inner;
>                     }
>                 }
>             }
>         // deduped result is left in a
>         }

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);
               }
          }

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

#35206

Eric Douglas <e.d.programmer@gmail.com> wrote:
> On Thursday, August 4, 2016 at 10:06:30 PM UTC-4, Roedy Green 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.

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

#35210

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.

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

#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

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

#35213

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.

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

That does seem odd.  That method doesn't check if the range is the end of the list to skip the arraycopy(), and only seems to be called from the clear() which always removes the range from zero to size.

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

#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

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

#35217

On 05.08.16 19.51, Eric Sosman wrote:
>      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);
>      }

This is the first reasonable solution I have seen here so far.


But two comments:

First of all you should initialize the HashSet with the size of the 
ArrayList. This avoids expensive rehash operations and finally turns the 
algorithm into O(n) - subject to excessive hash collisions, of course.

Secondly, what's wrong with removeAll()? OK, it's ugly. It takes the 
Collection interface for just calling exactly one method of it, i.e. 
contains() as predicate. So all you need to do is extend HashSet, 
override contains and call removeAll:

private class ContainsWorker extends HashSet<String>
{ public ContainsWorker(int size)
   { super(size);
   }
   public boolean contains(object o)
   { return !add(o.toString().toUpperCase());
   }
}

a.removeAll(new ContainsWorker(a.size()));

This is highly efficient with several types of lists.


Marcel

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

#35204

On 8/4/2016 11:05 PM, Stefan Ram wrote:
> Roedy Green <inquiry@mindprod.com> writes:
>> * Remove duplicates if match equalIgnoreCase
>> * a ArrayList to deDup
>
> public final class Main
> {
>   public static java.util.List< java.lang.String >
>   dedup( final java.util.List< java.lang.String >input )
>   { return
>     input.stream().map( java.lang.String::toLowerCase ).distinct().
>     collect( java.util.stream.Collectors.toList() ); }
>
>   public static void main( final java.lang.String[] args )
>   { final java.util.List< java.lang.String >list
>     = java.util.Arrays.asList( "A", "a", "b" );
>     java.lang.System.out.println( dedup( list )); }}
>
> [a, b]

But:

Arrays.asList( "A", "A", "b" );

also gives:

[a, b]

which may or may not be OK.

Arne

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

#35200

I am using a HashSet to DeDup, and I call
the method distinct() in analogy to the DISTINCT
keyword in SQL.

(If you go with Excel you could also call it
unique() in analogy to the corresponding
function).

So basically you need:
- 1) A hash set, either linked or not
- 2) Hash set needs a add + if not create,
      or you do a contains and then add
- 3) Hash set needs some enumeration
      into an array
- 4) Elements need hashCode() and equals()
- 5) No compareTo() for elements needed

The algorithm is pretty simple:
- add all elements to the hash set
- enumerate the elements back into a possibly shorter array

If you don't use hash set, for example a tree
you might suddently run into the problem that
your elements also need a compareTo().

If you use the java.util HashSet you incure a
great overhead, since internally HashSet is modelled
as a HashMap with a default value.

So I am using a custom light weight HashSet, without
mod count index bound checks as in java.util etc..

Bye

Roedy Green schrieb:
> 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.
>

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

#35201

Jan Burse schrieb:
> The algorithm is pretty simple:
> - add all elements to the hash set
> - enumerate the elements back into a possibly shorter array

If you use a linked hash set, you get
the input order of the array back.

If you don't care what the order is you
can use a simple hash set.

If you want a new order, you might need
something that uses compareTo().

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

#35202

Last but not least since I have a custom HashSet
available, it is also easy to use a custom
hash scrambling murmur() built into the HashSet ,

this gives better results for Float, Double,
Integer, Long etc..

See my post here some weeks ago about murmur().

Jan Burse schrieb:
> Jan Burse schrieb:
>> The algorithm is pretty simple:
>> - add all elements to the hash set
>> - enumerate the elements back into a possibly shorter array
>
> If you use a linked hash set, you get
> the input order of the array back.
>
> If you don't care what the order is you
> can use a simple hash set.
>
> If you want a new order, you might need
> something that uses compareTo().
>
>

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

#35298

The hash set that uses murmur is now open source,
you find it here:

    Package Data
 
http://www.jekejeke.ch/idatab/doclet/blog/en/docs/05_run/01_kernel/data/package.jsp
    See class AbstractSet
    See class SetEntry
    See class SetHash
    See class SetHashEntry
    See class HashScrambler

I just see, that since this library was organically
growing, it supports null keys.

But with the current API, this doesn't make sense anymore,
I should remove this and put some guards.

Bye


Jan Burse schrieb:
> Last but not least since I have a custom HashSet
> available, it is also easy to use a custom
> hash scrambling murmur() built into the HashSet ,
>
> this gives better results for Float, Double,
> Integer, Long etc..
>
> See my post here some weeks ago about murmur().

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

#35207

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);
     }
}

************************************************************************************************

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

#35208

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);
>     }
> }
>
> ************************************************************************************************
>

I like your solutions Daniel.  If I have some time I'm going to create a 
huge file with dups and try a speed test.  My inelegant solutions below:

import java.util.*;
import java.util.stream.*;

public class test {
     public static void main(String... args) {
         List<String> list1 = Arrays.asList(
          "hello","world","wOrld","onE","two","one","three","ONE","TWO");
         List<String> list2 = new ArrayList<>();

         for (String str1 : list1) {
             boolean flag = true;
             for (String str2 : list2)
                 if (str1.equalsIgnoreCase(str2)) {
                     flag = false;
                     break;
                 }
             if (flag)
                 list2.add(str1);
         }

         for (String str : list2)
             System.out.println(str);
     }
}




import java.util.*;
import java.util.stream.*;

public class test1 {
     public static void main(String... args) {
         List<String> list1 = Arrays.asList(
          "hello","world","wOrld","onE","two","one","three","ONE","TWO");
         List<String> list2 = new ArrayList<>();

         List<String> list3 = list1.stream().
          filter(s -> check(s,list2)).
          collect(Collectors.toList());

         list3.forEach(System.out::println);

     }

     static boolean check(String str,List<String> list) {
         boolean flag = true;
         for (String str1 : list) {
             if (str.equalsIgnoreCase(str1)) {
                 flag = false;
                 break;
             }
         }
         if (flag)
             list.add(str);
         return flag;
     }
}




-- 

Knute Johnson

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web