[kupfer] relevance: Simplify _findBestMatch loop

[Ulrik Sverdrup <usverdrup src gnome org>]

commit 9d4316e10a797d46c269aa728d817f89fd2c5b89
Author: Ulrik Sverdrup <ulrik sverdrup gmail com>
Date:   Fri Sep 11 18:41:53 2009 +0200

    relevance: Simplify _findBestMatch loop
    
    Apparently, checking if we got the whole query in the end of the
    string checks three conditions of which the latter two are always
    true. Doing less work here, and in addtion exiting directly when the
    query doesn't fit anymore, saves some cycles.
    
    Save len(query) in local variable, since we use this measure three
    times every turn of the loop, we can save some cycles by precomputing
    it.

 kupfer/relevance.py |   32 ++++++++++++++------------------
 1 files changed, 14 insertions(+), 18 deletions(-)
---
diff --git a/kupfer/relevance.py b/kupfer/relevance.py
index 8eb3b88..588e049 100644
--- a/kupfer/relevance.py
+++ b/kupfer/relevance.py
@@ -188,7 +188,6 @@ def _findBestMatch(s, query):
     >>> _findBestMatch('teerminal', 'erml')
     (2, 9)
     """
-    index = -1
     bestMatch = -1, -1
     
     # Find the last instance of the last character of the query
@@ -198,36 +197,33 @@ def _findBestMatch(s, query):
     # No instance of the character?
     if lastChar == -1:
         return bestMatch
-    
+
     # Loop through each instance of the first character in query
     _index = s.find
-    index = _index(query[0], index + 1)
-    while index >= 0:
-        # Is there room for a match?
-        if index > (lastChar + 1 - len(query)):
-            break
-        
+    index = _index(query[0])
+
+    queryLength = len(query)
+    lastIndex = lastChar - len(query) + 1
+    while 0 <= index <= lastIndex:
         # Look for the best match in the tail
         # We know the first char matches, so we dont check it.
         cur = index + 1
         qcur = 1
-        while (qcur < len(query)) and (cur < len(s)):
+        while (qcur < queryLength) and (cur < len(s)):
             if query[qcur] == s[cur]:
                 qcur += 1
             cur += 1
-        
-        if ((qcur == len(query)) \
-        and (((cur - index) < (bestMatch[1] - bestMatch[0])) \
-        or (bestMatch[0] == -1))):
+
+        # if whole query fit, save it; else we are done
+        if (qcur == queryLength):
             bestMatch = (index, cur)
-        
-        if index == (len(s) - 1):
+        else:
             break
-        
+
         index = _index(query[0], index + 1)
-        
+
     return bestMatch
-    
+
 if __name__ == '__main__':
     import doctest
     doctest.testmod()