Efficiently filter an ArrayList in Java/Android

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) >开发者_C百科;= 0) {
      this.currentList.add(d);
    }
  }
}

---

Yes, it's certainly painful to lower-case several objects for each loop iteration (plus a possibly redundant toString?), and also bad practice to call list.size() for every iteration — that value should be cached before the loop starts.

Anyway, if you're working with this much data, is there a reason that you're not using an SQLite database for storage and displaying/filtering your list using CursorAdapter?

That would be the recommended way to implement something of this size.

---

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.

---

may be too late answer but it's help for other in stuck same problem.

Java 8 (2014) solves this problem using streams and lambdas in one line of code:

Using Stream Api you can filter data without for loop and more feature's are available.

List<MyObject> mFilteredMyObjectList = mMyObjectList.stream()
    .filter(d -> d.getFirstName().toString().toLowerCase().indexOf(sv) >= 0 
    || d.getMiddleName().toString().toLowerCase().indexOf(sv) >= 0 
    || d.getLastName().toString().toLowerCase().indexOf(sv) >= 0).collect(Collectors.toList());

For more info see below link,

Link1 Link2

---

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.

---

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.