t, trace=0 -> (t1, t2, shift). Split a table to save space. t is a sequence of ints. This function can be useful to save space if many of the ints are the same. t1 and t2 are lists of ints, and shift is an int, chosen to minimize the combined size of t1 and t2 (in C code), and wh
(t, trace=0)
| 1295 | |
| 1296 | |
| 1297 | def splitbins(t, trace=0): |
| 1298 | """t, trace=0 -> (t1, t2, shift). Split a table to save space. |
| 1299 | |
| 1300 | t is a sequence of ints. This function can be useful to save space if |
| 1301 | many of the ints are the same. t1 and t2 are lists of ints, and shift |
| 1302 | is an int, chosen to minimize the combined size of t1 and t2 (in C |
| 1303 | code), and where for each i in range(len(t)), |
| 1304 | t[i] == t2[(t1[i >> shift] << shift) + (i & mask)] |
| 1305 | where mask is a bitmask isolating the last "shift" bits. |
| 1306 | |
| 1307 | If optional arg trace is non-zero (default zero), progress info |
| 1308 | is printed to sys.stderr. The higher the value, the more info |
| 1309 | you'll get. |
| 1310 | """ |
| 1311 | |
| 1312 | if trace: |
| 1313 | def dump(t1, t2, shift, bytes): |
| 1314 | print("%d+%d bins at shift %d; %d bytes" % ( |
| 1315 | len(t1), len(t2), shift, bytes), file=sys.stderr) |
| 1316 | print("Size of original table:", len(t)*getsize(t), "bytes", |
| 1317 | file=sys.stderr) |
| 1318 | n = len(t)-1 # last valid index |
| 1319 | maxshift = 0 # the most we can shift n and still have something left |
| 1320 | if n > 0: |
| 1321 | while n >> 1: |
| 1322 | n >>= 1 |
| 1323 | maxshift += 1 |
| 1324 | del n |
| 1325 | bytes = sys.maxsize # smallest total size so far |
| 1326 | t = tuple(t) # so slices can be dict keys |
| 1327 | for shift in range(maxshift + 1): |
| 1328 | t1 = [] |
| 1329 | t2 = [] |
| 1330 | size = 2**shift |
| 1331 | bincache = {} |
| 1332 | for i in range(0, len(t), size): |
| 1333 | bin = t[i:i+size] |
| 1334 | index = bincache.get(bin) |
| 1335 | if index is None: |
| 1336 | index = len(t2) |
| 1337 | bincache[bin] = index |
| 1338 | t2.extend(bin) |
| 1339 | t1.append(index >> shift) |
| 1340 | # determine memory size |
| 1341 | b = len(t1)*getsize(t1) + len(t2)*getsize(t2) |
| 1342 | if trace > 1: |
| 1343 | dump(t1, t2, shift, b) |
| 1344 | if b < bytes: |
| 1345 | best = t1, t2, shift |
| 1346 | bytes = b |
| 1347 | t1, t2, shift = best |
| 1348 | if trace: |
| 1349 | print("Best:", end=' ', file=sys.stderr) |
| 1350 | dump(t1, t2, shift, bytes) |
| 1351 | if __debug__: |
| 1352 | # exhaustively verify that the decomposition is correct |
| 1353 | mask = ~((~0) << shift) # i.e., low-bit mask of shift bits |
| 1354 | for i in range(len(t)): |