CODEWITHSUNDEEP
javaperformance
user1730056
user1730056

Reputation: 623

How can I make my function run in constant time?

I just received back my assignment and I lost marks for one function because it does not run at constant time, it wasn't efficient enough. I would have to go through the trouble of booking an appointment and waiting to get an answer from my prof, I was wondering if someone here could help me now.

I have a function that removes and returns randomly an item from an ArrayList.

public T pick() {
    int end = l.size() - 5;
    if (l.size() == 0)
        return null;
    assert(next >= 2 && next <= l.size()-1);
    T x = l.remove(next);
    next = (l.size() > 0) ? r.nextInt(l.size()) : -5;
    return x;
}

Could someone point out what I can do to make this code more efficient? Thank you in advance!

Upvotes: 1

Views: 308

Answers (1)

nosid
nosid

Reputation: 50074

The method ArrayList.remove has linear time complexity, if next is not near to the end. The trick is to swap the element at position next with the last element, and remove the last element.

T x = l.get(next);
l.set(next, l.get(l.size() - 1));
l.remove(l.size() - 1);

Upvotes: 3

Related Questions