使用大数组列表加速 AutoComplete 算法 [英] Speeding up AutoComplete algorithm with a big Array List

问题描述

我正在处理我的 Android 应用上的 InstantSearch 功能，我想要实现的结果如下图所示.

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.

除了一件事外，一切正常.我使用的 ArrayList 很大(它包含近 400k 个字).因此，我在 ListView 上显示结果时遇到了性能问题(滞后很多).

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).

我很确定这是由于我的 Wordlist 的长度造成的，因为减少了它的字数，一切都像黄油一样光滑.

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();
        }

    }
}

这就是我在 MainActivity 中加载 ArrayList 的方式:

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);

谢谢大家，

祝你有美好的一天.

推荐答案

我是 Cesarsk 项目的合作者，我注意到我们的问题是 performFiltering 方法.我们使用的 Wordlist 中有 394.000 多个元素，并且每次用户在 SearchBar 的 EditText 中键入一个字母时，performFiltering 方法都会检查所有这些元素，即使它应该在每次迭代中排除一些.所以我实现了一个简单的方法来将列表拆分到不同的子列表中.每个列表仅包含以字母表中的单个字母开头的单词.

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.

含义:

• 列表 1 仅包含以字母a"开头的单词

• 列表 2 仅包含以字母b"开头的单词

• List 1 contains only words starting with the letter "a"

• List 2 contains only words starting with the letter "b"

等等...

然后我将所有列表放在一个 HashMap 中，key = 字母表中的字母.这样做，现在我们可以只选择与用户输入的第一个字母匹配的子列表，循环检查的单词少得多，立即生成结果.

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.

这是一些代码:

@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;
    }

这篇关于使用大数组列表加速 AutoComplete 算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！