Optimize search in list (Kotlin/Android)

Question

Android, Kotlin 1.2. I have code like

data class Item(val id:Int,val field1:String, val field3:Array<String>,val field2:String)
val items:List<Item> = ....
var str:String='string_to_search'

I need to filter items list by str so I get sublist which contains onyly items in which str is case-insensitive substring of either field1 or field2 or both (it doesn't matter which one was matched or exact offset). Right now I use code like this:

 filteredItems=items
                        .filter { filtertFunc(it,filter) }

 ...
 fun filtertFunc(item: Item, filter:String):Boolean {

        if (item.field1.contains(filter, ignoreCase = true)) {
            return true
        }
        if (item.field2.contains(filter, ignoreCase = true)) {
            return true
        }
       return false
   }

list of items usually contains 2-3k items. field1 and field2 are usually 30-300 usually. Search string is 0-50 chars. Search string changes several times per second (usually new chars added - so abc changes to abcd ). List of items changes rarely.

My code have performance on some devices (filter took several seconds which is bad).

I can't use .parallelStream (I need to support Android 5.x but devices have usually at least 2 cores).

Using parallel map (from Parallel operations on Kotlin collections?) + special flag field in Item + filter does not help too much.

I thought about adding hash map with artificial keys (field1+field3) (or sorting list and using binarySearch) but this wont help because search string is not necessarily occurs at start of field1/field3.

How to better solve this performance issue? Any (sane) amount of pre-processing on list is ok.

If you are using Kotlin, you could use couroutines to paralelize your search i.e. using divide&conquer strategy. Spin up several coroutines, divide input list equally between them and run search on all sublists simultaneously. Then synchronize results. Fairly easy to achieve using async/await: https://kotlinlang.org/docs/reference/coroutines.html — pawelo, Apr 05 '18 at 13:34
"parallel map" link I mentioned is basically 'let's implement map using coroutines'. This helps a little. But only a little. Database.. may be an option but it will involve disk i/o and do this several times per second on device with possible slow flash memory is not a good idea. — Tauri, Apr 05 '18 at 14:39

score 1 · Accepted Answer · answered Apr 05 '18 at 14:06

Search string changes several times per second (usually new chars added - so abc changes to abcd ). List of items changes rarely.

You may filter the result of previous filtration after the search string growing. If search string reduced you may return to previous result.

Optimize search in list (Kotlin/Android)

1 Answers1