(I had been writing this before I received Max’s answer. Still...)
>From a general point of vue I agree that declaring a LinkedList makes
sense, when you want to stress the fact that you’re working with
a sequential structure with which it’s cheap to add/remove/access
elements at the beginning or end, but costly to retrieve one particular
element in the middle.
The unfortunate fact in Java is that the getFirst/Last and addFirst/Last
methods are available only in the LinkedList concrete class, and not on
an interface. Starting from Java 1.5 the Queue interface fills this gap
and would probably be used instead.
That said, on this particular topic, one may raise the question whether
the getNextKnuthElements methods should really return a sequential
structure or just a list. Looking at the commit, most of the getLast
method calls are used to test if the last returned element is a forced
break. In some future this should disappear and be handled a different
way (add a break /between/ blocks if there must be one). So I’m ok with
Max’s change.
And, still, congrats Max! It’s not the funniest of the jobs.
Andreas Delmelle wrote:
<snip/>
> For anything that remains FOP-internal, using concrete implementations
> does not only improve code-readability and -writability, but IIC, it
> also generates more efficient byte-code in the end. At run-time, the
> interpreter would spend slightly less time on determining the actual
> implementation of a method to be used.
>
> For the above example, the interpreter originally only needed to check
> the available implementations of getLast() (defined in the concrete
> class LinkedList), while after the change, it would need to check those
> of get() (defined in the List interface). Checking for the
> implementations of interface methods is known to be slightly more
> demanding than for class methods.
> Also, if we always know that the concrete type of the List in question
> is a LinkedList, index-based access is generally taken to be a bad idea.
> list.getLast() is likely to outperform list.get(list.size() - 1),
> especially if the lists grow large....
I really have to disagree here. In general I would be very reluctant to
sacrifice code encapsulation to optimization, unless the gain in
performance is significant. And on this particular point there’s
absolutely no benefit. The method lookup is negligible and probably done
only once, and there’s also JIT compiling that blurs things. And the
implementation of get in LinkedList is intelligent enough to start from
the end of the list when applicable. See the attached code, that’s worth
what it’s worth, but the same amount of time is spent in both ways.
Vincent
--
Vincent Hennebert Anyware Technologies
http://people.apache.org/~vhennebert http://www.anyware-tech.com
Apache FOP Committer FOP Development/Consulting
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class ListVsLinkedList {
private static final int REPEAT_TEST = 1000;
private static final int NB_ADDITIONS = 100000;
/**
* @param args
*/
public static void main(String[] args) {
List<Integer> list = new LinkedList<Integer>();
LinkedList<Integer> linkedList = new LinkedList<Integer>();
List<Long> timeList = new ArrayList<Long>(REPEAT_TEST);
List<Long> timeLinkedList = new ArrayList<Long>(REPEAT_TEST);
for (int i = 0; i < 1000; i++) {
long timeBefore = System.currentTimeMillis();
for (int j = 0; j < NB_ADDITIONS; j++) {
list.add(j);
list.get(list.size() - 1);
}
long timeAfter = System.currentTimeMillis();
timeList.add(timeAfter - timeBefore);
list.clear();
timeBefore = System.currentTimeMillis();
for (int j = 0; j < NB_ADDITIONS; j++) {
linkedList.add(j);
linkedList.getLast();
}
timeAfter = System.currentTimeMillis();
timeLinkedList.add(timeAfter - timeBefore);
linkedList.clear();
}
long sum = 0;
for (long time: timeList) {
sum += time;
}
System.out.println("List: " + (sum / REPEAT_TEST) + "ms");
sum = 0;
for (long time: timeLinkedList) {
sum += time;
}
System.out.println("LinkedList: " + (sum / REPEAT_TEST) + "ms");
}
}
