The best way to store and access 120,000 words in java

Question

I'm programming a java application that reads strictly text files (.txt). These files can contain upwards of 120,000 words.

The application needs to store all +120,000 words. It needs to name them word_1, word_2, etc. And it also needs to access these words to perform various methods on them.

The methods all have to do with Strings. For instance, a method will be called to say how many letters are in word_80. Another method will be called to say what specific letters are in word_2200.

In addition, some methods will compare two words. For instance, a method will be called to compare word_80 with word_2200 and needs to return which has more letters. Another method will be called to compare word_80 with word_2200 and needs to return what specific letters both words share.

My question is: Since I'm working almost exclusively with Strings, is it best to store these words in one large ArrayList? Several small ArrayLists? Or should I be using one of the many other storage possibilities, like Vectors, HashSets, LinkedLists?

My two primary concerns are 1.) access speed, and 2.) having the greatest possible number of pre-built methods at my disposal.

Thank you for your help in advance!!

---

Wow! Thanks everybody for providing such a quick response to my question. All your suggestions have helped me immensely. I’m thinking through and considering all the options provided in your feedback.

Please forgive me for any fuzziness; and let me address your questions:

1. Q) English?
   A) The text files are actually books written in English. The occurrence of a word in a second language would be rare – but not impossible. I’d put the percentage of non-English words in the text files at .0001%

2. Q) Homework?
   A) I’m smilingly looking at my question’s wording now. Yes, it does resemble a school assignment. But no, it’s not homework.

3. Q) Duplicates?
   A) Yes. And probably every five or so words, considering conjunctions, articles, etc.

4. Q) Access?
   A) Both random and sequential. It’s certainly possible a method will locate a word at random. It’s equally possible a method will want to look for a matching word between word_1 and word_120000 sequentially. Which leads to the last question…

5. Q) Iterate over the whole list?
   A) Yes.

Also, I plan on growing this program to perform many other methods on the words. I apologize again for my fuzziness. (Details do make a world of difference, do they not?)

Cheers!

Answer 1

I would store them in one large ArrayList and worry about (possibly unnecessary) optimisations later on.

Being inherently lazy, I don't think it's a good idea to optimise unless there's a demonstrated need. Otherwise, you're just wasting effort that could be better spent elsewhere.

In fact, if you can set an upper bound to your word count and you don't need any of the fancy List operations, I'd opt for a normal (native) array of string objects with an integer holding the actual number. This is likely to be faster than a class-based approach.

This gives you the greatest speed in accessing the individual elements whilst still retaining the ability to do all that wonderful string manipulation.

Note I haven't benchmarked native arrays against ArrayLists. They may be just as fast as native arrays, so you should check this yourself if you have less blind faith in my abilities than I do :-).

If they do turn out to be just as fast (or even close), the added benefits (expandability, for one) may be enough to justify their use.

Answer 2

Just confirming pax assumptions, with a very naive benchmark

public static void main(String[] args)
{
    int size = 120000;
    String[] arr = new String[size];
    ArrayList al = new ArrayList(size);
    for (int i = 0; i < size; i++)
    {
        String put = Integer.toHexString(i).toString();
        // System.out.print(put + " ");
        al.add(put);
        arr[i] = put;
    }

    Random rand = new Random();
    Date start = new Date();
    for (int i = 0; i < 10000000; i++)
    {
        int get = rand.nextInt(size);
        String fetch = arr[get];

    }
    Date end = new Date();
    long diff = end.getTime() - start.getTime();
    System.out.println("array access took " + diff + " ms");

    start = new Date();
    for (int i = 0; i < 10000000; i++)
    {
        int get = rand.nextInt(size);
        String fetch = (String) al.get(get);

    }
    end = new Date();
    diff = end.getTime() - start.getTime();
    System.out.println("array list access took " + diff + " ms");
}

and the output:
array access took 578 ms
array list access took 907 ms

running it a few times the actual times seem to vary some, but generally array access is between 200 and 400 ms faster, over 10,000,000 iterations.

Answer 3

If you will access these Strings sequentially, the LinkedList would be the best choice.

For random access, ArrayLists have a nice memory usage/access speed tradeof.