Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.java.programmer > #35212
| From | Eric Sosman <esosman@comcast-dot-net.invalid> |
|---|---|
| Newsgroups | comp.lang.java.programmer |
| Subject | Re: DeDup an ArrayList |
| Date | 2016-08-05 13:51 -0400 |
| Organization | A noiseless patient Spider |
| Message-ID | <no2jmu$qca$1@dont-email.me> (permalink) |
| References | <21r7qb1srdvnieuufjquie2qrfujso6l7p@4ax.com> <g4t7qb1r1ctt9ea84ji3rf7f66chkl1s9i@4ax.com> <4bc2ec3d-7ee4-4c3a-a769-8268ddfc1cbb@googlegroups.com> <slrnnq9c90.456.avl@login.logic.tuwien.ac.at> <9b29e37c-5a25-493b-8ac1-52db1366b93e@googlegroups.com> |
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
Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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