含未知XYZ分量的整数块合并优化方案问询

系统基础规则 #

• 块结构：每个块包含**出现次数（occurance）**和三个整数值(x,y,z)，示例：(4, 2, 3) * 6
• 合并规则：
  • 若XYZ分量完全匹配，可直接合并，如(4,2,3)*6与(4,2,3)*5合并为(4,2,3)*11
  • 若块的XYZ分量含未知值n（可匹配任意值），确定n的取值后若块等价则可合并，如(4,2,3)*4与(4,2,n)*2，当n=3时合并为(4,2,3)*6
• 补充规则：无意义的n最终需转为0，如(1,5,n)需转为(1,5,0)

建模示例块列表 #

(1, 5, n) * occurance
(2, 5, 2) * occurance
(2, 5, n) * occurance
(1, n, n) * occurance
(3, 1, 4) * occurance
(4, 0, 0) * occurance
(n, 2, n) * occurance
(n, n, n) * occurance

出现次数存储位宽计算规则 #

存储位宽公式：

floor(log2(all occurance values) + 1)

示例：二进制存储中，若最大出现次数为7（0b111），则存储位宽为3位。

核心合并问题 #

提取以下三个块：

(1, 5, n) * a
(1, n, n) * b
(n, 2, n) * c

存在两种可选合并路径：

路径一 #

(1,  5,  n) * a -> 合并
(1, <5>, n) * b -> 合并
(n,  2,  n) * c

路径二 #

( 1,  5,  n) * a
( 1, <2>, n) * b -> 合并
(<1>, 2,  n) * c -> 合并

优化目标与约束 #

1. 合并后块数最少
2. 尽可能降低最大出现次数，避免增加存储位宽
3. 全量场景下需避免n^k复杂度的迭代实现（此前尝试剔除列中冗余唯一值的方法，在列含n时失效）

内容的提问来源于stack exchange，提问作者OwenTheProgrammer