8
\$\begingroup\$

Suppose I have the array:

double[] arrayToCut = new double[100];
for(int i = 0 ; i < 100 ; ++i) {
    arrayToCut[i] = Math.random();
}

My objective is to end up with two arrays, firstArray and secondArray. firstArray is equal to (for example);

double[] firstArray = new double[50];
for(int i = 0 ; i < 50 ; ++i) {
    firstArray[i] = arrayToCut[i];
}

and secondArray is defined analogously (taking values from arrayToCut from 50 to 99 index).

However, this is linear time complexity and I want to cut gigantic arrays over 1 million in length. How can I speed up the above code (reduce computational overhead in any way for large arrays, whether by time complexity reduction or some other approach)?

\$\endgroup\$
10
\$\begingroup\$

I am pretty sure you can use copyOfRange(double[] original, int from, int to) from java.util.Arrays. @Rolfl said, and I quote : It is recommended practice to use Arrays.copyOf instead of System.arraycopy().

If you need to cut up the million+ array for parallel processing, then I would suggest you chunk the data while reading it, this should save you a processing step.


Edit: Internally, Arrays.copyOf() uses System.arraycopy() to do the hard work of duplicating the Array data in the new copy, and it will make your code look like this simple 1-liner:

double[] firstArray = Arrays.copyOf(arrayToCut, 50);
double[] secondArray = Arrays.copyOfRange(arrayToCut, 50, 100);

While using System.arraycopy() may seem like the fastest alternative, whenever you copy an array you have to:

  • first create the destination for the data to be copied to. This step requires initializing all the destination array points to their initialization values, which is a linear operation, but done in native code, so is fast.
  • then call the System.arraycopy() for the actual data re-write.

There are many ways that people may want to do this operation, and the various Arrays.copy*() methods are designed to make the relatively mundane, yet still rather complicated and bug-prone process a lot simpler, and less buggy.

Whenever you have a use case where you are copying data from one array to a new array, you should by default use the Arrays.copy*() methods. Only when you have a use case where you are overwriting data in to an existing array (or relocating data inside an array) should you use System.arraycopy(). As for the performance aspect, it appears that the performance of most native mechanisms are similar.

Arrays.copy* methods lead to better, more maintainable, and less buggy code, and, there is essentially no performance penalty because it is just doing the work you were going to do anyway.

\$\endgroup\$
  • \$\begingroup\$ This will actually call System.arrayCopy, as can be seen in the source \$\endgroup\$ – Simon Forsberg Feb 7 '14 at 14:44
  • \$\begingroup\$ Right your are! \$\endgroup\$ – konijn Feb 7 '14 at 14:52
  • 1
    \$\begingroup\$ +1 because 10 is so much nicer than 9, and 11 silver / 77 bronze is so much better than 11 silver / 76 bronze ;) \$\endgroup\$ – Mathieu Guindon Feb 11 '14 at 3:23
6
\$\begingroup\$

The method System.arrayCopy(...) invokes the native JIT implementation code for copying arrays and is the fastest alternative for large arrays.

In the end though, Arrays.copyOfRange is actually calling System.arrayCopy.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.