Tobias, the O(n) algorithms have been corrected. Here are the modified versions that null the slack space after removal:
public boolean removeAll(Collection<?> c) { int x=0, i=0; for (i=0; i<size; i++) if (!c.contains(elementData[i])) elementData[x++] = elementData[i]; if (x != i) { Arrays.fill(elementData, x, i, null); size = x; return true; } else { return false; } }
and
public boolean removeAll(Collection<?> c) { int oldHi=0, newHi=0, top=0; for (int i=0; i<size; ++i) { if (c.contains(elementData[i])) { oldHi = newHi; newHi = i;
// at the end of this loop newHi will be the non-inclusive // upper limit of the range to delete. // while (++newHi < size && c.contains(elementData[newHi]));
final int length = i - oldHi; System.arraycopy(elementData, oldHi, elementData, top, length); i = newHi; top += length; } } if (newHi > 0) { final int k = size - newHi; System.arraycopy(elementData, newHi, elementData, top, k); final int n = top + k; Arrays.fill(elementData, n, size, null); size = n; return true; } else { return false; } }
> Technically all of these issues result from breaking the > contract of contains(): > > "More formally, returns true if and only if this set > contains an element e such that (o==null ? e==null : > o.equals(e))."
There are plenty of legitimate reasons for have differing notions of equality. It would be better if there was a method on Collection to obtain the 'concept' of equality in use by that Collection. This would return either a Comparator or an interface containing methods to test equality and provide a hashCode.
> > Technically all of these issues result from breaking > the > > contract of contains(): > > > > "More formally, returns true if and only if this set > > contains an element e such that (o==null ? e==null : > > o.equals(e))." > > There are plenty of legitimate reasons for have differing > notions of equality.
Definitely. Didn't mean to suggest otherwise. It's more that the Collections interface is itself flawed. Hardly any of the implementations follow the rules so we can't make many assumptions. The contract isn't good enough because we need these other implementations.
> It would be better if there was a > method on Collection to obtain the 'concept' of equality > in use by that Collection. This would return either a > Comparator or an interface containing methods to test > equality and provide a hashCode.
There's actually an RFE for Equalator (you can search for that word and find it in the bug db. I've voted for it an argued for it many times. Depending only on the Objects themselves to determine equality in the Collection is fundamentally flawed. An arbitrator is needed especially when inheritance comes into play.
Amin, Good that Sun has accepted the issue which is O(ns) performance. But that doesn't take away James' argument that your implementations too remain O(ns). Please see the contains() in ArrayList which loops over the entire list.
Sun has to address which your 2 solutions also don't.
> Amin, > Good that Sun has accepted the issue which is O(ns) > performance. But that doesn't take away James' argument > that your implementations too remain O(ns). Please see the > contains() in ArrayList which loops over the entire list.
Go back and read this thread in more detail. The worst case performance of the linear removeAll implementation is O(n*K) where K is the complexity of the contains method on the passed collection, as a function of s (the number of items in the collection). Therefore, if the developer is being smart and passing a hashset, he'll achieve O(ns), whereas if he's not being smart and passes in an array list, he'll have O(ns) performance.
However, the worst case performance of Sun's removeAll implementation is O(n*n*K). For HashSet and ArrayList, you get O(n*n) and O(n*n*s) worst case performance.
As Mark Thorton pointed out to James, it's not possible to get a hard limit of O(n) performance by reallocated the elements to remove into a HashSet because you cannot guarantee correctness.
> Sun has to address which your 2 solutions also don't.
See my comments above: you clearly haven't understood the difference between Sun's approach and the O(n) approach.
> > Amin, > > Good that Sun has accepted the issue which is O(ns) > > performance. But that doesn't take away James' argument > > that your implementations too remain O(ns). Please see > the > > contains() in ArrayList which loops over the entire > list. > > Go back and read this thread in more detail. The worst > case performance of the linear removeAll implementation is > O(n*K) where K is the complexity of the contains method on > the passed collection, as a function of s (the number of > items in the collection). Therefore, if the developer is > being smart and passing a hashset, he'll achieve O(ns),
err... make that O(n) [typing too fast]
> whereas if he's not being smart and passes in an array > list, he'll have O(ns) performance. > > However, the worst case performance of Sun's removeAll > implementation is O(n*n*K). For HashSet and ArrayList, you > get O(n*n) and O(n*n*s) worst case performance. > > As Mark Thorton pointed out to James, it's not possible to > get a hard limit of O(n) performance by reallocated the > elements to remove into a HashSet because you cannot > guarantee correctness. > > > Sun has to address which your 2 solutions also don't. > > See my comments above: you clearly haven't understood the > difference between Sun's approach and the O(n) approach. > > > -Surender
Let me start with passing a list instead of a hashset.
Sun's impl: if(contains()) remove()
which is O(2n)=O(n) rather than O(n*n) as your analysis says. So your time estimates would for sure show the time differnce but not to the magnitude of n.
When you talk about deveopler's smartness of passing a Hashset the remove() in hashset would be O(1) [as would be contain()] if their was no chaining involved. So even Sun's impl passes that again. Sun impl's inner loop suffers from 2n [contain() and remove()] and not n*n.
> Let me start with passing a list instead of a hashset. > > Sun's impl: > if(contains()) remove() > > which is O(2n)=O(n) rather than O(n*n) as your analysis > says.
No, the performance of the statement above is O(n+s). I never said the performance of the statement above is O(n*n), I was talking about removeAll as a whole.
> So your time estimates would for sure show the time > differnce but not to the magnitude of n. > > When you talk about deveopler's smartness of passing a > Hashset the remove() in hashset would be O(1) [as would > be contain()] if their was no chaining involved. So even > Sun's impl passes that again. > Sun impl's inner loop suffers from 2n [contain() and > remove()] and not n*n.
> However, the worst case performance of Sun's removeAll > implementation is O(n*n*K). For HashSet and ArrayList, you > get O(n*n) and O(n*n*s) worst case performance. >
OK if you agree that if(contains()) remove is O(n+s) and Sun's impl is iterating 'n' times how can it have the worst case O(n*n*K) or O(n*n*s) or even O(n^3) for an arrayList[s=n makes it the worst case]
All I'm saying is Sun's impl has remove() which is making the time twice instead of your interpretation of n times.
> As Mark Thorton pointed out to James, it's not possible to > get a hard limit of O(n) performance by reallocated the > elements to remove into a HashSet because you cannot > guarantee correctness.
Yes but you could do it if the class of the passed in collection was ArrayList or LinkedList and marker interfaces could make it general.
Removing to HashSet suffers from one drawback. Lists can have duplicate elements while HashSet cannot. So if input collection is a list with duplicate elements then you run into problems unless you tweak insertion/lookup into the set.
One thing I would like to point out here is, although the current implemention is potentially slow, it is potentially safer. Because it internally uses an iterator, it can throw ConcurrentModificationException if the Collection is modified while you are iterating over it.
To quote the JavaDocs
"Iterators that do this are known as fail-fast iterators, as they fail quickly and cleanly, rather that risking arbitrary, non-deterministic behavior at an undetermined time in the future."
I think the new implementation should take this into account.
> One thing I would like to point out here is, although the > current implemention is potentially slow, it is > potentially safer. Because it internally uses an iterator, > it can throw ConcurrentModificationException if the > Collection is modified while you are iterating over it.
That's a good point. In fact one thing I should point out is that a correct implementation of the removeAll method needs to increment the modCount variable to make sure that the fail-fast iterators work properly. This was an implementation detail I left out of the code samples I posted.
That said, ConcurrentModificationExceptions are probably overkill for individual method calls since, in this case, concurrent modification can only occur in a multi-threaded environment where you have not synchronized the collection properly (i.e. in single threaded code it is impossible). On the other hand, with iterators, it is quite possible for single threaded code to concurrently modify the collection while one or more iterators are "live".
> > To quote the JavaDocs > > "Iterators that do this are known as fail-fast iterators, > as they fail quickly and cleanly, rather that risking > arbitrary, non-deterministic behavior at an undetermined > time in the future." > > I think the new implementation should take this into > account.
Again, when the arraylist is accessed by a single thread, operations that complete within a single method do not need to take this into account. In a multi-threaded environment, you would retrieve a synchronized version of the collection and use that instead.
> Removing to HashSet suffers from one drawback. Lists can > have duplicate elements while HashSet cannot. So if input > collection is a list with duplicate elements then you run > into problems unless you tweak insertion/lookup into the > set.
This is not a problem. If A is equal to B and A is equal to C then C is equal to B per the transitivity and symmetry requirements of equals. In other words, I don't need duplicates to determine if something is in the list.
Flat View: This topic has 41 replies
on 3 pages
[
«
|
123
|
»
]
Previous Topic
