parameters: (t)
return_statement: return best
docstring: t -> (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 where for each i in range(len(t)),
          t[i] == t2[(t1[i >> shift] << shift) + (i & mask)]
      where mask is a bitmask isolating the last "shift" bits.
docstring_summary: t -> (t1, t2, shift).  Split a table to save space.
docstring_tokens: t - > ( t1 t2 shift ) . Split a table to save space .
function: def splitbins(t):
      """t -> (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 where for each i in range(len(t)),
          t[i] == t2[(t1[i >> shift] << shift) + (i & mask)]
      where mask is a bitmask isolating the last "shift" bits.
      """
  
      def dump(t1, t2, shift, bytes):
          print("%d+%d bins at shift %d; %d bytes" % (
              len(t1), len(t2), shift, bytes), file=sys.stderr)
          print("Size of original table:", len(t)*getsize(t), \
              "bytes", file=sys.stderr)
      n = len(t)-1    # last valid index
      maxshift = 0    # the most we can shift n and still have something left
      if n > 0:
          while n >> 1:
              n >>= 1
              maxshift += 1
      del n
      bytes = sys.maxsize  # smallest total size so far
      t = tuple(t)    # so slices can be dict keys
      for shift in range(maxshift + 1):
          t1 = []
          t2 = []
          size = 2**shift
          bincache = {}
  
          for i in range(0, len(t), size):
              bin = t[i:i + size]
  
              index = bincache.get(bin)
              if index is None:
                  index = len(t2)
                  bincache[bin] = index
                  t2.extend(bin)
              t1.append(index >> shift)
  
          # determine memory size
          b = len(t1) * getsize(t1) + len(t2) * getsize(t2)
          if b < bytes:
              best = t1, t2, shift
              bytes = b
      t1, t2, shift = best
  
      print("Best:", end=' ', file=sys.stderr)
      dump(t1, t2, shift, bytes)
  
      # exhaustively verify that the decomposition is correct
      mask = 2**shift - 1
      for i in range(len(t)):
          assert t[i] == t2[(t1[i >> shift] << shift) + (i & mask)]
      return best
function_tokens: def splitbins ( t ) : def dump ( t1 , t2 , shift , bytes ) : print ( "%d+%d bins at shift %d; %d bytes" % ( len ( t1 ) , len ( t2 ) , shift , bytes ) , file = sys . stderr ) print ( "Size of original table:" , len ( t ) * getsize ( t ) , "bytes" , file = sys . stderr ) n = len ( t ) - 1 # last valid index maxshift = 0 # the most we can shift n and still have something left if n > 0 : while n >> 1 : n >>= 1 maxshift += 1 del n bytes = sys . maxsize # smallest total size so far t = tuple ( t ) # so slices can be dict keys for shift in range ( maxshift + 1 ) : t1 = [ ] t2 = [ ] size = 2 ** shift bincache = { } for i in range ( 0 , len ( t ) , size ) : bin = t [ i : i + size ] index = bincache . get ( bin ) if index is None : index = len ( t2 ) bincache [ bin ] = index t2 . extend ( bin ) t1 . append ( index >> shift ) # determine memory size b = len ( t1 ) * getsize ( t1 ) + len ( t2 ) * getsize ( t2 ) if b < bytes : best = t1 , t2 , shift bytes = b t1 , t2 , shift = best print ( "Best:" , end = ' ' , file = sys . stderr ) dump ( t1 , t2 , shift , bytes ) # exhaustively verify that the decomposition is correct mask = 2 ** shift - 1 for i in range ( len ( t ) ) : assert t [ i ] == t2 [ ( t1 [ i >> shift ] << shift ) + ( i & mask ) ] return best