Efficiently filter an ArrayList in Java/Android

Question

Hi, I'm developing an Android app (Android 1.6), but this is probably a more general Java question.

I have an ArrayList of about 10,000 objects

the objects contain 3 strings (firstName, middleName, lastName).

The user is presented with a "search box" on android where they can search for a particular "object" by typing in part of the name.

I have a class (which I call Filterer) that searches through the list of 10,000 for matching objects and then returns them as a "sublist".

The search is a little bit SLOW (especially on an Android handset) and I'm sure I'm not doing the search/filtering in the most efficient manner possible.

Does anyone have any suggestions on how to speed up my search? My code is below. One possibility to to search against a secondary "masterList" that already has every piece of information in lowercase and concatenated…but there may be additional ways to improve this search that would also help.

TIA!!

public void filterNames() {
  this.filteredList.clear();
  String sv = this.searchString.toString.trim().toLowerCase(); // search value
  for (int i = 0; i < this.masterList.size(); i++) {
    MyObject d = this.masterList.get(i);
    String fn = d.getFirstName().toString().toLowerCase();
    String mn = d.getMiddleName().toString().toLowerCase();
    String ln = d.getLastName().toString().toLowerCase();

    if (fn.indexOf(sv) >= 0 || md.indexOf(sv) >= 0 || ln.indexOf(sv) >= 0) this.currentList.add(d);
  }
}

Answer 1

Maybe you can trade some space for some speed? Create some form of an index for your data?

For example:

1. Create a list for each character (a-z) with all "MyObject"s where a part of the name contains the character (be aware of special characters!). For each entry count the number of "MyObject"s
2. If a user type in an query, look for the individual characters and only search the list with the smallest amount of entries.

Of course the addition of an name would require you to add it to the index.

Answer 2

After researching a bit more I have found that Suffix Arrays could get you the fasted answers. Also have a look at the Wikipedia entry for Suffix Trees for a bit more of an in depth explanation.
Besdies that I agree with the answer above that you could probably use an SQL Database for such queries. Doing an Sql Query against the data is probably one of the fastest ways to get what you want without suffix arrays.
One thing to speed things up a little without doing SQL would be to put firstName, middleName, lastName into one lowercase string, and put that into a new Map that is referencing the Array index. That way you can reduce search to just 10.000 strings of the hashmap without having to do a lowercase every time. It might be a bit faster but of course require more memory. Maybe try to do something with regular expressions to speed up the matching.
Another option would be to really create a searchindex with something like Lucene even though I think that would be really overkill on an Android device but could work in plain Java and infix search in Lucene isn't super high performance either.

Answer 3

How are you initially retrieving the 10,000+ list? If you're just using an instance of SQLite, I would really, strongly recommend you do this in SQL.

Answer 4

Did you find a working solution?