when implementing a binary search in Java, is using ArrayList.sublist considered 'in place'?

Question

The question is pretty much as stated in the title. I'm in an algorithms course and the professor and I disagree regarding whether or not operations performed on an ArrayList sublist (a sublist generated by ArrayList.sublist) can be considered 'in place'. To my read of the Java API:

Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive. (If fromIndex and toIndex are equal, the returned list is empty.) The returned list is backed by this list, so non-structural changes in the returned list are reflected in this list, and vice-versa. The returned list supports all of the optional list operations.

you are still manipulating the 'master' ArrayList directly. To his view, you are copying references from the 'master' array into a new sub-array which means employing ArrayList.subList is not considered 'in place'. Obviously, for the purposes of the course what he says goes (that is, if I want to pass :-/) but I would like to know either way for my own growth as a programmer. Code is below - and thank you!

public static int findK (int findME, int mVal, ArrayList<Integer> arr) {

    // pre stage return variable
    int returnVal = -1;

    // make a subarray consisting of indexes 0 - ((m-2)+(m-1)).
    // this because the relationship between the m, p, and q
    // is p>q>m - therfore the max value of q is m-1 and the
    // max value of p is m-2.
    int newArrSize = (mVal-2) + (mVal-1);
    ArrayList<Integer> subArr = new ArrayList<Integer>(arr.subList(0, newArrSize));

    // make the list smaller by looking at only the last [mVal]
    // elements. this because we know what we're looking for
    // has to be in the second section of the array, and that
    // section can't possibly be larger than mVal
    int fromIndex = subArr.size() - mVal;
    subArr = new ArrayList<Integer> (subArr.subList(fromIndex, subArr.size()));

    // at this point we can do a simple binary search, which on an
    // a sorted array of size mVal is lg(m)
    while (subArr.size() > 1) {

        // get midpoint value
        int midPointIndex = subArr.size() / 2;
        int midPointValue = subArr.get(midPointIndex);

        // check for case where midpoint value is in the first
        // region of the array
        // check for case where the midpoint is less than the
        // findME value
        //
        // if true, discard first half of the array
        if ((midPointValue == 9000) || (midPointValue < findME)) {
            subArr = new ArrayList<Integer> (subArr.subList(midPointIndex, subArr.size()));
            continue;
        }
        // else if midpoint is less than findMe, discard the second
        // half of the array
        else if (midPointValue > findME) {
            subArr = new ArrayList<Integer> (subArr.subList(0, midPointIndex));
            continue;
        }

        // if we're here, we've found our value!
        returnVal = midPointValue;
        break;


    }


    // check for match and return result to caller
    // only perform check if we haven't already found the value
    // we're looking for
    if (returnVal == -1) returnVal = (subArr.get(0) == findME) ? (subArr.get(0)) : (-1);
    return returnVal;

}

"In-place" usually refers to modifications, I believe. A search does not modify anything. This is more a question of semantics, anyway; it's more important to understand the underlying concepts that to have a perfectly precise definition of every term. So basically: I wouldn't worry about it. If there's a chance saying it's "in-place" might confuse someone, find a term that is less ambiguous. — jpmc26
– jpmc26, Commented Jun 3, 2014 at 3:30
I think he's thinking that ArrayList.sublist somehow creates a whole new list and that adds to the complexity of the algorithm. That's what I'm debating with him about. — snerd
– snerd, Commented Jun 3, 2014 at 3:31
subList does not copy data. It merely references a range within the first list. It adds to the complexity, but is constant-time, so it's trivial — etherous
– etherous, Commented Jun 3, 2014 at 3:36
Your TA is cheating. A primitive array is pretty much guaranteed to be faster than an ArrayList<Integer> no matter what you do with it, and that test doesn't even have much to do with the issue at hand anyways. I'd just direct them to the source code, as nowhere in there can they prove that a new list is made. All that's made is a new view. The abundance of ArrayList.this.___ and parent.___ only show that the sublist delegates all work to the containing class. — awksp
– awksp, Commented Jun 3, 2014 at 3:42
source code - capital idea!! just checked the openJDK implantation and indeed it is performing the operation against the master list. docjar.com/html/api/java/util/ArrayList.java.html — snerd
– snerd, Commented Jun 3, 2014 at 3:48

fabian · Accepted Answer · 2014-06-03 04:20:49Z

I assume in this answer, that by "in place" actually "uses constant additional memory" is meant.

The sublist function creates a view of the original list. This uses only O(1) memory.

However you allocate a new list (Indices were replaced with my own names here, for simplicity):

subArr = new ArrayList<Integer> (subArr.subList(index1, index2));

What you do with such a statement is:

create a subList view (uses O(1) memory)
copy the sublist (uses O(sublist size) = O(index2 - index1) memory).
delete reference to subList (and by that the reference to the old list too)

Note that the garbage collector can not claim the memory of the old list until all references to it are deleted. The sublist view contains a reference to the old list, so the old list cannot be claimed by the GC until all references to the sublist view are deleted. This means for a short while you use O(index2 - index1) more memory than in the list at the beginning. Since binary search makes the list half as large in every step, you use O(subArr.size()) additional memory (not in O(1)).

Will Hartung · Accepted Answer · 2014-06-03 04:05:21Z

2

Lines like these:

subArr = new ArrayList<Integer> (subArr.subList(fromIndex, subArr.size()));

That's your "copy". The new ArrayList is indeed, a copy of the data from the subList.

If you were using the subList "raw", then it could be better argued that you are "in place", because then the subList is simply a set of offsets in to the original array.

But with the create of new ArrayLists, you are definitely copying.

Of course, the easiest way to check is that when you find your value, change the value in the list to some sentinel (9999 or whatever). Then dump your original list. If 9999 shows up, it's in place. If not, then, it's not.

answered Jun 3, 2014 at 4:05

Will Hartung

119k20 gold badges134 silver badges209 bronze badges

4 Comments

snerd Over a year ago

can you better explain what you mean by 'sublist raw'? To my read, this is simply casting the returned view as an ArrayList.

awksp Over a year ago

@DavidDaedalus This means simply doing List<something> subArr = arr.subList(begin, end); instead of passing the result of subList() to a constructor.

jpmc26 Over a year ago

@DavidDaedalus new X always creates a new object. A cast would look like this: (ArrayList<Integer>)subArr.subList(fromIndex, subArr.size()), which should fail since it's not an ArrayList. Start getting into the habit of declaring your variables to be List<Integer> (the interface) so that you code continues to work if you decide you need to change list implementations for performance or what have you.

snerd Over a year ago

derp! I totally should've seen that what I was doing wasn't a cast:-)

awksp · Accepted Answer · 2014-06-03 04:05:42Z

"In-place" isn't a term that applies to binary-search, as it almost always refers to how modifications are made (e.g. for sorting, like quicksort (in-place) and mergesort (not in-place)). So it's not something you need to worry about for binary search, as searching makes no modifications.

As for whether ArrayList#subList() copies data, a look at the source code should prove that that is incorrect. Unfortunately, the source is a tad long for a SO answer, but I'll do my best to summarize.

The subList() method is this:

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

Where SubList is defined as the inner class:

private class SubList extends AbstractList<E> implements RandomAccess

with instance fields

private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;

Note how none of those fields are a type of array or list.

Looking at the implementations of mutators shows that all work is delegated to the parent class. For example, here is set():

public E set(int index, E e) {
    rangeCheck(index);
    checkForComodification();
    E oldValue = ArrayList.this.elementData(offset + index);
    ArrayList.this.elementData[offset + index] = e;
    return oldValue;
}

Notice how ArrayList.this is used to refer to the containing ArrayList instance, which means that the source ArrayList implementation is modified and not any (nonexistent) copy.

The add() method shows something similar:

public void add(int index, E e) {
    rangeCheckForAdd(index);
    checkForComodification();
    parent.add(parentOffset + index, e);
    this.modCount = parent.modCount;
    this.size++;
}

parent.add() is used here, where parent is also the containing instance. So again, it is the source list that is modified, and not any (nonexistent) copy.

And so on and so forth.

However, as pointed out by Will Hartung, all this is moot if you pass the resulting SubList into the constructor of a new ArrayList<>(), as the constructor:

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray(); // <------------ This line
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

makes a copy of the internal array (through toArray()), which is the copy your professor/TA were likely talking about.

Collectives™ on Stack Overflow

when implementing a binary search in Java, is using ArrayList.sublist considered 'in place'?

3 Answers 3

Comments

4 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related