CODEWITHSUNDEEP
javaarrayslistperformance
user498001
user498001

Reputation: 244

Java List vs Array[]. Previous threads say to use Lists, I'm not convinced.

I've read some previous posts on the matter. The arguments are that lists are easier to use, more flexible.

All of my previous experience has showed me that flexibility comes as a cost.

The program I am designing makes heavy use of lists. I have maps to lists of lists that are compared, and appended, and searched (oh my!).

Its easy to append two lists. listA.appendAll(listB).

Its almost as easy to append two arrays. Simply create an new array the size of both and copy them.

Now, when these operations are being done in order of tens of thousands, my gut is telling me that Arrays will be a considerably better choice. Of course, I'd much rather use a list, but not at the expense of a performance hit

Is my gut instinct correct, or are lists truly as efficient as arrays? I understand how ArrayLists double in capacity to make appending average ~O(N), but I need the most efficient choice for my usage.

Upvotes: 3

Views: 137

Answers (3)

James Dunn
James Dunn

Reputation: 8264

Is my gut instinct correct, or are lists truly as efficient as arrays?
Neither. Lists are not "truly" as efficient as Arrays (although ArrayLists are close), but this doesn't mean that any optimization necessarily outweighs the flexibility benefits, even if you have thousands of operations going on.

Consider these questions:

  • Does this application need to be really, really fast?
  • Is the part of the code using either Arrays or Lists never going to be further developed?

If the answer to both of these questions is yes, then use Arrays. Otherwise, use Lists.

But since the performance between Arrays and Lists (particularly the ArrayList implementation) isn't that much, and since your code is highly likely to be developed further...
...just use Lists.

Upvotes: 2

user2033671
user2033671

Reputation:

ArrayList is backed by an array so without testing I feel that they are probably close in efficiency. If you know the size of your arrays just construct ArrayList with an initial size to reduce the overhead of increasing the size.

  public ArrayList(int initialCapacity) {
     super();
     if (initialCapacity < 0)
         throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
     this.elementData = new Object[initialCapacity];
 }

ArrayList.addAll ArrayList implementation already looks like something you would probably come up with

    public boolean addAll(Collection<? extends E> c) {
     Object[] a = c.toArray();
     int numNew = a.length;
     ensureCapacity(size + numNew);  // Increments modCount
     System.arraycopy(a, 0, elementData, size, numNew);
     size += numNew;
     return numNew != 0;
 }

odd are if you make the array yourself you will probably end up making a helper methods to do most of the stuff that ArrayList has already implemented. Don't reinvent the wheel

Upvotes: 1

Aaron Digulla
Aaron Digulla

Reputation: 328556

Your gut instinct is almost always wrong (if you knew for sure, you wouldn't need to listen to your guts and if you don't know, your decision is mostly random).

The question today isn't how efficient lists are, the question is: How much memory do you have to spare and how much time can you allocate to hunt for bugs in your optimized (but sadly slightly broken) code?

Millions of people are using ArrayList, it's a safe, proven, fast and reliable technology. Appending two of them is almost as fast as doing it manually with two native arrays but a) it's only a single line of code for me, b) it covers all the corner cases and c) if it should really be too slow, I can have my profiler find the few places where it's too slow and fix those (instead of making my life miserable in a thousand places where 999 don't matter much).

In addition to that, since ArrayList is such a heavy used type, the Java compilers and JIT have been optimized to death to make them fast. So even when it looks like it was more code, it might be actually faster than anything you can write manually because the JIT won't recognize your code and optimize it as aggressively.

Lastly, you can easily write your own ArrayList to use a more efficient allocation algorithm. If you write your code using the List interface everywhere, you can end up with something that you need to optimize in a single place only to make it faster everywhere.

Or maybe use a new Array interface with the 2-3 operations that you need. That way, you could easily create 2-3 implementations which different optimization goals and use them accordingly.

From my experience, the worst solution is to sprinkle your code with 4-10 line chunks of native array operations (like the four lines you need to append two arrays). At least move such code in a common helper class and make sure you cover all the corner cases with unit tests.

Upvotes: 8

Related Questions