3
\$\begingroup\$

I want to optimize the below code, I have asked a similar question here. I know this approach is better than my last code but I feel there are ways to optimize this too.This code is used in almost every project and I am not satisfied with this answer. There are not even using last filter results and traversing whole list every time.

I have three points to ask in this question,

  1. Can I optimize HashMap memory by using ArrayMap? Should I use comma separated positions in String instead of Integer objects array or any way to use int primitive array?
  2. I am not getting any animation in this result, how to get that? (I am using notifyItemInserted still no animation)
  3. How much data should be kept in Hashmap, till 2 characters or it should be according to result list size?
I would be glad to know if anything can be done better in this code other than these points.

In below code, mList is used in onBindViewHolder method. copyList always contains all data(no insertion or deletion is done on that).

class MyFilter extends Filter {


        /**
         * 1. check do we have search results available (check map has this key)
         * 2. if available, remove all rows and add only those which are value for that key (string)
         * 3. else check do we have any key available starting like this, s=har, already available -ha then it can be reused
         *
         * @param constraint
         */
        @Override
        protected FilterResults performFiltering(CharSequence constraint) {
            //Here you have to implement filtering way
            final FilterResults results = new FilterResults();

            if (!mSearchMap.containsKey(constraint.toString())) {
                String supersetKey = getSupersetIfAvailable(mSearchMap, constraint.toString());
                if (supersetKey == null) {
                    List<Integer> foundPositions = doFullSearch(copyList, constraint.toString());
                    mSearchMap.put(constraint.toString(), foundPositions);
                } else {
                    List<Integer> foundPositions = filterFromSuperset(copyList, mSearchMap.get(supersetKey), constraint.toString());
                    mSearchMap.put(constraint.toString(), foundPositions);
                }
            }


            return results;
        }

        private String getSupersetIfAvailable(Map<String, List<Integer>> mSearchMap, String s) {
            Set<String> set = mSearchMap.keySet();
            List<String> list = new ArrayList<>(set);
            Collections.sort(list);
            Collections.reverse(list);
            for (String c : list) {
                if (s.startsWith(c.toString())) {
                    return c;
                }
            }
            return null;
        }
        private List<Integer> filterFromSuperset(List<WeekWorkBean> list, List<Integer> supersetResults, String s) {
            List<Integer> results = new ArrayList<>();
            String lowerS = s.toLowerCase();
            for (int i = 0; i < supersetResults.size(); i++) {
                if (list.get(supersetResults.get(i)).getEmpName().toLowerCase().startsWith(lowerS)) {
                    results.add(supersetResults.get(i));
                }
            }
            return results;
        }

        private List<Integer> doFullSearch(List<WeekWorkBean> list, String s) {
            List<Integer> results = new ArrayList<>();
            for (int i = 0; i < list.size(); i++) {
                if (list.get(i).getEmpName().toLowerCase().startsWith(s.toLowerCase())) {
                    results.add(i);
                }
            }
            return results;
        }

        @Override
        protected void publishResults(CharSequence constraint, FilterResults results) {
            // here you can use result - (f.e. set in in adapter list)
            mList.clear();
            notifyDataSetChanged();
            List<Integer> res = mSearchMap.get(constraint.toString());
            int j = 0;
            for (Integer i : res) {
                mList.add(copyList.get(i));
                notifyItemInserted(j++);
            }
        }
    }
\$\endgroup\$
3
  • \$\begingroup\$ Your last question still has an open bounty for 2 days. Are you sure you want to ask this now and not wait till after you've awarded a bounty and made the necessary changes to your code? \$\endgroup\$
    – Mast
    Nov 28, 2016 at 13:25
  • \$\begingroup\$ meta.codereview.stackexchange.com/questions/1763/… above link given by a moderator. He has reverted back my edit and suggested me to add new question. I want a good filter method nothing else. \$\endgroup\$ Nov 28, 2016 at 13:29
  • \$\begingroup\$ I have rolled back Rev 4 → 3. Please see What to do when someone answers. \$\endgroup\$ Dec 6, 2016 at 5:47

3 Answers 3

4
+100
\$\begingroup\$

Your main questions

  1. Can I optimize HashMap memory by using ArrayMap? Should I use comma separated positions in String instead of Integer objects array or any way to use int primitive array?

As the documentation explains, an ArrayMap may be more memory-efficient, at the expense of speed, and when using fewer than hundreds of items. As for the values, List<Integer> is natural and reasonable.

  1. I am not getting any animation in this result, how to get that? (I am using notifyItemInserted still no animation)

You haven't shared enough code to debug that, and in any case we review working code on Code Review. If you need debugging help, try Stack Overflow instead, and make sure to read their posting guidelines.

  1. How much data should be kept in Hashmap, till 2 characters or it should be according to result list size?

I don't understand this question.

Don't repeat yourself

In the performFiltering method there are several repeated elements:

  • constraint.toString() is used multiple times
  • There are two identical mSearchMap.put calls

Similarly, in doFullSearch you repeatedly call s.toLowerCase().

It would be better to avoid such duplications, by saving repeated values in local variables, or by extracting common code from conditional branches to before or after the conditional statement.

Performance

To avoid the repeated sorting and conversion from set to list in getSupersetIfAvailable, you could keep a sorted list of the keys of mSearchMap. That is, every time you insert or remove a value in mSearchMap, also insert or remove that value from the sorted list. You could use a TreeSet to accomplish this easily. And then you could pass that to getSupersetIfAvailable instead of mSearchMap.

Another optimization could be to replace the linear search for a prefix of s with binary search.

Use for-each loop

Instead of this:

for (int i = 0; i < supersetResults.size(); i++) {
    if (list.get(supersetResults.get(i)).getEmpName().toLowerCase().startsWith(lowerS))

{ results.add(supersetResults.get(i)); } }

It's recommended to use a for-each loop:

for (Integer result : supersetResults) {
    if (list.get(result).getEmpName().toLowerCase().startsWith(lowerS)) {
        results.add(result);
    }
}

Conventions

The Android convention is to use a prefix of m in field names, this naming should not be used for method parameters like mSearchMap here:

private String getSupersetIfAvailable(Map<String, List<Integer>> mSearchMap, String s) {

On the other hand, copyList seems to be a member, but it is not named accordingly. Use a consistent naming scheme, either prefix all fields with m or none of them.

\$\endgroup\$
2
  • \$\begingroup\$ Third point is, if user type harish then these 6 keys will be created "h", "ha", "har", "hari", "haris", "harish". As we know that the more characters a query contains, less results it gets. we can store results for "h" and "ha" and whenever we need results for "har", we can search from superset. it will save memory but processor is used everytime to get results for query length>2. How to use processor and memory in a efficient way. \$\endgroup\$ Dec 6, 2016 at 5:50
  • \$\begingroup\$ Second point, notifyItemInserted() is used to animate insertion of rows inside recyclerView. but I am not getting animation. \$\endgroup\$ Dec 6, 2016 at 5:51
2
\$\begingroup\$

As you haven't explained what the code is supposed to do I'm going to go out on a limb here and assume that it is a filter for a text box that will show suggestions/predictions for what you are about to type.

Better data structure

If that is the case then there is a data structure called a Trie (wikipedia) which is commonly used for this. By using a trie you will get faster performance and less memory usage than your current code.

You should check it out.

\$\endgroup\$
3
  • \$\begingroup\$ When screen loads, it shows all the rows in RecyclerView after that as you type it shows only those results which start from that String. \$\endgroup\$ Dec 6, 2016 at 9:43
  • 1
    \$\begingroup\$ So yes you need all strings that are prefix of the key, Trie is the way to go. \$\endgroup\$
    – Emily L.
    Dec 6, 2016 at 9:50
  • \$\begingroup\$ I mean you need all strings for which the search key is a prefix... \$\endgroup\$
    – Emily L.
    Dec 7, 2016 at 12:24
1
\$\begingroup\$
for (String c : list) {
    if (s.startsWith(c.toString())) {

You don't need to call toString on a String. You can just use it as is.

\$\endgroup\$
1
  • \$\begingroup\$ You are right, but if you see toString() method implementation it just return this. Still I appreciate your observation. It saves a method call. \$\endgroup\$ Dec 1, 2016 at 6:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.