| 264 | # repeatedly |
| 265 | |
| 266 | def __chain_b(self): |
| 267 | # Because isjunk is a user-defined (not C) function, and we test |
| 268 | # for junk a LOT, it's important to minimize the number of calls. |
| 269 | # Before the tricks described here, __chain_b was by far the most |
| 270 | # time-consuming routine in the whole module! If anyone sees |
| 271 | # Jim Roskind, thank him again for profile.py -- I never would |
| 272 | # have guessed that. |
| 273 | # The first trick is to build b2j ignoring the possibility |
| 274 | # of junk. I.e., we don't call isjunk at all yet. Throwing |
| 275 | # out the junk later is much cheaper than building b2j "right" |
| 276 | # from the start. |
| 277 | b = self.b |
| 278 | self.b2j = b2j = {} |
| 279 | |
| 280 | for i, elt in enumerate(b): |
| 281 | indices = b2j.setdefault(elt, []) |
| 282 | indices.append(i) |
| 283 | |
| 284 | # Purge junk elements |
| 285 | self.bjunk = junk = set() |
| 286 | isjunk = self.isjunk |
| 287 | if isjunk: |
| 288 | for elt in b2j.keys(): |
| 289 | if isjunk(elt): |
| 290 | junk.add(elt) |
| 291 | for elt in junk: # separate loop avoids separate list of keys |
| 292 | del b2j[elt] |
| 293 | |
| 294 | # Purge popular elements that are not junk |
| 295 | self.bpopular = popular = set() |
| 296 | n = len(b) |
| 297 | if self.autojunk and n >= 200: |
| 298 | ntest = n // 100 + 1 |
| 299 | for elt, idxs in b2j.items(): |
| 300 | if len(idxs) > ntest: |
| 301 | popular.add(elt) |
| 302 | for elt in popular: # ditto; as fast for 1% deletion |
| 303 | del b2j[elt] |
| 304 | |
| 305 | def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None): |
| 306 | """Find longest matching block in a[alo:ahi] and b[blo:bhi]. |