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

Question

我需要一种快速的方法来找到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个值中.如果样本<= maxValues,我们不做任何事情,这为我们提供了快速而轻松的救助.我遇到的问题是每次找到新的更好的价值时都会进行洗牌.它一直向下运行maxValues,直到它找到它的位置,洗牌maxValues中的所有元素为自己腾出空间.

我已经准备好了解SIMD解决方案或缓存优化,因为它看起来有一些缓存发生冲突.降低此操作的成本将极大地影响我的整体算法的性能,因为这被称为多次,占我总体成本的60-80%.

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

我只想过预加载maxValues的前M个元素,这可能会带来一些小的节省.在当前的算法中,前M个元素保证一直向下移动,只是为了初始填充maxValues.

任何优化大师的帮助将非常感谢:)

Answer 1

你可以尝试一些想法.在N = 100和M = 15的一些快速测试中,我能够在VC++ 2010中将它提高约25%,但是自己测试一下,看看它们是否对你的情况有帮助.根据实际使用/数据和编译器优化,其中一些更改可能没有甚至是负面影响.

• maxValues除非您需要,否则每次都不要分配新数组.使用堆栈变量而不是动态分配会使我+ 5%.
• 更改g_Source[i][j]到g_Source[j][i]的收益,你很有点(并不像我以为会有).
• 使用SourcePoint1底部列出的结构让我再获得几个百分点.
• 约+ 15%的最大涨幅是替换本地变量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
};