Piroumian, Konstantin wrote:
> Sylvain, Berin,
>
> you are very convincing ;)
> I told that only because just yesterday have read about it in Bruce Eckel's
> "Thinking in Java 2nd Edition" (Appendix C, Implementation section, 14). It
> sounds something like (have read it in Russian and will try to translate it
> back to English):
>
> 14. ...
> <quot>
> Use containers from standart Java libs. Becoming more professional in
> container usage, you will also improve your perfomance. Prefer to use
> ArrayList for sequences, HashSet for sets, HashMap for associated arrays and
> LinkedList for stacks (instead of Stack) and queries.
> </quot>
You know what, I created my simple test, and found out something very interesting!
For stack operations (add last/remove last), the performance times of the
Lists are _very_ different!
Here are the results form running the following command line:
$java -cp ./build/scratchpad StackTest 123456 1000000
Time: 260
Time: 381
Time: 381
Time: 290
Where the stacks were populated with 123,456 items (much more than the buffers),
and the push/pop (or equivalent) operations were performed 1,000,000 times. The
order of the results are ArrayList, LinkedList, Stack, ArrayStack.
The interesting thing to note is that *all* collections performed with constant
access time heuristics. It didn't matter whether there was 624 items or 123,456
items in the stack--with 1,000,000 iterations it performed the same.
What is particularly interesting to note is that there is no real advantage of
using LinkedList over Stack with JDK 1.3 on windows. In fact you lose synchronization,
but gain no time. ArrayStack beat both LinkedList and Stack as was expected.
However, what I didn't expect was for ArrayList to beat everything!
While the actual times will vary accross machines, the relative speed of these
approaches is the same.
The final verdict:
Use ArrayList for Stack operations (by simply using add() and remove(lastindex)).
Use FixedSizeBuffer for FIFO buffer operations if you know the max size--otherwise
use VariableSizeBuffer.
BTW, here is the source code for StackTest:
--------------------------------------------------------------------------------
import java.util.*;
import org.apache.avalon.excalibur.collections.ArrayStack;
public class StackTest
{
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();
Stack lStack = new Stack();
ArrayStack lArrayStack = new ArrayStack();
long lBegin, lEnd;
for (int i = 0; i < lInitialSize; i++)
{
lArrayList.add(new Integer(i));
lLinkedList.add(new Integer(i));
lStack.push(new Integer(i));
lArrayStack.push(new Integer(i));
}
lBegin = System.currentTimeMillis();
for (int i = 0; i < lIterations; i++)
{
lArrayList.add(new Integer(i)); // Add to the tail
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.addLast(new Integer(i)); // Add to the tail
lLinkedList.removeLast(); // Remove from the tail
}
lEnd = System.currentTimeMillis();
System.out.println("Time: " + (lEnd - lBegin));
lBegin = System.currentTimeMillis();
for (int i = 0; i < lIterations; i++)
{
lStack.push( new Integer(i) );
lStack.pop(); // Remove from the tail
}
lEnd = System.currentTimeMillis();
System.out.println("Time: " + (lEnd - lBegin));
lBegin = System.currentTimeMillis();
for (int i = 0; i < lIterations; i++)
{
lArrayStack.push( new Integer(i) );
lArrayStack.pop();
}
lEnd = System.currentTimeMillis();
System.out.println("Time: " + (lEnd - lBegin));
}
}
---------------------------------------------------------------------
--
"They that give up essential liberty to obtain a little temporary safety
deserve neither liberty nor safety."
- Benjamin Franklin
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, email: [EMAIL PROTECTED]
