title: What is the fastest way to filter list of strings in Python?
body: <p>I have a list of string (~400K) where the longest string has ~220 chars.
  the strings represented path to objects with "." as separator.</p>
  
  <p>I am trying to build an auto-complete feature that allows the user to quickly pick objects from a list instead of typing their full path.</p>
  
  <p>The auto-complete feature is based on filtering the database based on user input.</p>
  
  <p>I tried the following approaches.</p>
  
  <ol>
  <li><p>Using <code>filter</code> - benchmarked to ~0.8 seconds</p>
  
  <pre><code>database = list()
  database.append("path.to.first.object")
  database.append("path.to.first.some.object.of.mine")
  ....
  database.append("path.to.last.object") # ~430K items 
  
  partial_name = "som"
  filtered_list = list(filter(lambda x: partial_name in x, database))
  </code></pre></li>
  <li><p><code>regex</code> approach - benchmark to ~0.15 seconds</p>
  
  <pre><code>regex = re.compile(r"{0}".format(partial_name))
  filtered_list = list(filter(regex.search, database))
  </code></pre></li>
  </ol>
  
  <p>The above is expected to yield only <code>path.to.first.some.object.of.mine</code> object</p>
  
  <p>I also considered <code>Trie</code> data structure but this one won't support the "regex" kind of filtering.</p>
  
  <p>Is there a faster approach for filtering strings?</p>