Remove an array of ids contained in another array

Question

If I have an array of Track objects:

Track[] tracks;

Where each track has many fields among others a String trackId:

public class Track{

    private String trackId;


    private String artistId;
}

then I have

String trackIdsToRemove[];

I would like to remove the ids in trackIdsToRemove[] that are in the objects inside the list tracks.

Is there any fancy way to do this other than iterate? Maybe with Guava? Or RxJava?

Given what you provided as infos, no. If the main array is sorted by trackId it could be possible to binary search for them. Also, you can't really "remove" from an array, at best you can set the content of a cell to null. — Diego Martinoia, Jan 26 '16 at 15:47

score 0 · Answer 1 · answered Jan 26 '16 at 15:50

No matter what trick / library you will use, the backend will be the same everytime, you need to locate the element to remove, and then proceed to actually removing it.

But there are some little optimization you could do, first off take the best data structure. If you're going to add/remove tracks often maybe you shoud use a list instead of an array.
And then you could also insert your track in an ordered way so you can do a binary search when you need to locate the track to remove. The binary search takes O(log(n)) to find a track in the worst case whereas a normal search takes O(n)

usefull link : http://bigocheatsheet.com/#data-structures

score 0 · Answer 2 · edited May 23 '17 at 12:07

0

You can use an ArrayList:

ArrayList array = new ArrayList();
//add elements to array -> array.add(object1);
ArrayList arrayToRemove = new ArrayList();
//add elements to array to remove -> array.add(object1);
for(Object obj : arrayToRemove){
   array.remove(obj);
}

To do this, if you are using your own object you need to override the next object functions equals and hashCode, here is an example on this thread:

ArrayList's custom Contains method

edited May 23 '17 at 12:07

Community

1
1

answered Jan 26 '16 at 15:55

kunpapa

367
1
9

Worth mentioning that this approach creates a copy of the data: if OP is worried about performance it's likely because the collection is big, so duplicating the data may not be feasible. – Diego Martinoia Jan 26 '16 at 15:57
1

@DiegoMartinoia I assumed that he could change the objects. For sure if OP have a primitive array, the best thing it to make his own iteration and create a new copy with the results. – kunpapa Jan 26 '16 at 16:05

Alex Derkach · Accepted Answer · 2016-01-26T16:18:37.937

0

If you are using java 8 and Guava:

Set<String> toRemove = Sets.newHashSet(trackIdsToRemove);
tracks = Arrays.stream(tracks)
    .filter(t -> !toRemove.contains(t.trackId))
    .toArray(Track[]::new);

edited Jan 26 '16 at 16:18

answered Jan 26 '16 at 15:58

Alex Derkach

741
5
8

score 0 · Answer 4 · answered Jan 26 '16 at 16:07

I'm unsure what you mean by "removing" from an array: you simply can't do that, at best you can set to null the cell content or somehow marked it as invalid/free.

If your array is sorted by id, you can binary search the ids that you want to "remove" to have a better performance: supposing that N is the size of the collection and M of the removal collection, then normal iteration is O(n*m), while by binary searching you get down to O(log(n)*m)

In general, even if you had a library, it would do exactly this with those data structures, just behind the scene.

As others have pointed out, if you need to support deletion it's best to use different structures: given you have ID's it suggests that your items are unique, so a Set could be ideal, otherwise a List should do, or a Map Obj -> Int to implement a multi-set.

Supposing you can change your code to use more ideal structures, you could do something like (Java8):

Set<Track> tracks;
Set<String> idsToRemove;
//Note: this has O(n*m) performance, though you could try using .parallelstream() instead of .stream()
Set<Track> remainingOnes = tracks.stream().filter(x -> !idsToRemove.contains(x.id)).collect(Collectors.toSet());

score -1 · Answer 5 · answered Jan 26 '16 at 15:46

-1

You cannot remove from array. You can remove from a list. Change your array to list and do that way:

public void remove(String trackIdsToRemove[], List<Track> tracks) {
    for(String str: trackIdsToRemove) {
        tracks.remove(tracks.indexOf(str));
    }
}

answered Jan 26 '16 at 15:46

Paulo

1,458
2
12
26

If you really have to go by list, then you may have the trackIdsToRemove as list and do removeAll. But note that trackToRemove is a collection of ID's, not of Track objects, so you need to adapt your code accordingly: as it's now it wont compile bc types are not compatible – Diego Martinoia Jan 26 '16 at 15:48
The parameter of `removeAll()` is a Collection of the list type. And that's not the case. If I pass an array of String to removeAll() of a list of Track, it won't remove all the Tracks. Please, search about your answer before down voting. – Paulo Jan 26 '16 at 15:50
That's exactly what I said: if you had a collection of Tracks, you could use remove or removeAll, but you have a collection of Strings (id's) so you can't use neither of them: your indexOf method would fail here bc you are passing it a string – Diego Martinoia Jan 26 '16 at 15:51

Remove an array of ids contained in another array

5 Answers5