algorithm - 2 个整数的非幂的包装集
问题描述
我有一组整数,每个整数都有一个特定的范围:
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
这可以节省我一大笔钱!
这就是我的问题所在:使用这种布局加载和存储数字的最佳方式是什么?
解决方案
具有不同范围的变量列表,如下所示:
foo = [1, 5]
bar = [1, 10]
baz = [1, 200]
可以(几乎?)被解释为混合基数表示。如果它们从零开始,则对应将是立即的,但是由于它们从一开始(或者通常:如果它们是任何有限的可能性集),它们必须先重新映射一点,这里只需减去一个以转换为“打包" 状态并在再次解码时添加一个。
编码很好也很简单,只涉及廉价的操作:
packed = (foo - 1) + 5 * (bar - 1) + (5 * 10) * (baz - 1)
比例因子当然来自可能状态的数量。每个元素都需要重新映射到从零开始的连续范围,然后按前面元素的#states 的乘积进行缩放,第一个元素缩放 1(空乘积)。顺便注意一下 [1 .. 5] 有 5 个状态,而不是 4 个。
解码涉及余数和除法,最简单(但通常不是最快)的方法是逐位提取:
// extract foo
foo = packed % 5 + 1
// drop foo from packed representation
packed /= 5
// extract bar (which is now the lowest digit in 'packed')
bar = packed % 10 + 1
// drop bar
packed /= 10
// top digit is left over
baz = packed + 1
对于较大的示例,首先将打包的数字“切割”成几个单独的部分,然后独立解码这些部分会更有效。这可以防止产生一长串依赖操作,而逐位方法自然会导致这种情况。
直接使用打包表示通常很棘手,除了在您知道不会溢出的情况下从元素中添加和减去。
推荐阅读
- apache-kafka - 两个独立的引导服务器可以订阅同一个 Kafka 主题吗?
- node.js - 吉普错误!堆栈错误:无法建立隧道套接字,原因=在建立安全 TLS 连接之前已断开客户端网络套接字
- python - Selenium get(url) 显示错误的页面
- node.js - 是否可以在 .eleventy 配置文件中使用“addGlobalData”?
- nginx - 从 Plex 服务器 URL 中删除 /web/index.html#!/
- java - 在另一个 Line 组件上绘制自定义 Line 组件,我做错了什么?
- c# - 使用 Vector2.MoveTowards 缓入和缓出
- android - 在其他地方点击时,TextView 的选择弹出菜单没有关闭
- r - R Shiny:设置反应滤波器的默认值
- javascript - 如何仅从带有“RANKED_SOLO_5x5”而不是“RANKED_FLEX_SR”的json部分获取信息(“tier”、“rank”、“leaguePoints”)