How to construct a new array given an old array and a set of index locations which need to skipped?

Question

Basically what I want is to I skip elements on those index values which are there in the set otherwise I should just push the old array elements into the new array.

So if my set contains [2, 4, 9, 10] I should skip the values at index 2,4,9,10 in the old Array and put the values at othe other index locations in my new Array.

I am writing code like this

  int[] newArr = new int[oldArray.length - set.size()];


   for(int i = 0, j = 0; j < newArr.length && i < oldArray.length; j++,i++){
      if(set.contains(i) )
         i++;
       else
         newArray[j] = oldArray[i];
      }

I am creating and filling my set like this

       Set<Integer> commonSet = new HashSet<>();

       for(int i = 0; i < array1; i++ ){
         for(int j= 0; j < array2; j++) {
            if(arrayOne[i] == arrayTwo[j]){
              commonSet.add(i);// Here I am saving the indices.
           }
         }
       }

Not Sure if this is the best way. Is there any other way which would be more efficient? Or I must have to resort to Collection classes like ArrayLists.

Answer 1

Using Collection classes instead of arrays would make your code much simpler.

Doing array subtraction using common libraries like apache CollectionUtils looks like this:

    Collection<Integer> diff = CollectionUtils.subtract(Arrays.asList(array1), Arrays.asList(array2));

Unless you're going to be working very large sets of data, it won't have a noticeable impact on speed.

Also, creating a set of different indexes the way you do above is going to scale very poorly for larger data sets. Just calculating the times for doing a difference using CollectionUtils.subtract() vs your set creation code shows the scaling problems (arrays filled with random Integers):

array1.length = 1000
array2.length = 1000
diff.size() = 530
elapsed ms for calculating diff = 39
set creation ms = 7

array1.length = 10000
array2.length = 10000
diff.size() = 5182
elapsed ms for calculating diff = 47
set creation ms = 519

array1.length = 50000
array2.length = 50000
diff.size() = 26140
elapsed ms for calculating diff = 101
set creation ms = 12857

array1.length = 1000000
array2.length = 1000000
diff.size() = 524142
elapsed ms for calculating diff = 1167
(didn't bother to wait for the program to finish)

As you can see, doing a double loop to compare every element scales quite poorly, and that's not even counting the subtraction you'll have to do afterwards.

EDIT updated to reflect changes in the question

Answer 2

If you're worried about performance, definitely do not use any list or collection classes. They are notorious for re-allocating arrays frequently as they need more capacity, which is a very slow operation.

Unfortunately, I don't know how you create/fill the set of indices. If it is possible for you to have your set in an array as well and generate it in such a way that its entries are sorted, you can optimize your code significantly.

If set is fairly long compared to oldArray, do this (this assumes no duplicate entries in set!):

int l = oldArray.length; // Cache length (some compilers might do this for you)
for (int i=0, j=0, k=0; i<l; i++) {
    if (set[k]==i) {
        k++;
    } else {
        newArr[j++] = oldArray[i];
    }
}

If set is fairly short, do this (this can handle duplicate entries, but set still needs to be sorted):

int o1=0;
int o2=0;
for (int p:set) {
    System.arraycopy(oldArray, o1, newArr, o2, p-o1);
    o1+=p+1;
    o2+=p;
}
System.arraycopy(oldArray, o1, newArray, o2, oldArray.length-o1);

The former avoids function calls and the latter banks on the optimized memory-copy implementation of System.arraycopy(...) (and set can be any sorted Iterable, although an array will be faster).

Which one is faster will depend on the exact sizes of your arrays and which system (CPU, JVM) you use.

If set is not sorted, you can either use your approach (debugged, of course) or you can sort it first and then use one of the approaches here. Again, which one will give you better performance will depend on the size of set and your system.

Answer 3

This piece of code is doing it for me. Thanks @ Patricia Shanahan

         int j = 0, i = 0;
         while( j < newArr.length && i < oldArray.length){

           if(commonSet.contains(i)){
                i++;
               }
           else{
               diffArray[j] = arrayOne[i];
               j++;
               i++;
             }
          }