I have to keep thousands of strings in memory to be accessed serially in Java. Should I store them in an array or should I use some kind of List ?
Since arrays keep all the data in a contiguous chunk of memory (unlike Lists), would the use of an array to store thousands of strings cause problems ?
Answer: The common consensus is that the performance difference is minor. List interface provides more flexibility.
If you know in advance how large the data is then an array will be faster.
A List is more flexible. You can use an ArrayList which is backed by an array.
No, because technically, the array only stores the reference to the strings. The strings themselves are allocated in a different location. For a thousand items, I would say a list would be better, it is slower, but it offers more flexibility and it's easier to use, especially if you are going to resize them.
list is slower than arrays.If you need efficiency use arrays.If you need flexibility use list.
I suggest that you use a profiler to test which is faster.
My personal opinion is that you should use Lists.
I work on a large codebase and a previous group of developers used arrays everywhere. It made the code very inflexible. After changing large chunks of it to Lists we noticed no difference in speed.
The Java way is that you should consider what data abstraction most suits your needs. Remember that in Java a List is an abstract, not a concrete data type. You should declare the strings as a List, and then initialize it using the ArrayList implementation.
List<String> strings = new ArrayList<String>();
This separation of Abstract Data Type and specific implementation is one the key aspects of object oriented programming.
An ArrayList implements the List Abstract Data Type using an array as its underlying implementation. Access speed is virtually identical to an array, with the additional advantages of being able to add and subtract elements to a List (although this is an O(n) operation with an ArrayList) and that if you decide to change the underlying implementation later on you can. For example, if you realize you need synchronized access, you can change the implementation to a Vector without rewriting all your code.
In fact, the ArrayList was specifically designed to replace the low-level array construct in most contexts. If Java was being designed today, it's entirely possible that arrays would have been left out altogether in favor of the ArrayList construct.
Since arrays keep all the data in a contiguous chunk of memory (unlike Lists), would the use of an array to store thousands of strings cause problems ?
In Java, all collections store only references to objects, not the objects themselves. Both arrays and ArrayList will store a few thousand references in a contiguous array, so they are essentially identical. You can consider that a contiguous block of a few thousand 32-bit references will always be readily available on modern hardware. This does not guarantee that you will not run out of memory altogether, of course, just that the contiguous block of memory requirement is not difficult to fufil.
You should prefer generic types over arrays. As mentioned by others, arrays are inflexible and do not have the expressive power of generic types. (They do however support runtime typechecking, but that mixes badly with generic types.)
But, as always, when optimizing you should always follow these steps:
Don't get into the trap of optimizing without proper benchmarking. As others have suggested use a profiler before making any assumption.
The different data structures that you have enumerated have different purposes. A list is very efficient at inserting elements in the beginning and at the end but suffers a lot when accessing random elements. An array has fixed storage but provides fast random access. Finally an ArrayList improves the interface to an array by allowing it to grow. Normally the data structure to be used should be dictated by how the data stored will be access or added.
About memory consumption. You seem to be mixing some things. An array will only give you a continuous chunk of memory for the type of data that you have. Don't forget that java has a fixed data types: boolean, char, int, long, float and Object (this include all objects, even an array is an Object). It means that if you declare an array of String strings [1000] or MyObject myObjects [1000] you only get a 1000 memory boxes big enough to store the location (references or pointers) of the objects. You don't get a 1000 memory boxes big enough to fit the size of the objects. Don't forget that your objects are first created with "new". This is when the memory allocation is done and later a reference (their memory address) is stored in the array. The object doesn't get copied into the array only it's reference.
"Thousands" is not a large number. If all you want to do is access these serially, use an in-memory, immutable, singly-linked List.
I don't think it makes a real difference for Strings. What is contiguous in an array of strings is the references to the strings, the strings themselves are stored at random places in memory.
Arrays vs. Lists can make a difference for primitive types, not for objects. IF you know in advance the number of elements, and don't need flexibility, an array of millions of integers or doubles will be more efficient in memory and marginally in speed than a list, because indeed they will be stored contiguously and accessed instantly. That's why Java still uses arrays of chars for strings, arrays of ints for image data, etc.
Remember that an ArrayList encapsulates an array, so there is little difference compared to using a primitive array (except for the fact that a List is much easier to work with in java).
The pretty much the only time it makes sense to prefer an array to an ArrayList is when you are storing primitives, i.e. byte, int, etc and you need the particular space-efficiency you get by using primitive arrays.
I'm guessing the original poster is coming from a C++/STL background which is causing some confusion. In C++ std::list is a doubly linked list.
In Java [java.util.]List is an implementation-free interface (pure abstract class in C++ terms). List can be a doubly linked list - java.util.LinkedList is provided. However, 99 times out of 100 when you want a new List, you want to use java.util.ArrayList instead, which is the rough equivalent of C++ std::vector. There are other standard implementations, such as those returns by java.util.Collections.emptyList and java.util.Arrays.asList.
From a performance stand point there is a very small hit from having to go through an interface and an extra object, however runtime inlining means this rarely has an significance. Also remember that String are (typically) an object plus array. So for each entry, you probably have two other objects. In C++ std::vector<std::string>, although copying by value without a pointer as such, the character arrays will form an object for string (and these will not usually be shared).
If this particular code is really performance sensitive, you could create a single char[] array (or even byte[]) for all the characters of all the strings, and then an array of offsets. IIRC, this is how javac is implemented.
Well firstly it's worth clarifying do you mean "list" in the classical comp sci data structures sense (ie a linked list) or do you mean java.util.List? If you mean a java.util.List, it's an interface. If you want to use an array just use the ArrayList implementation and you'll get array-like behaviour and semantics. Problem solved.
If you mean an array vs a linked list, it's a slightly different argument for which we go back to Big O (here is a plain English explanation if this is an unfamiliar term.
Array;
Linked List:
So you choose whichever one best suits how you resize your array. If you resize, insert and delete a lot then maybe a linked list is a better choice. Same goes for if random access is rare. You mention serial access. If you're mainly doing serial access with very little modification then it probably doesn't matter which you choose.
Linked lists have a slightly higher overhead since, like you say, you're dealing with potentially non-contiguous blocks of memory and (effectively) pointers to the next element. That's probably not an important factor unless you're dealing with millions of entries however.
Array vs. List choice is not so important (considering performance) in the case of storing string objects. Because both array and list will store string object references, not the actual objects.
I wrote a little benchmark to compare ArrayLists with Arrays. On my old-ish laptop, the time to traverse through a 5000-element arraylist, 1000 times, was about 10 milliseconds slower than the equivalent array code.
So, if you're doing nothing but iterating the list, and you're doing it a lot, then maybe it's worth the optimisation. Otherwise I'd use the List, because it'll make it easier when you do need to optimise the code.
n.b. I did notice that using for String s: stringsList was about 50% slower than using an old-style for-loop to access the list. Go figure... Here's the two functions I timed; the array and list were filled with 5000 random (different) strings.
private static void readArray(String[] strings) {
long totalchars = 0;
for (int j = 0; j < ITERATIONS; j++) {
totalchars = 0;
for (int i = 0; i < strings.length; i++) {
totalchars += strings[i].length();
}
}
}
private static void readArrayList(List<String> stringsList) {
long totalchars = 0;
for (int j = 0; j < ITERATIONS; j++) {
totalchars = 0;
for (int i = 0; i < stringsList.size(); i++) {
totalchars += stringsList.get(i).length();
}
}
}
If you have thousands, consider using a trie. A trie is a tree-like structure that merges the common prefixes of the stored string.
For example, if the strings were
intern
international
internationalize
internet
internets
The trie would store:
intern
-> \0
international
-> \0
-> ize\0
net
->\0
->s\0
The strings requires 57 characters (including the null terminator, '\0') for storage, plus whatever the size of the String object that holds them. (In truth, we should probably round all sizes up to multiples of 16, but...) Call it 57 + 5 = 62 bytes, roughly.
The trie requires 29 (including the null terminator, '\0') for storage, plus sizeof the trie nodes, which are a ref to an array and a list of child trie nodes.
For this example, that probably comes out about the same; for thousands, it probably comes out less as long as you do have common prefixes.
Now, when using the trie in other code, you'll have to convert to String, probably using a StringBuffer as an intermediary. If many of the strings are in use at once as Strings, outside the trie, it's a loss.
But if you're only using a few at the time -- say, to look up things in a dictionary -- the trie can save you a lot of space. Definitely less space than storing them in a HashSet.
You say you're accessing them "serially" -- if that means sequentially an alphabetically, the trie also obviously gives you alphabetical order for free, if you iterate it depth-first.
Depending on the implementation. it's possible that an array of primitive types will be smaller and more efficient than ArrayList. This is because the array will store the values directly in a contiguous block of memory, while the simplest ArrayList implementation will store pointers to each value. On a 64-bit platform especially, this can make a huge difference.
Of course, it's possible for the jvm implementation to have a special case for this situation, in which case the performance will be the same.