import java.util.*;
public class Main
{
public static void main( String[] args )
{
final boolean isArrayList = true;
final int max = 10000;
final Random rand = new Random( 0 );
for ( int i = 0; i < 10; i++ ) {
final List<Integer> ls = isArrayList ?
new ArrayList<Integer>() :
new LinkedList<Integer>();
for ( int j = 0; j < max; j++ ) {
ls.add( j );
}
final long start = System.currentTimeMillis();
for ( int j = 0; j < max; j++ ) {
final int index = rand.nextInt( ls.size() );
ls.remove( index );
}
System.out.println( System.currentTimeMillis() - start );
}
}
}
I am randomly removing all items, and when using an ArrayList, it is more then twice as fast then using a LinkedList, on my PC.
The error of your checking seems to be as that ArrayList tries to use the int you giving it as an index while the LinkedList tries to find and remove it.
I did a little more hideus testing (as to avoid other reasons to affect the time effect than just the removing).
My thinking is that Random, using Integers (instead of objects) and other such things may tweak the results, so I made sure to avoid those things when creating the test.
[quote] public Test(){
List mainList = createList();
Object[] toRemove = mainList.subList(4923, 44323).toArray();
ArrayList aList = new ArrayList();
LinkedList lList = new LinkedList();
for(Object o : mainList.toArray()){
aList.add(o);
lList.add(o);
}
remove(aList, toRemove);
remove(lList, toRemove);
}
private ArrayList<String> createList(){
ArrayList<String> a = new ArrayList<String>();
for(int i = 0; i<100000;i++){
a.add(NameGenerator.newString());
}
return a;
}
private void remove(List<Object> list, Object[] toRemove){
Long time = System.currentTimeMillis();
for(Object o : toRemove){
list.remove(o);
}
System.out.println(System.currentTimeMillis()-time);
}
[/quote]
Which gives me that LinkedList is 2-4 times quicker than an ArrayList is.
Three attempts:
ArrayList: 5462, 8187, 8110
LinkedList: 2213, 3329, 3328
I would’ve preferred to use a specific removal instead of pop/poll myself, makes it easier in the long run and as long as you aren’t doing hideus things there shouldn’t be any extensive CPU demands. In case the goal is to loop through often and not too many kills each loop that is.
Not true. The signature for the List.remove which removes by index is clearly defined. It is ‘int’, not ‘Integer’, and that is what I am passing in (so it binds tighter).
However to remove the ambiguity, I have changed my example to store String instead of Integer.
import java.util.*;
public class Main
{
public static void main( String[] args )
{
final boolean isArrayList = false;
final int max = 10000;
final Random rand = new Random( 0 );
final String[] strs = new String[ max ];
for ( int j = 0; j < max; j++ ) {
strs[j] = String.valueOf(j);
}
for ( int i = 0; i < 10; i++ ) {
final List<String> ls = isArrayList ?
new ArrayList<String>() :
new LinkedList<String>();
for ( int j = 0; j < max; j++ ) {
ls.add( strs[j] );
}
final long start = System.currentTimeMillis();
for ( int j = 0; j < max; j++ ) {
final int index = rand.nextInt( ls.size() );
ls.remove( index );
}
System.out.println( System.currentTimeMillis() - start );
}
}
}
The results are the same, when removing by index, ArrayList is on average faster then LinkedList.
Your test also does not take into account ‘random’ removals. Instead by using sublist, it is skewed towards one half of the list. This gives LinkedList an unfair advantage (unless a skewed random removal is what you are trying to test). So I have altered your test to create a random list of elements, and remove them. This gives a much better spread of removals.
public static void test2()
{
final int max = 25000;
final boolean isArrayList = false;
List<String> mainList = createList(max);
final String[] toRemove = new String[max];
final Random random = new Random(0);
for ( int i = 0; i < max; i++ ) {
final int index = random.nextInt( mainList.size() );
toRemove[i] = mainList.remove( index );
}
mainList = createList(max);
final List<String> list = isArrayList ?
new ArrayList<String>() :
new LinkedList<String>();
for ( int i = 0; i < 10; i++ ) {
for ( String o : mainList ){
list.add(o);
}
remove(list, toRemove);
}
}
private static ArrayList<String> createList( int length ){
final ArrayList<String> a = new ArrayList<String>();
for ( int i = 0; i<length; i++ ){
a.add( String.valueOf(i) );
}
return a;
}
private static void remove(List<String> list, String[] toRemove){
long time = System.currentTimeMillis();
for ( final String o : toRemove){
list.remove(o);
}
System.out.println(System.currentTimeMillis()-time);
}
With very large data sets, I found the ArrayList is faster. With smaller ones, the Linked List is marginally faster. But either way, you really shouldn’t be searching for objects in a List.
My overall point stands. For removal by index, ArrayList is faster then LinkedList, on average. For some special cases, LinkedList is faster, but generally there are better alternatives.
Disagree. The ArrayList will trounce the Linked List, easily, when used as a stack. Pretty much all stack implementations are essentially arrays underneath.
The ArrayDeque will also handle this job much faster then the ArrayList.
Tested it out and also made a new version which would include a little more randomness and less special cases.
My conclusion is that you seem to be correct, so if you are to remove things at a random position ArrayList is better than LinkedList.
If to have numbers then ArrayList seems to be in my tests about 10% faster than LinkedList at least when removing 500-30,000 objects in a 100,000 size list.
I’d also suggest that using a copying sweep would be the fastest method still. That is, as you iterate the arraylist, copy the elements into a new arraylist that are still “live”, and then switch to that arraylist, like a double-buffer. This should make absolutely the best use of caches.
I’ve only ever used this method for particle effects where there are hundreds or thousands of them created and deleted each frame. It’s cheaper to pull ones already allocated off a queue than it is to deallocate them and reallocate new ones every frame.
Actually Apple’s UIListView does this as well. This is their UI element when you are scrolling through a very long list of elements (like the address book), it only ends up allocating a few and changes their contents as you scroll through them. This however is because you only have a few on screen at once (like 10 maybe) so it doesn’t make sense to allocate 200 of them. But you don’t face that issue at all, really, and enemies on screen are not nearly as predictable as a list view.
