title: Strategies for speeding up string searches in Python
body: <p>I need some help. I've been working on a file searching app as I learn Python, and it's been a very interesting experience so far, learned a lot and realized how little that actually is.</p>
  
  <p>So, it's my first app, and it needs to be fast! I am unsatisfied with (among other things) the speed of finding matches for sparse searches. </p>
  
  <p>The app caches file and folder names as dbm keys, and the search is basically running search words past these keys. </p>
  
  <p>The GUI is in Tkinter, and to try not get it jammed, I've put my search loop in a thread. The thread recieves queries from the GUI via a queue, then passes results back via another queue. </p>
  
  <p>That's how the code looks:</p>
  
  <pre><code>def TMakeSearch(fdict, squeue=None, rqueue=None):
      '''Circumventing StopIteration(), did not see speed advantage'''
  
      RESULTS_PER_BATCH=50
  
      if whichdb(DB)=='dbhash' or 'dumb' in whichdb(DB): 
          '''iteration is  not implemented for gdbm and (n)dbm, forced to
          pop the keys out in advance for "for key in fdict:" ''' 
  
          fdict=fdict 
      else:
          # 'dbm.gnu', 'gdbm', 'dbm.ndbm', 'dbm'
          fdict=fdict.keys()
  
      search_list=None
      while True:  
          query=None
          while not squeue.empty():        
              #more items may get in (or not?) while condition is checked
              query=squeue.get()
          try:    
              search_list=query.lower().encode(ENCODING).split()
              if Tests.is_query_passed:
                  print (search_list)
          except:
              #No new query, or a new database has been created and needs to be synced
                  sleep(0.1)
                  continue
          else:
              is_new_query=True
  
          result_batch=[] 
          for key in fdict: 
              separator='*'.encode(ENCODING)   #Python 3, yaaay
              filename=key.split(separator)[0].lower()
  
              #Add key if matching    
              for token in search_list:
                  if not token in filename:
                      break              
              else: 
                  #Loop hasn't ended abruptly    
                  result_batch.append(key)
  
              if len(result_batch)&gt;=RESULTS_PER_BATCH: 
                  #Time to send off a batch
                  rqueue.put((result_batch, is_new_query))
                  if Tests.is_result_batch: 
                      print(result_batch, len(result_batch))
                      print('is_result_batch: results on queue')
  
                  result_batch=[]
                  is_new_query=False
                  sleep(0.1)
  
                  if not squeue.empty(): 
                      break
  
          #Loop ended naturally, with some batch&lt;50        
          rqueue.put((result_batch, is_new_query))    
  </code></pre>
  
  <p>Once there are few results, the results cease to be real-time, but rather take a few seconds, and that's on my smallish 120GB hard disk.</p>
  
  <p>I believe it can be faster, and wish to make the search real-time.</p>
  
  <p>What approaches exist to make the search faster? </p>
  
  <p>My current marks all involve ramping up the faculties that I use - use multiprocessing somehow, use cython, perhaps somehow use ctypes to make the searches circumvent the Python runtime. </p>
  
  <p>However, I suspect there are simpler things that can be done to make it work, as I am not savvy with Python and optimization. </p>
  
  <p>Assistance please!</p>
  
  <ul>
  <li><p>I wish to stay within the standard library if possible, as a proof of concept and for portability (currently I only scandir as an external library on Python &lt;3.5), so for example ctypes would be preferrable to cython.</p></li>
  <li><p>If it's relevant/helpful, the rest of the code is here - 
  <a href="https://github.com/h5rdly/Jiffy" rel="nofollow noreferrer">https://github.com/h5rdly/Jiffy</a></p></li>
  </ul>
  
  <p><strong>EDIT:</strong></p>
  
  <p>This is the heart of the function, take a few pre-arrangements:</p>
  
  <pre><code>for key in fdict: 
      for token in search_list:
          if not token in key:
              break
      else:     
          result_batch.append(key)
  </code></pre>
  
  <p>where <code>search_list</code> is a list of strings, and <code>fdict</code> is a dictionary or a dbm (didn't see a speed difference trying both). </p>
  
  <p>This is what I wish to make faster, so that results arrive in real-time, even when there are only few keys containing my search words.</p>
  
  <p><strong>EDIT 2:</strong>
  On @hpaulj 's advice, I've put the dbm keys in a (frozen) set, to gain a noticable imrovement on Windows/Python27 (dbhash):
  <a href="https://i.stack.imgur.com/B1fKl.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/B1fKl.gif" alt="enter image description here"></a></p>
  
  <p>I have some caveats though -  </p>
  
  <ul>
  <li><p>For my ~50Gb in use, the frozenset takes 28Mb, as by <code>pympler.asizeof</code>. So for the full 1Tb, I suspect it'll take a nice share of RAM.</p></li>
  <li><p>On linux, for some reason, the conversion not only doesn't help, but the query itself stops getting updated in real time for some weird reason for the duration of the search, making the GUI look unrespnsive.</p></li>
  <li><p>On Windows, This is almost as fast as I want, but still not warp-immediate.</p></li>
  </ul>
  
  <p>So this comes around to this addition:</p>
  
  <pre><code>if 'win' in sys.platform:
      try:
          fdict=frozenset(fdict)
      except:
          fdict=frozenset(fdict.keys())
  </code></pre>
  
  <p>Since it would take a significant amount of RAM for larger disks, I think I'll add it as an optional faster search for now, "Scorch Mode". </p>
  
  <p>I wonder what to do next. I thought that perhaps, if I could somehow export the keys/filenames to a datatype that ctypes can pass along, I could then pop a relevant C function to do the searches.
  Also, perhaps learn the Python bytecode and do some lower-level optimization.</p>
  
  <p>I'd like this to be as fast as Python would let me, please advise.</p>