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

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

Re: DeDup an ArrayList

Show all headers | View raw

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

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