我有一组整数,每个整数都有一个特定的范围:
foo = [1, 5]
bar = [1, 10]
baz = [1, 200]
我可以根据它们可以拥有的不同状态的数量来计算分别存储每个数字需要多少位:
foo = 5 possible states ~ 3 bits
bar = 10 possible states ~ 4 bits
baz = 200 possible states ~ 8 bits
这给了我总共15位 . 但是每个数字都有一个未使用的范围,导致空间浪费 . 我可以通过计算所有组合数的所有可能状态来计算整个集合的所需位数:
5 * 10 * 200 = 10000 possible states ~ 14 bits
这可以节省我一点!
这就是我的问题所在:使用这种类型的布局加载和存储数字的最佳方法是什么?
1 回答
具有不同范围的变量列表,如下所示:
可以(几乎?)被解释为混合基数表示 . 如果它们从零开始,则对应关系将是立即的,但由于它们从一开始(或者一般来说:如果它们是任何有限的可能性集合),它们必须首先重新映射,这里只需减去一个转换为"packed"状态并在再次解码时添加一个 .
编码很简单,只涉及廉价操作:
比例因子当然来自可能的状态数 . 每个元素都需要重新映射到从零开始的连续范围,然后按前面元素的#states的乘积缩放,第一个元素按1缩放(空产品) . 顺便说一下,[1 .. 5]有5个状态,而不是4个 .
解码涉及剩余和划分,最简单(但不是一般最快)的方法是逐位提取:
对于更大的示例,首先将打包的数字“切”成几个单独的部分,然后独立地解码它们会更有效 . 这可以防止具有长链依赖操作,这种操作自然会导致数字逐位方法 .
直接使用压缩表示通常很棘手,除非在知道不会溢出的情况下添加和减少元素 .