3
\$\begingroup\$

I have built a search function that will compare strings regardless of punctuation and whitespace. It is case insensitive.

Here is my current function:

var itemsToFilter = MPMediaQuery.songs().items!

func searchForItemsWithString(_ searchText: String) {
    if searchText != "" {
            let filteredItems = itemsToFilter.filter { item in
                let filterStr = item.title

                if filterStr == nil {
                    return false
                }

                let punctuation = CharacterSet.punctuationCharacters
                let whitespace = CharacterSet.whitespaces
                let unwanted = punctuation.union(whitespace)
                let filterStringContainsSearchText = filterStr!.components(separatedBy: unwanted).joined(separator: " ")

                return filterStringContainsSearchText.contains(searchText)
            }

    }
}

This works, but it is very slow. How can I optimise it?

What else can I improve?

\$\endgroup\$
8
  • 1
    \$\begingroup\$ Can you provide an example of what you are trying to accomplish? it's hard to extract that from your code alone \$\endgroup\$ Aug 29, 2017 at 14:03
  • \$\begingroup\$ I agree with @CodeDifferent. In addition, are you using unit tests in order to check performances? \$\endgroup\$
    – Lorenzo B
    Aug 29, 2017 at 14:41
  • \$\begingroup\$ How big are your strings? It might be faster to take, say, first 10 non-punctuation non-whitespace characters, lowercase them and compare these small pieces. Only if they are the same - go the full route. \$\endgroup\$ Aug 29, 2017 at 14:43
  • \$\begingroup\$ I updated the code. I hope this clarifies it. @LorenzoB I am not using unit tests, this was checking by eye where the old function just used .contains(searchText). \$\endgroup\$
    – evenwerk
    Aug 29, 2017 at 15:14
  • 1
    \$\begingroup\$ If list of songs doesn't change much, you'd be better off with a prefix tree - or, better yet, derived from that hash tree with purged lowercased names as hashes and songs as values. Now, the fuzzy search would be an interesting problem... \$\endgroup\$ Aug 29, 2017 at 20:07

2 Answers 2

2
\$\begingroup\$

You might want to create a combined CharacterSet of punctuation and whitespace first and then apply this set using a single operation. This should speed things up. Please have a look at this code snippet:

let punctuation = CharacterSet.punctuationCharacters
let whitespace = CharacterSet.whitespaces
let unwanted = punctuation.union(whitespace)
let components = filterString.components(separatedBy: unwanted).joined(" ")
let filterStringContainsSearchText = components.contains(searchText)
\$\endgroup\$
1
  • \$\begingroup\$ The performance doesn't seem to be improved. I also modified your code a bit to added the missing functions such as the joined function with spaces and the contains function. \$\endgroup\$
    – evenwerk
    Aug 29, 2017 at 14:04
1
\$\begingroup\$

Optimizing your search will require that you don't repeat costly operations on every item if they can be performed once beforehand.

It would also help to avoid the overhead of special character processing if the search text doesn't justify it (e.g if it has no spaces or special characters itself).

Finally, procedural code (for loops) are optimized more efficiently by the compiler than their "functional" equivalent (.filter / .map) so the traversal of songs should be performed in a loop instead of a .filter()

I would suggest extending the MPMediaQuery class to allow it to provide a filtered list of songs in the most optimal way possible. This has some reuse value and will keep your main logic more readable and maintainable.

On the other hand, if the MPMediaQuery goes back to storage every time, it will be more efficient to create a simple function that takes the array of songs as a parameter.

For example:

extension MPMediaQuery
{
   static func songsMatching(_ searchText:String) -> [MPMediaItem]
   {
      // Common function to turn special characters into spaces
      // will have a certain amount of overhead so we will try
      // to avoid using it if possible...
      func normalizedText(_ text:String) -> String
      {
         let chars = text.unicodeScalars.enumerated()
                         .map ({ 
                                   CharacterSet.punctuationCharacters.contains($1)
                                || CharacterSet.whitespaces.contains($1) 
                                   ? " " : Character($1)
                              })
         return String(chars)
      }

      // Search string should only be prepared once
      // This means that the whole filtering operation needs to be
      // included in the optimization.
      let searchString  = searchText.lowercased()      
      let cleanedString = normalizedText(searchString)

      // based on search string content, we can forgo complex comparisons
      // We only need to manage special characters if the search text
      // contains any.
      // If the search text doesn't contain spaces or special characters
      // then removing them from the titles is unnecessary
      let simpleFilter = !cleanedString.contains(" ")

      // The Swift optimizer is much more efficient compiling procedural
      // code (As opposed to the functional style .filter{} and such)
      // This can give a 20x speed boost in some cases.
      var result:[MPMediaItem] = []
      for song in songs().items ?? []
      {
         guard let title = song.title?.lowercased()
         else { continue }

         if simpleFilter
         { 
            if title.contains(searchString)
            { result.append(song) }
         }
         else
         {
            if normalizedText(title).contains(searchString)
            { result.append(song) }
         }
      }

      return result
  }    
}
\$\endgroup\$
4
  • \$\begingroup\$ In your map function, you replace special characters with spaces ? " " : Character($1), How can I remove these characters? replacing " " with "" doesn't work. \$\endgroup\$
    – evenwerk
    Oct 30, 2017 at 15:10
  • 1
    \$\begingroup\$ you could add .replacingOccurrences(of:" ", with:"") at the end of the return String(chars) statement. but that would also remove "normal" spaces. If that's not what you want, replace special characters with " * " in the .map(...) and then .replacingOccurrences(of:" * ", with:"") instead. \$\endgroup\$
    – Alain T.
    Oct 31, 2017 at 3:29
  • \$\begingroup\$ If there are accents, I want to convert these to regular letters. I tried this in the map function CharacterSet.decomposables.contains($1). What would be the best way to that? \$\endgroup\$
    – evenwerk
    Oct 31, 2017 at 11:46
  • 1
    \$\begingroup\$ You can do it directly on the string using let text = text.applyingTransform(.stripDiacritics, reverse:false) ?? text \$\endgroup\$
    – Alain T.
    Oct 31, 2017 at 23:36

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.