使用大数组列表加速自动完成算法 [英] 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是BIG(包含近40万个单词).因此，我在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).

我很确定这是由我的单词表的长度引起的，因为减少单词的数量，一切都像黄油一样光滑.

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

这是适配器类中的过滤代码:

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

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