c++ - 使用C++在NxN数组中查找M个最大元素的优化方法

我需要一种快速的方法来找到NxN数组中M个最大元素的2D位置和值。

现在我正在这样做:

struct SourcePoint {
    Point point;
    float value;
}

SourcePoint* maxValues = new SourcePoint[ M ];

maxCoefficients = new SourcePoint*[
for (int j = 0; j < rows; j++) {
    for (int i = 0; i < cols; i++) {
        float sample = arr[i][j];
        if (sample > maxValues[0].value) {
            int q = 1;
            while ( sample > maxValues[q].value && q < M ) {
                maxValues[q-1] = maxValues[q];      // shuffle the values back
                 q++;
            }
            maxValues[q-1].value = sample;
            maxValues[q-1].point = Point(i,j);
        }
    }
}

Point结构只是两个整数-x和y。

这段代码基本上是对插入的值进行插入排序。maxValues [0]始终包含具有最低值的SourcePoint，但仍将其保持在迄今为止已加密的前M个值之内。如果样本
我现在已经准备好研究SIMD解决方案或缓存优化，因为看起来好像发生了相当多的缓存颠簸。降低此操作的成本将极大地影响我的整体算法的性能，因为这被多次调用，并且占我总体成本的60-80％。

我试过使用std::vector和make_heap，但我认为创建堆的开销超过了堆操作的节省。这可能是因为M和N通常不大。 M通常为10-20，N通常为10-30(NxN 100-900)。问题在于此操作被重复调用，并且无法进行预先计算。

我只是想到要预加载maxValues的前M个元素，这可能会节省一些钱。在当前算法中，保证前M个元素一直向下随机播放，以仅初始填充maxValues。

来自优化专家的任何帮助将不胜感激:)

最佳答案

您可以尝试一些方法。在N = 100和M = 15的一些快速测试中，我能够在VC++ 2010中使其速度提高25％左右，但您自己进行测试以查看它们是否对您有帮助。这些更改中的一些可能没有影响，甚至没有负面影响，具体取决于实际的用法/数据和编译器优化。

除非您需要，否则不要每次都分配新的maxValues数组。使用堆栈变量而不是动态分配可以使我获得5％的 yield 。

将g_Source[i][j]更改为g_Source[j][i]会给您带来一点点好处(不如我想的那样多)。

使用底部列出的SourcePoint1结构可以使我获得百分之几的收入。

大约+ 15％的最大 yield 是将本地变量sample替换为g_Source[j][i]。编译器可能足够聪明，可以优化对数组的多次读取，而如果使用局部变量则无法做到这一点。

尝试简单的二进制搜索使我损失了百分之几的小钱。对于较大的M/N，您可能会看到好处。

如果可能，请尝试对arr[][]中的源数据进行排序，即使只是部分排序也是如此。理想情况下，您希望在创建源数据的同时生成maxValues[]。

看看如何创建/存储/组织数据可以为您提供模式或信息，以减少生成maxValues[]数组的时间。例如，在最佳情况下，您可以想出一个公式，该公式可以为您提供最高的M坐标，而无需进行迭代和排序。

上面的代码:

struct SourcePoint1 {
     int x;
     int y;
     float value;
     int test;       //Play with manual/compiler padding if needed
};

关于c++ - 使用C++在NxN数组中查找M个最大元素的优化方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7126201/

m个

c++ - 使用C++在NxN数组中查找M个最大元素的优化方法