时间戳

首页 > 解决方案 > 计算二维数组的总和很慢

android - 计算二维数组的总和很慢

问题描述

我正在使用 RenderScript 构建一个 Android 应用程序。我想创建一个二维数组，其中包含矩形中从原点到 (x, y) 的所有整数的总和。

如此处所述，RenderScript 是一种 C99 派生语言。RS_KERNEL框架将为每个像素调用一次带有关键字的任何函数。不保证调用的顺序。通过为Java/KotlingenerateGridPixelCount提供一块分配的内存来调用它。每个项目都由相应的返回值设置。

因此，例如：

   Input                Output
                  -----------------
                  | 0 | 0 | 0 | 0 |
-------------     -----------------
| 1 | 1 | 1 |     | 0 | 1 | 2 | 3 | 
-------------     -----------------
| 0 | 1 | 1 |     | 0 | 1 | 3 | 5 |
-------------     -----------------
| 1 | 1 | 1 |     | 0 | 2 | 5 | 8 |
-------------     -----------------

对于小型阵列，这是可行的，但是当阵列与屏幕一样大（1080x2280）时，我编写的函数需要很长时间。

static bool shouldCheckPixel(uint x, uint y) {
    return (x + y) % (width / stepSize) == 0 || (x - y) % (width / stepSize) == 0;
}

int RS_KERNEL generateGridPixelCount(uint x, uint y) {
    int pixelCount = 0;

    for (int dx = 0; dx < x; dx++) {
        for (int dy = 0; dy < y; dy++) {
            if (shouldCheckPixel(dx, dy)) {
                pixelCount++;
            }
        }
    }

    return pixelCount;
}

但是，如果pixelCount++;删除了 if 或删除了 if 语句，它几乎会立即完成。当它变慢时，它就会结合起来。

上一个RS_KERNEL函数循环输出。这可以反过来：

void RS_KERNEL generateGridPixelCount(uchar4 input, uint x, uint y) {
   if (shouldCheckPixel(x, y)) {
      for (int x = 0; x < dx; x++) {
         for (int y = 0; y < dy; y++) {
            rsAtomicInc(*pixelArray[x][y]);
         }
      }
   }
}

计算这个数组的最佳方法是什么？

标签： androidcarraysrenderscript

解决方案

Eric Postpischil 把我推向了正确的方向；以下片段是我现在使用的。

科特林：

script.forEach_generateShouldCheckPixelLookup(shouldCheckPixelLookup)
script.invoke_generateShouldCheckPixelSum()

渲染脚本：

int RS_KERNEL generateShouldCheckPixelLookup(uint x, uint y) {
    if (shouldCheckPixel(x, y)) {
        return 1;
    } else {
        return 0;
    }
}

void generateShouldCheckPixelSum() {
    for (int y = 1; y < height + 1; y++) {
        for (int x = 1; x < width + 1; x++) {
            int top     = rsGetElementAt_int(shouldCheckPixelSum, x,     y - 1);
            int left    = rsGetElementAt_int(shouldCheckPixelSum, x - 1, y);
            int topLeft = rsGetElementAt_int(shouldCheckPixelSum, x - 1, y - 1);

            int current = rsGetElementAt_int(shouldCheckPixelLookup, x, y);
            int value = top + left - topLeft + current;

            rsSetElementAt_int(shouldCheckPixelSum, value, x, y);
        }
    }
}

generateShouldCheckPixelLookup对每个像素调用一次并将其存储在shouldCheckPixelLookup. 然后generateShouldCheckPixelSum调用一次并运行一次。

我的想法是，由于 RenderScript 尝试并行运行每个像素的调用，这总是比运行单个函数调用一次更快。但是，与我最初的问题generateShouldCheckPixelSum一样快generateGridPixelCount。

推荐阅读