How to best search a list of string in java using String.contains?

Question

Right now I'm working on an android application using voice recog. Basically, I'm wondering what the best search method is once I get String from voice recognition. I'm currently using a linear search on the list of packagename, using the following to get that list:

    pkgNames = new ArrayList<String>();
    pkgAppsList = (ArrayList<ApplicationInfo>) getPackageManager()
            .getInstalledApplications(PackageManager.GET_META_DATA);

    // List available packages on phone.
    for (ApplicationInfo appInfo : pkgAppsList) {

        if (!isSystemPackage(appInfo))
            pkgNames.add(appInfo.packageName);
    }

I've decide that it's probably better to use the ApplicationInfo list(pkgAppsList) and do a a search on that, but is there a faster way of searching that list than just a simple linear search and using the result to open the Application with an Intent. Right now, all I can think of doing is:

    for(ApplicationInfo ai: pkgAppsList){
        if((ai.name).contains(voice_recog_result))
           //open Launch Intent for ai.packageName
    }

Is there a way faster search method I can use with the contains method or a way I can do this without the contains method?

Unless you have tens of thousands of installed applications, that will be fast enough, I would think. Calculating the list of installed applications is probably the slowest part, you may want to do that just once on startup and cache the list. — Thilo, Nov 07 '11 at 04:13
Hmm I guess you're right, I just figured if I wanted to include system applications I might want do something faster than this. And good call on caching, but what would you suggest if they installed something while the up is in use ? — Zurno, Nov 07 '11 at 04:19
@Sam_k Maybe you could be more specific, but If i understand what you mean, I'm not really searching from strings as in text input, but the voice recognition conversion is a string list. — Zurno, Nov 07 '11 at 04:22
I have to say i dont really understand what your tring to do... but what about using a HashMap with appInfo.packageName as key? retreaving information from HashMap happens in O(1). and it doesnt seem like you can have more than one package with the same name. — Gleeb, Nov 07 '11 at 05:20
I would go with Thilo's suggestion and not worry about the cost of the linear search for a relatively limited amount of apps. If you really need to keep track of newly installed packages (and then removed ones as well, I presume), you can register your app to receive the PACKAGE_ADDED and PACKAGE_REMOVED intent actions and update the cached list. [See here for an example](http://developer.android.com/resources/faq/framework.html#7) on how to do that. — MH., Nov 07 '11 at 06:25

score 0 · Answer 1 · edited May 23 '17 at 11:48

For small numbers of searched strings (application names), the simplest method (traversing a linked list) should be chosen.

Auto-growing hash tables are often used for similar tasks, but only if the set of searched strings is often large. The worst case performance of a hash table is the same as traversing a linked list (due to auto-growing, and due to the potential of mass hash value collisions), and it has non-negligible overhead. It is therefore not a great choice for "just in case" insurance against a longer set of strings.

The data structure that is theoretically fitted to this task is called trie. Tries are not part of JCL or Android libraries, but available implementations are available. The worst case performance of a trie is proportional to the length of the longest string, regardless of the number of strings. Tries however tend to take a lot of memory which makes them unsuitable for mobile environments.

How to best search a list of string in java using String.contains?

1 Answers1