Return an upper bound on ratio() very quickly.
- def __init__(self, isjunk=None, a='', b=''):
+ def __init__(self, isjunk=None, a='', b=''):
"""Construct a SequenceMatcher.
Optional arg isjunk is None (the default), or a one-argument
Optional arg b is the second of two sequences to be compared. By
default, an empty string. The elements of b must be hashable. See
also .set_seqs() and .set_seq2().
+ Optional arg autojunk should be set to False to disable the
+ "automatic junk heuristic" that treats popular elements as junk
+ (see module documentation for more information).
# DOES NOT WORK for x in a!
# for x in b, isbpopular(x) is true iff b is reasonably long
- # (at least 200 elements) and x accounts for more than 1% of
- # its elements. DOES NOT WORK for x in a!
+ # (at least 200 elements) and x accounts for more than 1 + 1% of
+ # its elements (when autojunk is enabled).
+ # DOES NOT WORK for x in a!
+ self.autojunk = autojunk
def set_seqs(self, a, b):
# from starting any matching block at a junk element ...
# also creates the fast isbjunk function ...
# b2j also does not contain entries for "popular" elements, meaning
- # elements that account for more than 1% of the total elements, and
+ # elements that account for more than 1% of the total elements, and
# when the sequence is reasonably large (>= 200 elements); this can
# be viewed as an adaptive notion of semi-junk, and yields an enormous
# speedup when, e.g., comparing program files with hundreds of
# out the junk later is much cheaper than building b2j "right"
+ for i, elt in enumerate(b):
+ indices = b2j.setdefault(elt, )
+ for elt in list(b2j.keys()): # using list() since b2j is modified
+ # Purge popular elements that are not junk
- for i, elt in enumerate(b):
- if n >= 200 and len(indices) * 100 > n:
+ if self.autojunk and n >= 200:
+ for elt, idxs in list(b2j.items()):
- # Purge leftover indices for popular elements.
- for elt in populardict:
- # Now b2j.keys() contains elements uniquely, and especially when
- # the sequence is a string, that's usually a good deal smaller
- # than len(string). The difference is the number of isjunk calls
- for d in populardict, b2j:
- # Now for x in b, isjunk(x) == x in junkdict, but the
- # latter is much faster. Note too that while there may be a
- # lot of junk in the sequence, the number of *unique* junk
- # elements is probably small. So the memory burden of keeping
- # this dict alive is likely trivial compared to the size of b2j.
- self.isbjunk = junkdict.__contains__
- self.isbpopular = populardict.__contains__
+ # Now for x in b, isjunk(x) == x in junk, but the latter is much faster.
+ # Sicne the number of *unique* junk elements is probably small, the
+ # memory burden of keeping this set alive is likely trivial compared to
+ self.isbjunk = junk.__contains__
+ self.isbpopular = popular.__contains__
def find_longest_match(self, alo, ahi, blo, bhi):
"""Find longest matching block in a[alo:ahi] and b[blo:bhi].