This week's book giveaway is in the OCP forum.
We're giving away four copies of OCP Java SE 8 Programmer II Exam Study Guide and have Kathy Sierra, Bert Bates, & Elizabeth Robson on-line!
See this thread for details.
Win a copy of OCP Java SE 8 Programmer II Exam Study Guide this week in the OCP forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Fastest way to remove multiple elements from an ArrayList  RSS feed

 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have an ArrayList of tens of thousands of elements, and want to remove the items at a given set of sorted indices like {1,5,29,318,499,583}. It seems like this operation could be performed in linear time and space by first finding a cumulative sum of the shifts needed to move everything to their right positions and then shifting every item. On the other hand, removing and shifting one by one would seem to require many more shifts. Is there a way to do this in Java's ArrayList?
 
Ranch Hand
Posts: 75
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You don't describe the input to the ArrayList. You also don't describe what you want to remove from the ArrayList. A full description of the problem you are trying to solve would helpful.
 
author & internet detective
Sheriff
Posts: 38050
606
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carl,
Welcome to CodeRanch!

I can think of a way to do it in linear time (but not space)
1) Create a new ArrayList of the original size minus the number of elements to remove - this will ensure the new ArrayList doesn't grow as you add elements
2) Go through the original ArrayList adding the element at each index (unless it needs to be removed) to the new one

This doesn't use linear space though. The ArrayList class doesn't have a method that does what you are looking for. I recommend checking the performance of the code using normal ArrayList methods first to see if this is an actual performance problem.
 
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Carl Dewitt wrote:I have an ArrayList of tens of thousands of elements, and want to remove the items at a given set of sorted indices like {1,5,29,318,499,583}. It seems like this operation could be performed in linear time and space by first finding a cumulative sum of the shifts needed to move everything to their right positions and then shifting every item. On the other hand, removing and shifting one by one would seem to require many more shifts. Is there a way to do this in Java's ArrayList?


I suspect you might be overthinking this. My O(n + r) solution would be:
1. Go through the list of indices and "null out" the element at that index.
2. Copy all non-null elements from your original list to the new one.

Or, if the original List CAN contain nulls, then an alternative is to:
1. Sort the indices to be removed.
2. Copy the elements from your original list to the new one, missing out the indices in your "to be removed" array.
Slightly more complex than above, but basically the same idea.

The latter will be O(n + (r log r)) which, assuming r (the number of elements to remove) is relatively small, won't affect O(n) very much. In the first case, assuming r < n (ie, no duplicate indices), the overall time must be <= O(2n) == O(n). The copy can be done "in place" in both cases, so it would only require space relative to r if a sort is involved in the latter case.

If you want to get fancy, you could use a HashSet of "indexes to be removed", but you'll likely have a space overhead. I leave that to your ingenuity.

Winston
 
Marshal
Posts: 58421
178
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Put everything into a linked set and copy the set back to a new List?
You can probably get a Stream from the original List and use the distinct method on the Stream.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!