CODEWITHSUNDEEP
javaperformancelistswapindexof
classOlek
classOlek

Reputation: 33

Code optimality

Every time I'm coding I have dilemma between creating more variables and using methods, that make code more clear but less optimal? Can you tell me what is better for our application performance?

For example:

protected static <T> void exch(List<T> list, Object o1, Object o2) {
    list.set(list.indexOf(o1), list.set(list.indexOf(o2), list.get(list.indexOf(o1))));
}

Should I use:

indexOf(o1)

twice or make temp variable instead?

PS Just to make it clear for you. I'm writing few types of sorting methods for my university project. We're sorting lists that have ~150k elements. I would really like to get the best performance.

Upvotes: 3

Views: 94

Answers (2)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476574

If you exchange on objects, the best you can do is indeed first calculate the indexOf(o1) once, since this is an O(n) operation: meaning that if you have a list with ~100k elements, it will require approximately twice the time compared to ~50k elements in the worst case. You do not want to do this expensive task twice. So you can optimize it to:

protected static <T> void exch(List<T> list, T o1, T o2) {
    int i1 = list.indexOf(o1);
    list.set(i1, list.set(list.indexOf(o2), list.get(i1)));
}

That's however not all. You do not need to call list.get(i1): you know the result will be o1 (given you did not override the .equals(..) method. But if you are sorting, I assume that you have a reference to the real object, not to an equivalent object. So you can rewrite it to:

protected static <T> void exch(List<T> list, T o1, T o2) {
    int i2 = list.indexOf(o2);
    list.set(list.indexOf(o1),o2);
    list.set(i2,o1);
}

It is of vital importance here to first obtain the index of o2: since once you have list.set(..,o2), there are two indices that map to o2. In order to get the old one, we first have obtain the index.

Declaring an int in a method has no impact on the garbage collection process: the int will be declared on the call stack or it will use an accumulator (and thus have no memory address at all). That depends on your processor architecture, etc. Nevertheless the impact of declaring an int is minimal in terms of speed. Making a method call alone will have more impact: you make a call frame on the call stack, have to jump to that method, etc. The overhead is "large" compared to declaring one int.

Nevertheless I think your sorting algorithm is of bad design if you exchange objects by fetching there index. As said before this is an O(n) operation. If you do bookkeeping on the indices. You can make it an O(1) operation (this will result in a speedup of approximately ~50k) so that is where the real speedup lies (even if you manage to get the most out of the indexOf method, it inherently will be outperformed by a method working on indices). You can then implement it like:

protected static <T> void exch(List<T> list, int i1, int i2) {
    T o1 = list.get(i1);
    list.set(i1,list.get(i2));
    list.set(i2,o1);
}

Upvotes: 4

Jesus is Lord
Jesus is Lord

Reputation: 15399

If I was writing the details of that method I'd probably do this if I was going for readability.

protected static <T> void exch(List<T> list, Object o1, Object o2) {
    int indexOfO1 = list.indexOf(o1);
    int indexOfO2 = list.indexOf(o2);
    // TODO: Handle if either indexOf was out of range.
    list.set(indexOfO2, o1);
    list.set(indexOfO1, o2);
}

I don't think doing it in one line like you have will matter in terms of performance. Read about premature optimization.

Upvotes: 0

Related Questions