Popular @ dzone.com: fresh links for developers

Submit a story   Vote on new stories
Forum Controls
Whos Online: 155 guest(s), 0 user(s). More info »
Spotlight Features

The Rich Engineering Heritage Behind Dependency Injection

Andrew McVeigh takes us on a tour of the rich heritage behind dependency injection, what it represents, and tells us why its here to stay.

NetBeans 6: Matisse Updates

NetBeans 6 delivers great updates to the Matisse GUI builder. Spend a few minutes with Roman Strobl and get an expert briefing on what's new and what has changed.

Introduction to Groovy Part 3

In this, the third and final installation of Andres' Introduction to Groovy series, you learn about how Groovy handles variable numbers of arguments, named parameters, currying, and more about Groovy operators. Including, some new operators.

Easier Custom Components with Swing Fuse

Swing Fuse (actually just Fuse), is a framework designed to make it easier to create your own custom desktop components. In this article, Daniel Spiewak shows you how to get started and provides sample source code you can download.

Benchmark Analysis: Guice vs Spring

Willam Louth shows how he uses JXInsight Probes to investigate probable performance issues with code bases that he is not familiar with. He also highlights possible pitfalls in creating a benchmark, as well as in the analysis of results.
Read the Spotlight Archives
Replies: 2 - Pages: 1  
Threads: [ Previous | Next ]
  Click to reply to this thread Reply

Question #16739 collections

At 1:08 PM on Jun 12, 2007, Stefan van Risswyck wrote:

The answer is wrong:
The insertion of elements in the middle of a list is in the ArrayList-implementation much faster than in the LinkedList due to the fact, that the linked list first has to traverse half of the list to find the insertion point, while the ArrayList uses the fast System.arracopy method. Performance gap is big! Please try the following code snippet as demonstration 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Vector;
 
class Test {
 private static final int COUNT = 30000;
 
 public static void main(String[] args) {
   doTest(new Vector());
   doTest(new ArrayList());
   doTest(new LinkedList());
 }
 
 private static void doTest(List list) {
   for (int i = 0; i < COUNT; i++) {
     list.add(new Integer(i));
   }
   long start = System.currentTimeMillis();
   for (int i = 0; i < COUNT; i++) {
     list.add(list.size() / 2, new Integer(i));
   }
   long end = System.currentTimeMillis();
   System.out.println("elapsed time = " + (end - start));
 }
 
}


I commented this question twice: no change.
The answer "LinkedList" is false!!!

2 replies so far ( Post your own)

1 . At 9:45 PM on Jun 12, 2007, Chinh Nguyen wrote:
  Click to reply to this thread Reply

Re: Question #16739 collections

Thanks for bringing it to my attention (You could also use the "Require attention from the exam leader" option though)

I think it is really hard to give a clear answer to this question. Adding an element to a LinkedList takes constant time, while indexing takes linear time. The reverse is true for ArrayList. So if we are comparing the add(int index, E element) method, the result is pretty much implementation-dependent.

The answer is still correct if the question is asking about the addition only. But unfortunately the corresponding method is private so we have nothing to compare.

Anyway, your test should eliminate the size() method and new Integer() constructor to provide a more exact comparison.

I think the question is too hard for Java SE - Basic so I moved it to Collections. But maybe it would fit better in the (future) algorithm and data structure exam.
Brown Belt #1450799
2 . At 4:32 AM on Jun 13, 2007, Stefan van Risswyck wrote:
  Click to reply to this thread Reply

Re: Question #16739 collections

Correct, I changed the code snippet to 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Vector;
 
class Test {
 private static final int COUNT = 30000;
 
 public static void main(String[] args) {
   doTest(new Vector());
   doTest(new ArrayList());
   doTest(new LinkedList());
 }
 
 private static void doTest(List list) {
   Object obj = new Object();
   for (int i = 0; i < COUNT; i++) {
     list.add(obj);
   }
   long start = System.currentTimeMillis();
   for (int i = 0; i < COUNT; i++) {
     list.add( (COUNT + i) / 2, obj);
   }
   long end = System.currentTimeMillis();
   System.out.println("elapsed time = " + (end - start));
 }
 
}


The behaviour didn't change.
I think it is a good idea to move the question to another category, but there is still the problem with the private method.
Replies: 2 - Pages: 1   Threads: [ Previous | Next ]

thread.rss_message