具有特定属性的高维数组搜索

Question

我有一个三维数组，其中的值是单调递增或递减的。如何找到所有满足 |f(X,Y,Z) – v1| < t 的 (x,y)。

- CRM

---

函数 f(x,y,z) 在三个轴向上是否连续可导？换句话说，您是否有通过可能不那么昂贵的运算来计算例如 f(x+1,y,z) 的选项，前提是您已知 f(x,y,z) 的值？ - UltraInstinct

你能委派给另一个核心、处理器或线程吗？例如，使用2个线程，线程1计算奇数Z位置，线程2计算偶数Z位置。可能还有其他算法可用于并行执行。 - Thomas Matthews

你正在寻找Java解决方案吗？C++中有一些库，例如Boost，用于线程支持。 - Thomas Matthews

@ThomasMatthews 目前我正在使用Java作为一个大型项目的一部分来解决这个问题。我可以在Java中使用线程，这不是问题。除了你已经建议的地方，你能否建议我在算法的哪些其他地方使用线程来加速计算？ - CRM

你应该有两个研究方向：减少操作数量和并行计算。如果你能够将问题分解为可并行执行的独立操作，可以使用图形处理器核心的库进行加速。矩阵运算是很好的候选项。搜索“CUDA矩阵运算C ++”。 - Thomas Matthews

Answer 1

有Omega(n^2)个点，它们的坐标总和为n-1。事先不知道这些点的值如何相互比较，因此在最坏情况下，必须检查所有这些点。通过在每个常数z切片中运行2D算法，可以提供与常数因子相匹配的上限。

- David Eisenstat

---

@TheGame = O(n^2)，是的。常数可能会有所改善，所以请稍等一段时间再标记最佳答案。 - David Eisenstat

Answer 2

如果三维数组在每个维度上都是单调非递减的，那么我们知道如果

f(x0, y0, z0) < v1 - t
          or
f(x1, y1, z1) > v1 + t

那么子数组 f(x0...x1, y0...y1, z0...z1) 中的任何元素都不能包含任何有趣的点。为了看清这一点，例如可以考虑以下情况：

f(x0, y0, z0) <= f(x, y0, z0) <= f(x, y, z0) <= f(x, y, z)

对于子数组中的每个 (x, y, z)，都成立一个类似的关系，并且对于 (x1, y1, z1)，也存在一个类似的关系（方向相反）。因此，f(x0, y0, z0) 和 f(x1, y1, z1) 分别是子数组的最小值和最大值。

可以通过使用递归细分方案来实现简单的搜索方法。

template<typename T, typename CBack>
int values(Mat3<T>& data, T v0, T v1, CBack cback,
           int x0, int y0, int z0, int x1, int y1, int z1) {
    int count = 0;
    if (x1 - x0 <= 2 && y1 - y0 <= 2 && z1 - z0 <= 2) {
        // Small block (1-8 cells), just scan it
        for (int x=x0; x<x1; x++) {
            for (int y=y0; y<y1; y++) {
                for (int z=z0; z<z1; z++) {
                    T v = data(x, y, z);
                    if (v >= v0 && v <= v1) cback(x, y, z);
                    count += 1;
                }
            }
        }
    } else {
        T va = data(x0, y0, z0), vb = data(x1-1, y1-1, z1-1);
        count += 2;
        if (vb >= v0 && va <= v1) {
            int x[] = {x0, (x0 + x1) >> 1, x1};
            int y[] = {y0, (y0 + y1) >> 1, y1};
            int z[] = {z0, (z0 + z1) >> 1, z1};
            for (int ix=0; ix<2; ix++) {
                for (int iy=0; iy<2; iy++) {
                    for (int iz=0; iz<2; iz++) {
                        count += values<T, CBack>(data, v0, v1, cback,
                                                  x[ix], y[iy], z[iz],
                                                  x[ix+1], y[iy+1], z[iz+1]);
                    }
                }
            }
        }
    }
    return count;
}

该代码接受一个子数组，如果最小元素太大或最大元素太小，则跳过搜索，并将数组分成8个子立方体。递归在子数组很小时（2x2x2或更小）结束，在这种情况下进行完全扫描。

实验表明，使用这种相当简单的方法可以搜索包含100x200x300个元素的数组，通过设置元素 f(i,j,k) 为max(f(i-1,j,k), f(i,j-1,k), f(i,j,k-1)) + random(100)并检查范围内符合条件的元素，仅需检查约3％的元素（每找到一个元素，检查25个元素）。

Data 100x200x300 = 6000000 elements, range [83, 48946]
Looking for [24594-1=24593, 24594+1=24595]
Result size = 6850 (5.4 ms)
Full scan = 6850 (131.3 ms)
Search count = 171391 (25.021x, 2.857%)

- 6502

Answer 3

对于每个值（例如v1），执行以下步骤：

1. 对于与X轴相切的4个立方体面（Y=0，Y=n-1，Z=0，Z=n-1），执行2D算法。将匹配的（X，Y，Z）单元格集合按X坐标索引以供下一步使用。
2. 对于沿X轴的所有n个切片（X=0..n-1），使用步骤1的结果初始化2D算法的第一个边界点。如果给定x坐标没有匹配的单元格，则在常数时间内移动到下一个切片。

最坏情况的复杂度为O(O(2D算法) * n)。

对于多个值（v2等），保留函数评估的缓存，并为每个值重新执行算法。对于100^3，密集数组足够。

将其视为等值面提取算法可能很有用，尽管您的单调性约束使其更容易。

- ajclinto

---

在第一步中，通过 Y=0，我指的是在XZ平面上所有Y坐标都为0的二维切片。该切片在第一个X切片上与一条线相交（Y=0且X=0），因此如果第一步在该线上找到匹配单元格，则可以将其用作下一步的起点。通过搜索与X相切的4个面，所有在X=0周边的匹配单元格在第二步之前就已经被确定 - 因此我们知道该切片中是否存在任何匹配的单元格。如果有，2D算法可以从这些单元格开始（而不必再次搜索周长以寻找起点）。 - ajclinto

Answer 4

由于函数是非递减的，我认为你可以用二分搜索来做一些事情。
在一个 (x, 1, 1)（列）向量中，您可以进行二分搜索以找到与您的要求匹配的范围，这将需要 O(log(n)) 的时间。
要查找哪些列向量，请对 (x, y, 1)（切片）向量进行二分搜索，仅检查第一个和最后一个点以确定该值是否可以落在它们之间，这将再次需要 O(log(n)) 的时间。
要知道要查找哪些切片，请对整个立方体进行二分搜索，检查4个点 ((0, 0), (x, 0), (x, y), (0, y))，这将需要 O(log(n)) 的时间。
因此，总体而言，该算法将需要 log(z) + a * log(y) + b * log(x) 的时间，其中 a 是匹配切片的数量，b 是匹配列的数量。
最坏情况下的朴素计算是 O(y * z * log(x))。

- Daniel