基于Y轴稀疏特性的无限3D布尔数组特定模式高效搜索方案问询

嘿，这个问题抓准了关键优化点——既然Y值越大，getState返回True的概率越低，那完全可以利用这个稀疏性特性把搜索效率提上去，根本不用傻乎乎地暴力遍历每个(x,z)起点。我来给你唠几个实用的优化思路，都是围绕着“用最罕见的特征快速过滤无效候选”这个核心：

1. 先抓模式里的“硬骨头”：优先定位罕见的高Y值True点 #

因为Y值越大，True值在数组里越稀疏，所以模式中那些要求为True且对应Y值最大的点（这里的Y值是相对于模式自身的y偏移），就是最罕见的“锚点”。我们可以：

• 先预处理模式，把所有要求为True的相对坐标（dx, dy, dz）提取出来，然后按dy从大到小排序（dy越大，对应目标数组的Y值越高，True越罕见）。
• 先在搜索范围内找出所有能匹配排序最靠前的那个锚点的(x,z)位置——也就是目标数组中getState(x+dx, dy, z+dz)为True的点。这些点就是我们的候选起点，数量会比暴力遍历的候选少得多。

比如如果模式里有个点要求在dy=3（Y维度最高层）为True，那这个点在数组里出现的概率极低，用它过滤后，候选起点可能直接从几十万降到几百个，效率提升不是一星半点。

2. 按Y从高到低验证，不满足直接放弃 #

对于每个候选(x,z)起点，别傻乎乎地从Y=0开始挨个验证，而是按Y从高到低的顺序检查模式要求：

• 先查模式中Y值最高的那些要求，一旦发现某个点不匹配（比如模式要求True但数组返回False，或者模式要求False但数组返回True），直接跳过这个起点，不用再查剩下的Y层。
• 因为高Y值的匹配条件最难满足，早发现不匹配就能早止损，节省大量不必要的getState调用。

3. 缓存已查询的结果，避免重复调用 #

在验证不同候选起点时，很可能会重复查询同一个(x,y,z)坐标——比如两个相邻的候选起点会共享很多重叠的Y层坐标。这时候用一个字典缓存所有已调用过的getState结果，键是(x,y,z)三元组，值是返回的布尔值，能避免重复执行相同的查询操作，尤其是在搜索范围大的时候，缓存的收益会非常明显。

4. 预处理模式，提前明确边界范围 #

先把模式的X、Z偏移范围算清楚：

• 找出模式中所有点的dx最小值/最大值，dz最小值/最大值，这样就能确定候选起点(x0,z0)的有效范围：x0必须满足x0+dx >= Xmin且x0+dx <= Xmax（对所有dx），z0同理。
• 这样能直接排除那些会导致模式超出搜索边界的无效起点，不用再对这些点做任何验证。

举个伪代码例子帮你理解 #

# 预处理模式：提取所有要求为True的相对坐标，按dy从大到小排序
pattern_true = sorted(
    [(dx, dy, dz) for (dx, dy, dz) in pattern if pattern[(dx, dy, dz)]],
    key=lambda p: -p[1]
)
# 缓存已查询的状态
state_cache = {}

def get_cached(x, y, z):
    key = (x, y, z)
    if key not in state_cache:
        state_cache[key] = getState(x, y, z)
    return state_cache[key]

# 计算候选起点的有效范围
if pattern_true:
    dx_min, _, dz_min = min(pattern_true, key=lambda p: (p[0], p[2]))
    dx_max, _, dz_max = max(pattern_true, key=lambda p: (p[0], p[2]))
else:
    # 模式全是False，所有在边界内的(x,z)都匹配
    dx_min = dz_min = 0
    dx_max = dz_max = 0

x_start = Xmin - dx_min
x_end = Xmax - dx_max
z_start = Zmin - dz_min
z_end = Zmax - dz_max

# 第一步：用最罕见的锚点过滤候选
candidates = set()
if pattern_true:
    # 取dy最大的那个True点当锚点
    anchor_dx, anchor_dy, anchor_dz = pattern_true[0]
    for x in range(x_start, x_end + 1):
        target_x = x + anchor_dx
        for z in range(z_start, z_end + 1):
            target_z = z + anchor_dz
            if get_cached(target_x, anchor_dy, target_z):
                candidates.add((x, z))
else:
    # 全False模式，直接生成所有有效起点
    for x in range(x_start, x_end + 1):
        for z in range(z_start, z_end + 1):
            candidates.add((x, z))

# 第二步：验证每个候选起点
matching_starts = []
for (x0, z0) in candidates:
    valid = True
    # 先查高Y值的True点
    for dx, dy, dz in pattern_true:
        tx = x0 + dx
        ty = dy
        tz = z0 + dz
        if not get_cached(tx, ty, tz):
            valid = False
            break
    if not valid:
        continue
    # 再查所有要求为False的点
    for (dx, dy, dz) in pattern:
        if pattern[(dx, dy, dz)]:
            continue
        tx = x0 + dx
        ty = dy
        tz = z0 + dz
        if get_cached(tx, ty, tz):
            valid = False
            break
    if valid:
        matching_starts.append((x0, z0))

print("找到的匹配起点：", matching_starts)

这些思路都是完全贴合你提到的稀疏性特性设计的，核心就是用最罕见的特征快速缩小候选范围，避免无意义的暴力遍历，能把搜索效率提升几个数量级，尤其是当模式中有高Y值True点的时候，效果会特别明显。

内容来源于stack exchange