StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Remember that big-O complexity describes asymptotic behaviour and may not reflect actual implementation speed. It describes how the cost of each operation grows with the size of the list, not the speed of each operation. For example, the following implementation of <code>add</code> is O(1) but is not fast:</p> <pre><code>public class MyList extends LinkedList { public void add(Object o) { Thread.sleep(10000); super.add(o); } } </code></pre> <p>I suspect in your case ArrayList is performing well because it increases it's internal buffer size fairly aggressively so there will not be a large number of reallocations. When the buffer does not need to be resized ArrayList will have faster <code>add</code>s.</p> <p>You also need to be very careful when you do this kind of profiling. I'd suggest you change your profiling code to do a warm-up phase (so the JIT has the opportunity to do some optimization without affecting your results) and average the results over a number of runs.</p> <pre><code>private final static int WARMUP = 1000; private final static int TEST = 1000; private final static int SIZE = 500000; public void perfTest() { // Warmup for (int i = 0; i < WARMUP; ++i) { buildArrayList(); } // Test long sum = 0; for (int i = 0; i < TEST; ++i) { sum += buildArrayList(); } System.out.println("Average time to build array list: " + (sum / TEST)); } public long buildArrayList() { long start = System.nanoTime(); ArrayList a = new ArrayList(); for (int i = 0; i < SIZE; ++i) { a.add(i); } long end = System.nanoTime(); return end - start; } ... same for buildLinkedList </code></pre> <p>(Note that <code>sum</code> may overflow and you might be better to use <code>System.currentTimeMillis()</code>).</p> <p>It's also possible that the compiler is optimizing away your empty <code>get</code> loops. Make sure the loop actually does something to ensure that the right code is getting called.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload