CODEWITHSUNDEEP
javaperformancedata-structuresbig-o
Manuel
Manuel

Reputation: 1004

How can I make this code run in O(c.size()+n-i) time?

public boolean addAll(int i, Collection<? extends T> c) {
   for (T x : c)
   add(i++, x);
   return true;
}

The List method addAll(i,c) inserts all elements of the Collection c into the list at position i. This takes a LOT of time. Is there any way it can be implemented faster ? Any ideas, please? Thanks

Here is the implementation of the arrayDeque:

public class ArrayDeque extends AbstractList { /** * The class of elements stored in this queue */ protected Factory f;

/**
 * Array used to store elements
 */
protected T[] a;

/**
 * Index of next element to de-queue
 */
protected int j;

/**
 * Number of elements in the queue
 */
protected int n;

/**
 * Grow the internal array
 */
protected void resize() {
    T[] b = f.newArray(Math.max(2*n,1));
    for (int k = 0; k < n; k++) 
        b[k] = a[(j+k) % a.length];
    a = b;
    j = 0;
}

/**
 * Constructor
 */
public ArrayDeque(Class<T> t) {
    f = new Factory<T>(t);
    a = f.newArray(1);
    j = 0;
    n = 0;
}

public int size() {
    return n;
}

public T get(int i) {
    if (i < 0 || i > n-1) throw new IndexOutOfBoundsException();
    return a[(j+i)%a.length];
}

public T set(int i, T x) {
    if (i < 0 || i > n-1) throw new IndexOutOfBoundsException();
    T y = a[(j+i)%a.length];
    a[(j+i)%a.length] = x;
    return y;
}

public void add(int i, T x) {
    if (i < 0 || i > n) throw new IndexOutOfBoundsException();
    if (n+1 > a.length) resize();
    if (i < n/2) {  // shift a[0],..,a[i-1] left one position
        j = (j == 0) ? a.length - 1 : j - 1; // (j-1) mod a.length
        for (int k = 0; k <= i-1; k++)
            a[(j+k)%a.length] = a[(j+k+1)%a.length];
    } else {        // shift a[i],..,a[n-1] right one position
        for (int k = n; k > i; k--)
            a[(j+k)%a.length] = a[(j+k-1)%a.length];
    }
    a[(j+i)%a.length] = x;
    n++;
}

public T remove(int i) {
    if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException();
    T x = a[(j+i)%a.length];
    if (i < n/2) {  // shift a[0],..,[i-1] right one position
        for (int k = i; k > 0; k--)
            a[(j+k)%a.length] = a[(j+k-1)%a.length];
        j = (j + 1) % a.length;
    } else {        // shift a[i+1],..,a[n-1] left one position
        for (int k = i; k < n-1; k++)
            a[(j+k)%a.length] = a[(j+k+1)%a.length];
    }
    n--;
    if (3*n < a.length) resize();
    return x;
}

public void clear() {
    n = 0;
    resize();
}

}

Upvotes: 1

Views: 323

Answers (1)

templatetypedef
templatetypedef

Reputation: 372664

Rather than adding items one at a time, consider doing the following:

  • Ensure enough space exists in the data structure for all the new elements.
  • Shift all elements at position i down a number of spaces equal to the number of new elements that will be added. This can be done in time O(1 + n - i), since each item is moved exactly once.
  • Write the elements to be inserted into the new spot.

Overall, this takes time O(n - i + k + 1), where n is the number of elements in the original data structure, i is the position to insert, and k is the number of new elements inserted. The key advantage is that you do all the shifting at once, rather than doing lots and lots of smaller shifts.

Hope this helps!

Upvotes: 2

Related Questions