How to filter large array in iOS swift 2 for uisearchbar

Question

I am having a UISearchBar with more than 80000 elements in an array and I have to filter this array according to the user input.

But while typing in search view its working very slow means its taking too much time for typing values in keyboard.

func searchBar(searchBar: UISearchBar, textDidChange searchText: String) {

    if searchText.characters.count == 0 {
        searchActive = false
    } else {
        searchActive = true;
        filtered.removeAllObjects()

        dispatch_to_background_queue {
            for sumber in self.data {
                let nameRange: NSRange = sumber.rangeOfString(searchText, options: [NSStringCompareOptions.AnchoredSearch,NSStringCompareOptions.CaseInsensitiveSearch])
                if nameRange.location != NSNotFound {
                    self.filtered.addObject(sumber)
                }
            }//end of for

            self.dispatch_to_main_queue {
                /* some code to be executed on the main queue */
                self.tableView.reloadData()
            }
        } //end of dispatch
    }
}

func dispatch_to_main_queue(block: dispatch_block_t?) {
    dispatch_async(dispatch_get_main_queue(), block!)
}

func dispatch_to_background_queue(block: dispatch_block_t?) {
    let q = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0)
    dispatch_async(q, block!)
}

Answer 1

I want to add a couple of thoughts.

You already seem to do async processing, which is great. It won't make the search faster, but the app keeps responsive. Consider making it stoppable. If the user types three letters, you will queue up three searches and will get the relevant results only after the last run finished. This could be done using some sort of a boolean stop flag that gets checked within the search. If a new search is started, kill the old one first.

Show partial results. The user won't be watching at thousands of cells at once, but only at the first 20 or so. Depending on the order of your input and output, this may be very easy to do and fast as hell.

Build on your previous search. Searching for "Ab" will only be successful if searching for "A" (or "b" for that matter if the search wasn't anchored) was successful at well. So if your last search was a substring from your current search, take the output array of your previous search as an input. Obviously, be careful with stopped searches here.

Check if performance is really as bad. Do you run with optimizations switched on? The debug mode might be considerable slower, but that wouldn't matter.

Where does the data come from? That's a rather huge amount of data to keep around in memory. If it's coming from a database, using database functions might be easier (and most words above still comply).

Still too slow? Index your data set. If you know upfront which elements contain "A", the number of needed searches could drop significantly. And you'd have the results for the first search already

As you're using anchored search, working on a sorted array could give a much better performance characteristic. Just find the first and last element of your search term with binary search and use that range. Maybe without even copying into a new array. This approach puts some workload upfront (maybe before the user even started typing). If your search data is within larger objects, some sort of index tables would do.

Answer 2

There are two approaches to combine here for the best result:

First, keep long-running operations off the main (UI) thread

You can dispatch the filtering to a background thread using dispatch_async, or even to a background thread after some delay using dispatch_after.

Second, don't filter the array immediately after every key press

It's a waste of time because usually the user will type several keys before waiting to see what pops up. You want to therefore delay the filtering operation, and only perform it after some small amount of time has passed since the last key press. This is called "debouncing".

Here's a neat way to do all of this in Swift:

func debounce(delay:NSTimeInterval, queue:dispatch_queue_t, action: (()->())) -> (()->()) {

    var lastFireTime:dispatch_time_t = 0
    let dispatchDelay = Int64(delay * Double(NSEC_PER_SEC))

    return {
        lastFireTime = dispatch_time(DISPATCH_TIME_NOW,0)
        dispatch_after(
            dispatch_time(
                DISPATCH_TIME_NOW,
                dispatchDelay
            ),
            queue) {
                let now = dispatch_time(DISPATCH_TIME_NOW,0)
                let when = dispatch_time(lastFireTime, dispatchDelay)
                if now >= when {
                    action()
                }
        }
    }
}

class ViewController {

    lazy var debouncedFilterArray : () -> () = debounce(0.3, queue: dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), action: self.filterArray)

    func filterArray() {
        // do filtering here, but don't call this function directly            
    }
}

The debounce function itself returns a function that when called will exhibit this "debouncing" behaviour, running no more often than the delay interval passed to it.

To use, simply call debouncedFilterArray(). It will in turn call filterArray, but always on a background thread and never more often than every 0.3 seconds.

Answer 3

80000! That is a lot of data indeed. One solution which could considerably speed things is to shrink the search array after each key stroke AND to cancel the search if many keystrokes are typed in a row while caching the search in case keystrokes are erased. You could combine it with appzYouLife's answer and you would already have a more solid framework. Here is an example of how that could work, the token is necessary so that you update the UI in accordance with the search:

var dataToSearch = [AnyObject]()
  var searchCache = NSCache()
  var currentSearchToken = 0

  func searchBar(searchBar: UISearchBar, textDidChange searchText: String) {
    performSearch(searchText, searchToken: ++currentSearchToken)
  }

  func performSearch(searchText: String, searchToken: Int) {

    if let searchResults = searchCache.objectForKey(searchText) as? [AnyObject] { //If the search is cached, we simply pull the results
      guard searchToken == currentSearchToken else {return} //Make sure we don't trigger unwanted UI updates
      performListUpdate(searchResults)
      return
    }

    var possiblePreviousSearch = searchText //We're going to see if we can build on any of previous searches

    while String(possiblePreviousSearch.characters.dropLast()).characters.count > 0 { //While we still have characters
      possiblePreviousSearch = String(possiblePreviousSearch.characters.dropLast()) //Drop the last character of the search string
      if let lastSearch = searchCache.objectForKey(possiblePreviousSearch) as? [AnyObject]{ //We found a previous list of results
        let queue = dispatch_get_global_queue(QOS_CLASS_USER_INITIATED, 0)

        dispatch_async(queue) {
          let newResults = lastSearch.filter {object in /**put your conditions here instead of return true*/ return true} //Sort on top of a previous search
          self.searchCache.setObject(newResults, forKey: searchText)
          guard searchToken == self.currentSearchToken else {return} //We don't want to trigger UI Updates for a previous search
          dispatch_async(dispatch_get_main_queue()) {
            self.performListUpdate(newResults)
            return
          }
        }
      }
    }

    //If we got to this point, we simply have to search through all the data
    let queue = dispatch_get_global_queue(QOS_CLASS_USER_INITIATED, 0)

    dispatch_async(queue) {
      let newResults = self.dataToSearch.filter {object in /**put your conditions here instead of return true*/ return true} //Sort on top of a previous search
      self.searchCache.setObject(newResults, forKey: searchText)
      guard searchToken == self.currentSearchToken else {return} //We don't want to trigger UI Updates for a previous search
      dispatch_async(dispatch_get_main_queue()) {
        self.performListUpdate(newResults)
        return
      }
    }
  } //end of perform search

Of course this answer isn't perfect. It assumes your lists can be sorted on top of smaller ones (for example the results of searching for "abc" will be a subset of the results of searching "ab" and "a").

EDIT Combine this with debouncing as shown in another answer and you have an ok performance!

Answer 4

You could perform the filtering on a background thread so to leave the main thread (which does manage the UI) responsive.

func filter(list:[String], keyword:String, completion: (filteredList:[String]) -> ()) {

    let queue = dispatch_get_global_queue(QOS_CLASS_USER_INITIATED, 0)

    dispatch_async(queue) {
        let filtered = list.filter { $0.containsString(keyword) }

        dispatch_async(dispatch_get_main_queue()) {
            completion(filteredList: filtered)
        }
    }
}

Example

let data = ["dog", "cat", "eagle"]
filtered(data, keyword: "do") { (filteredList) -> () in
    // update the UI here
}