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

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

Re: DeDup an ArrayList

Show key headers only | View raw

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

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