Making this arraycopy more efficient

Question

I'd like to find out how I can make my function more efficient:

public boolean addAll(int i, Collection<? extends T> c) {
 for (T x : c)
 add(i++, x);
 return true;
}
public void add(int i, T x) {
 if (n + 1 > a.length) resize();
 System.arraycopy(a, i, a, i+1, n-i);
 a[i] = x;
 n++;
}
protected void resize() {
 T[] b = f.newArray(Math.max(2 * n,1));
 System.arraycopy(a, 0, b, 0, n);
 a = b;
}

I'm not sure what else I can do to implement a more efficient way to use my addAll() function.

Answer 1

As @Brythan suggested, you should rename your variables. I propose:

• arr instead of a
• size instead of n
• index instead of i
• copy instead of b
• items or elements or collection instead of c

I suppose that addAll returns a boolean to mimic the behavior of Collections.addAll. That is all well, except you're not actually implementing that behavior, only the method signature. The JavaDoc says:

Returns:

true if the collection changed as a result of the call

So you should change your implementation accordingly. Perhaps something like this:

public boolean addAll(int index, Collection<? extends T> items) {
 if (items.isEmpty()) {
 return false;
 }
 if (size + items.size() > arr.length) {
 resize(2 * (size + items.size()));
 }
 System.arraycopy(arr, index, arr, index + items.size(), size - index);
 for (T item : items) {
 arr[index++] = item;
 }
 size += items.size();
 return true;
}

This also includes my naming suggestions, as well as Brythan's advice to avoid calling add one by one for each element. For the resizing, I added a helper method and refactored the existing one like this:

private void resize() {
 resize(Math.max(2 * size, 1));
}
private void resize(int targetSize) {
 T[] copy = newArray(targetSize);
 System.arraycopy(arr, 0, copy, 0, size);
 arr = copy;
}

(Since I don't know what was "f" in your original f.newArray, I wrote my own newArray.)

Notice that I changed the visibility of resize to private. This is an internal operation that shouldn't be accessible by any other class by default.

Finally, by the same logic of addAll (following existing examples), add should also return boolean: true if the collection was modified. (In your case always.)

Answer 2

First, this would be easier if you named things more descriptively. I don't know enough about a to suggest a name. For i though, it should be called something like currentPosition. For n, something like aCount if the array is still named a.

You are calling add on every member of your collection. This could potentially do two System.arraycopy calls and a memory allocation for every member. Instead, addAll should do the same things that add does only it should do it for the entire collection at once. That gets us down to two System.arraycopy calls and a memory allocation total.

if (n + 1 > a.length) resize();
System.arraycopy(a, i, a, i+1, n-i);

Rewrite these for addAll.

Hint: the 1 is incorrect for addAll. Replace the 1 with the appropriate value based on the collection.

a[i] = x;
n++;

These are mostly correct. You can put them in the for loop that you are using to call add in your current code. There needs to be one change in the first line to make it work.

You can also take the n++ out of the for loop and rewrite it into a single statement if you want.

Hint: n++ is the equivalent of n += 1 and we already discussed that 1 is wrong for addAll.

Finally, you never return false from addAll. Why make it return anything at all?