How do I optimize tens of thousands of substring searches in instance attributes in Python?
Question: I'm trying to write a program which autocompletes user input which may be one
of the following: an airport's three letter IATA code, a city's name, a city's
name in one of given languages, an airport's name, a country's name, a state's
name.

The airport data is all located in instances of an `Airport` class, which has
the `.match()` method, determining if any of the relevant attributes starts
with the user's input.

Here's all relevant code:

    
    
    class Location(object):
        def __init__(self, code, location_type):
            self.code = code  # Country/city/state/airport codes. Format varies.
            self.type = location_type
            self.name = self.get_name()  # String containing name of location.
            if self.type == 'city':
                self.localizations = self.get_localizations()
                # The above is a dictionary, keys are locales (ex. 'fr-FR'), values
                # are the translated city names in the specified locale.
    
        def match(self, pattern, match_code=False, locales=[]):
            if match_code:  # Fires if we only match for the 3 letter IATA code 
                return pattern.match(self.code)
    
            if not self.name:  # Some instances don't have names
                return None
    
            if locales and self.localizations:  # Fires if there's languages given
                for locale in locales:
                    match = pattern.match(self.localizations.get(locale, ''))
                    if match:
                        return locale
                return None
    
            return pattern.match(self.name)
    
    
    class Airport(Location):
        def __init__(self, airport, city=None, state=None, country=None):
            self.code = airport
            self.type = 'airport'
            self.name = self.get_name()
            self.city = Location(city, 'city')
            self.state = Location(state, 'state')
            self.country = Location(country, 'country')
    
    matches = []
    pattern = re.compile('^' + keyword, re.I)  # Keyword is the user's input
    for airport in airports:  # airports is a list of Airport instances
        if airport.match(pattern, match_code=True):
            matches.append(airport.create_match('airport', 100))
        elif (airport.city.match(pattern)
              or airport.city.match(pattern, locales=locales)):
            if airport.city.match(pattern):
                matches.append(airport.create_match('locality', 70))
            else:
                locale = airport.city.match(pattern, locales=locales)
                matches.append(airport.create_match('localised_locality', 70,
                                                    locale=locale))
        elif airport.match(pattern):
            matches.append(airport.create_match('airport', 50))
        elif airport.country.match(pattern):
            matches.append(airport.create_match('country', 30))
        elif airport.state.match(pattern):
            matches.append(airport.create_match('state', 30))
    

According to my testing, the `Airport.match()` method is what takes up
practically all the time. There's currently 9451 `Airport` instances, and a
search takes around 50ms on my PC.

My program is what creates all these instances at startup, loading them from
XML files, so I can make modifications to the source data, if necessary.


Answer: I think you’re going about this backwards. What do I mean by that? Well, it
seems to me that your list of things to match against is static (relatively),
while your user is going to be entering data one character at a time. What you
should probably do is put all of the things you might autocomplete to into a
sorted array, then every time the user types another character, find the first
item in the array that matches the prefix entered by the user.

You can optimise by remembering the last place you got to, so that e.g. if a
user types 'S', when you get the next character you start searching at the
first 'S' in your array; if they type 'SF', then you search starting at 'SF'
and so on.

### Update

Here’s an example, based on what you wrote above:

    
    
    import bisect
    
    # Construct the search array
    search_array = [(l.code.lower(), l) for l in locations] + [(l.name.lower(), l) for l in locations] + [(a.city.lower(), a) for a in airports] + [(a.state.lower(), a) for a in airports] + [(a.country.lower(), a) for a in airports]
    search_array.sort()
    
    # Now, assume the user enters 'S'; we do
    new_entry = bisect.bisect_left(search_array, ('S'.lower(), None))
    
    if new_entry < len(search_array):
      found = search_array[new_entry]
      if found[0].startswith('S'.lower()):
        entry = new_entry
        autocompletion = found[0]
    
    # Let's say they now enter 'F'; we do
    new_entry = bisect.bisect_left(search_array, ('SF'.lower(), None), entry)
    
    if new_entry < len(search_array):
      found = search_array[new_entry]
      if found[0].startswith('SF'.lower()):
        entry = new_entry
        autocompletion = found[0]
    

and so on. Obviously this is just knocked together in Stack Overflow as an
example.

