At http://people.ubuntu.com/~robertc/baz2.0/plugins/search/trunk
------------------------------------------------------------ revno: 68 revision-id: [email protected] parent: [email protected] committer: Robert Collins <[email protected]> branch nick: trunk timestamp: Wed 2009-01-21 17:56:03 +1100 message: Reduce the number of string comparisons during prefix lookups in BTree indices. === modified file 'index.py' --- a/index.py 2009-01-21 04:42:53 +0000 +++ b/index.py 2009-01-21 06:56:03 +0000 @@ -17,6 +17,7 @@ """The core logic for search.""" +from bisect import bisect_left from itertools import chain import math import re @@ -1414,11 +1415,22 @@ for node in nodes.values(): # TODO bisect the edge nodes? / find boundaries and so skip # some work. - for node_key, (value, refs) in sorted(node.keys.iteritems()): + items = sorted(node.keys.items()) + low_value = (key, ()) + start_pos = bisect_left(items, low_value) + for pos in xrange(start_pos, len(items)): + node_key, (value, refs) = items[pos] if node_key[:-1] != key_prefix: + # Shouldn't happen, but may. continue if not node_key[-1].startswith(key_suffix): - continue + # A node that doesn't match + if node_key[-1] > key_suffix: + # and is after: stop + break + else: + # was before the search start point. + continue if self.node_ref_lists: yield (self, node_key, value, refs) else: -- bazaar-commits mailing list [email protected] https://lists.ubuntu.com/mailman/listinfo/bazaar-commits
