• Post Reply Bookmark Topic Watch Topic
  • New Topic

Fastest way to remove multiple elements from an ArrayList  RSS feed

 
Carl Dewitt
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?
 
Emil Jennings
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.
 
Jeanne Boyarsky
author & internet detective
Marshal
Posts: 37462
537
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.
 
Winston Gutkowski
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
 
Campbell Ritchie
Marshal
Posts: 56522
172
  • 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!