Speeding up AutoComplete algorithm with a big Array List

Question

I'm dealing with the InstantSearch feature on my Android App and the result I'd like to achieve is the one in the following picture.

Everything works properly except for one thing. The ArrayList I'm using is BIG (it contains almost 400k words). Hence, I have performance issues while showing my results on the ListView (it lags a lot).

I'm pretty sure it's caused by the length of my Wordlist because, reducing its number of words, everything is smooth as butter.

Here's my filtering code in the Adapter Class:

private class SearchResultsFilter extends Filter {

    @Override
    protected FilterResults performFiltering(CharSequence constraint) {

        FilterResults filterResults = new FilterResults();

        ArrayList<String> found = new ArrayList<>();
        if (constraint != null) {
            for (String word : MainActivity.WordList) {
                if (word.startsWith(constraint.toString().toLowerCase())) {
                    found.add(word);
                }
            }
        }

        filteredList = found;
        filterResults.values = found;
        filterResults.count = found.size();

        return filterResults;
    }

    @Override
    protected void publishResults(CharSequence constraint, FilterResults filterResults) {
        if (filterResults.count > 0) {
            Log.println(Log.INFO, "Results", "FOUND");
            results.clear();
            results.addAll((ArrayList<String>) filterResults.values);
            notifyDataSetChanged();
        } else {
            Log.println(Log.INFO, "Results", "-");
            results.clear();
            notifyDataSetInvalidated();
        }

    }
}

That's how I load my ArrayList in my MainActivity:

public static void loadDictionary(Activity activity) {
        //loading wordslist from file.
        BufferedReader line_reader = new BufferedReader(new InputStreamReader(activity.getResources().openRawResource(R.raw.wordlist)));
        String line;
        try {
            while ((line = line_reader.readLine()) != null) {
                WordList.add(line);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        Collections.sort(WordList);

Thank you everyone,

Have a nice day.

do not show AutoComplete until someone types at least X letters ... play with X value to fit your needs — Selvin, Mar 01 '17 at 14:46
@Selvin Thank you for your answer. I don't think that this solution solves my issue, because my code still iterates through the whole list every time I type a letter. Instead, I'd like to know if I can use a different algorithm that reduces the amount of words to check each time. Perhaps it might be better use a different data structure? — Cesarsk, Mar 01 '17 at 16:24

score 1 · Accepted Answer · answered Mar 09 '17 at 14:26

I'm a collaborator in Cesarsk's project, I noticed that our problem was the performFiltering method. The Wordlist we used, had 394.000+ elements in it and the performFiltering method checked all of them each time the user typed a letter in the EditText of the SearchBar even if it should have excluded some on each iteration. So I implemented a simple way to split the list in different sublists. Each list contains only word starting with a single letter from the alphabet.

Meaning:

List 1 contains only words starting with the letter "a"
List 2 contains only words starting with the letter "b"

And so on...

Then I put all the lists in an HashMap with key = letter of the alphabet. Doing this, now We are able to select only the sublist matching the first letter the user typed, and the loop checks a lot less words, generating results instantly.

Here's some code:

@Override
    protected FilterResults performFiltering(CharSequence constraint) {

        FilterResults filterResults = new FilterResults();

        ArrayList<Pair<String, String>> temp_list = null;
        ArrayList<Pair<String, String>> found = new ArrayList<>();

        if (constraint != null) {
            if (!(constraint.toString().isEmpty())) {
                temp_list = MainActivity.Wordlists_Map.get(constraint.toString().substring(0,1).toLowerCase());

                if(temp_list != null){
                    for(Pair<String, String> element : temp_list){
                        if(element.first.startsWith(constraint.toString().toLowerCase())){
                            found.add(element);
                        }
                    }
                }
            }
        }

        filterResults.values = found;
        filterResults.count = found.size();

        return filterResults;
    }

Speeding up AutoComplete algorithm with a big Array List

1 Answers1

Linked