I have a large list of strings that the user of the iPhone / Android application needs to look for. The rows are sorted alphabetically, but this is actually not so useful, since the string should be included in the results if the search query falls at any point within the string, and not just at the beginning. When a user enters his search query, the search must be updated to reflect the results of what they currently entered. (for example, if they type "cat", it should display the results for "c", "ca" and "cat" as they are entered).
My current approach is this:
I have a stack of "search results" that starts empty. If the user types something to increase the search query, I push the current search results onto the stack and then look only at the current search results for new ones (it is impossible for something to be in the full list of lines, but not in the current one) )
If the user is gaining back space, I only need to pull the search results from the stack and restore them. This can be done almost instantly.
This approach is great for "reverse" searches (making the query shorter) and for cases where the search query is already long enough so that the number of results is low. However, it still has to look for a complete list of strings in O (n) time for each of the first few letters that the user enters, which is pretty slow.
One approach that I reviewed is to have a precompiled list of results for all possible 2 or 3 letter search queries. The problem with this approach is that this will require 26 ^ 2 or 26 ^ 3 such lists and will take up quite a lot of space.
Any other optimizations or alternative approaches you can think of?
source
share