4

私はこれらのインデックスを持っています:

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,etc...

マトリックス内のノードのインデックス (対角要素を含む) は次のとおりです。

1
2  3
4  5  6
7  8  9  10
11 12 13 14 15
16 17 18 19 20 21
etc...

i,jこれらのインデックスから座標を取得する必要があります。

1,1
2,1 2,2
3,1 3,2 3,3
4,1 4,2 4,3 4,4
5,1 5,2 5,3 5,4 5,5
6,1 6,2 6,3 6,4 6,5 6,6
etc...

座標を計算する必要がある場合、インデックスは 1 つしかなく、他のインデックスにはアクセスできません。

4

2 に答える 2

5

まったく最適化されていません:

int j = idx;
int i = 1;

while(j > i) {
    j -= i++;
}

最適化:

int i = std::ceil(std::sqrt(2 * idx + 0.25) - 0.5);
int j = idx - (i-1) * i / 2;

そして、ここにデモンストレーションがあります：

あなたは私を探しています：

sumRange(1, i-1) < idx && idx <= sumRange(1, i)

sumRange(min, max) が min と max の間の整数を合計すると、両方が含まれます。しかし、あなたはそれを知っているので:

sumRange(1, i) = i * (i + 1) / 2

次に、次のものがあります。

idx <= i * (i+1) / 2
=> 2 * idx <= i * (i+1)
=> 2 * idx <= i² + i + 1/4 - 1/4
=> 2 * idx + 1/4 <= (i + 1/2)²
=> sqrt(2 * idx + 1/4) - 1/2 <= i
于 2016-12-04T00:40:31.063 に答える
2

私の場合 (標準 C で実装された CUDA カーネル)、ゼロベースのインデックスを使用しているため (対角線を除外したいので)、いくつかの調整を行う必要がありました。

// idx is still one-based
unsigned long int idx = blockIdx.x * blockDim.x + threadIdx.x + 1; // CUDA kernel launch parameters
// but the coordinates are now zero-based
unsigned long int x = ceil(sqrt((2.0 * idx) + 0.25) - 0.5);
unsigned long int y = idx - (x - 1) * x / 2 - 1;

結果は次のとおりです。

[0]: (1, 0)
[1]: (2, 0)
[2]: (2, 1)
[3]: (3, 0)
[4]: (3, 1)
[5]: (3, 2)

また、 Flórez-Rueda y Moreno 2001の式を再導出し、次の結果に到達しました。

unsigned long int x = floor(sqrt(2.0 * pos + 0.25) + 0.5);

CUDA 注:倍精度演算の使用を避けるために考えられることはすべて試しましたが、sqrtCUDA の単精度関数は、1 億 2,100 万を超える位置を x、y 座標に変換するほど正確ではありません (1,024 スレッドを使用する場合)。ブロックごと、および 1 つのブロック次元に沿ったインデックスのみ)。一部の記事では、結果を特定の方向に向けるために「修正」を採用していますが、これはある時点で必然的に崩壊します。

于 2019-09-20T23:46:48.710 に答える