Your results piqued my interest. I have created a test program to determine
at which point the linked list becomes more efficient than the array list.
Here are my results:
List Size = 16 elements
Iterations = 1,000,000
ArrayList = 331 ms
LinkedList = 761 ms
List Size = 32 elements
Iterations = 1,000,000
ArrayList = 391 ms
LinkedList = 761 ms
List Size = 64 elements
Iterations = 1,000,000
ArrayList = 460 ms
LinkedList = 751 ms
List Size = 128 elements
Iterations = 1,000,000
ArrayList = 601 ms
LinkedList = 751 ms
List Size = 256 elements
Iterations = 1,000,000
ArrayList = 881 ms
LinkedList = 761 ms
As you can see, the linked list's add/remove time remains constant, while
the array list experiences linear degradation. The crossover point being
somewhare around 200 some elements. Anyway, it was an interesting exercise.
Below is the program I used to test this, and all results above were
generated w/ a P4 @ 1.4GHz, 512 MB RAM.
Chad
import java.util.*;
public class ListTest
{
public static void main(String[] args)
{
int lInitialSize = Integer.parseInt(args[0]);
int lIterations = Integer.parseInt(args[1]);
ArrayList lArrayList = new ArrayList(lInitialSize + 1);
LinkedList lLinkedList = new LinkedList();
long lBegin, lEnd;
for (int i = 0; i < lInitialSize; i++)
{
lArrayList.add(new Integer(i));
lLinkedList.add(new Integer(i));
}
lBegin = System.currentTimeMillis();
for (int i = 0; i < lIterations; i++)
{
lArrayList.add(0, new Integer(i)); // Add to the head
lArrayList.remove(lInitialSize); // Remove from the tail
}
lEnd = System.currentTimeMillis();
System.out.println("Time: " + (lEnd - lBegin));
lBegin = System.currentTimeMillis();
for (int i = 0; i < lIterations; i++)
{
lLinkedList.addFirst(new Integer(i)); // Add to the head
lLinkedList.removeLast(); // Remove from the tail
}
lEnd = System.currentTimeMillis();
System.out.println("Time: " + (lEnd - lBegin));
}
}
----- Original Message -----
From: "Berin Loritsch" <[EMAIL PROTECTED]>
To: "Avalon Developers List" <avalon-dev@jakarta.apache.org>
Sent: Wednesday, December 19, 2001 12:37 PM
Subject: Re: [Report] Efficiencies of FixedSize and Default Queues
> NOTE:
>
> Test environment is 750 MHz Athlon using JDK 1.3.0_02 with 256MB RAM
> on Win2K.
>
> Berin Loritsch wrote:
>
> > My initial testing (consisting of running the TestCases several times)
> > reveals the cost of an enqueue/dequeue operation. This consists of
> > both single element vs. multiple element enqueue/dequeue operations.
> > All calls are paired.
> >
> > The average cost of using the Default Queue is 1.156 usecs per
> > enqueue/dequeue operation. This is pretty decent considering that the
> > Queue is ThreadSafe (i.e. locking is performed). It uses an ArrayList
> > to perform it's duties.
> >
> > The average cost of using the Fixed Size Queue is 884.0 nsecs per
> > enqueue/dequeue operation. This is a little over half the cost of
> > the DefaultQueue, and it is also ThreadSafe. It directly manipulates
> > an array to perform it's duties.
> >
> > The array manipulation works like this:
> >
> > | 1 | 2 | 3 | 4 | 5 |
> > * *
> > S E
> >
> > S = Start
> > E = End
> >
> > The current figure shows a queue with 1 element enqueued. When S=E,
> > there are no elements enqueued. The next figure shows what happens
> > when the element is dequeued:
> >
> > | 1 | 2 | 3 | 4 | 5 |
> > **
> > SE
> >
> > The Start pointer moves forward when there are elements to dequeue,
> > and the End pointer moves forward when a new element is enqueued. It
> > is also important to note that the entry where start is is nulled after
> > it is retrieved.
> >
> > The algorithm wraps the pointers back to 0 when they reach the maximum.
> >
> > This moving pointer system works quite well, and never requires useless
> > creation of objects or new queue sizes during the life of the Queue.
> >
>
>
>
> --
>
> "They that give up essential liberty to obtain a little temporary safety
> deserve neither liberty nor safety."
> - Benjamin Franklin
>
>
> --
> To unsubscribe, e-mail:
<mailto:[EMAIL PROTECTED]>
> For additional commands, e-mail:
<mailto:[EMAIL PROTECTED]>
>
>
--
To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
