You need to sign in to do that
Don't have an account?
Richard Corfield
Set.retainAll performance query
We're trying to optimise code - new CPU governor and all that - and have found something strange with set.retainAll().
Given sets A and B, we'd expect A.retainAll(B) to be pretty fast. According to Wikipedia's article on HashSet performence we'd expect O(n). When the set becomes very large, we see rapidly diminishing performance.
The strange thing is if we implement it ourselves.
/* pseudocode */
For (itemA : setA){
if(!setB.contains(itemA)){
setA.remove(itemA);
}
}
Given that this involves two hash lookups to do a remove, rather than being able to take advantage of something like Java's Iterator.remove() method, we'd expect it to be slower.
The only risk is that we're modifyin a set while iterating over it. Will this break things?
We could also perform the operation by copying into a new Set, but this takes a little more heap (only a little, as it's copy by reference of course).
/* pseudocode */
Set outputSet = new Set();
For (itemA : setA){
if(setB.contains(itemA)){
outputSet.add(itemA);
}
}
Given sets A and B, we'd expect A.retainAll(B) to be pretty fast. According to Wikipedia's article on HashSet performence we'd expect O(n). When the set becomes very large, we see rapidly diminishing performance.
The strange thing is if we implement it ourselves.
/* pseudocode */
For (itemA : setA){
if(!setB.contains(itemA)){
setA.remove(itemA);
}
}
Given that this involves two hash lookups to do a remove, rather than being able to take advantage of something like Java's Iterator.remove() method, we'd expect it to be slower.
The only risk is that we're modifyin a set while iterating over it. Will this break things?
We could also perform the operation by copying into a new Set, but this takes a little more heap (only a little, as it's copy by reference of course).
/* pseudocode */
Set outputSet = new Set();
For (itemA : setA){
if(setB.contains(itemA)){
outputSet.add(itemA);
}
}
Were you able to Optimize this code?
Its quite complex, can you explain a bit more.
Are you hitting any governon limit.
Regards,
Ashish