将一维“扁平化”索引转换为 N 维数组的 N 维向量索引

Question

我有一个 N 维数组，每个维度具有相同数量的项目（即相同的“长度”）。

给定数组中的一维索引，我想要一个函数来返回与该索引关联的坐标。数组的索引方式实际上并不重要（从某种意义上说，数组的所有维度都是相等的，就将在数组上运行的算法而言，没有任何维度具有优先权）。

因此，例如，如果我有一个 4x4x4 数组，索引 63 应返回 [3,3,3]，索引 0 应返回 [0,0,0]，索引 5 应返回 [1,1,0]。

我编写了以下函数，其中 nDim 是维度数，nBin 是每个维度的长度：

def indicesOf(x,nDim,nBin) :
    indices = []
    for i in arange(0,nDim) :   
        index = (x/nBin**(i))%nBin
        indices.append(index)
        x -= index*nBin**i
    return indices

它似乎有效——但是有没有更有效的方法来进行这个计算？老实说，我有一半“问”了这个问题只是为了分享这个解决方案，因为我在网上找不到解决方案。但如果有更有效的方法来做到这一点，那就太好了——请分享！

上面的函数是用 python 编写的，但我刚刚用它来对 C（实际上是 CUDA）函数进行原型设计，所以没有一个 python 很棒的库可供我使用。

这是结合 JackOLantern 和 Eric 关于以下两种尺寸的力量的评论的解决方案。它似乎适用于我尝试过的少数测试用例。

def indicesPowOf2(x,nDim,nBin) :
    logWidth = math.log(nBin,2)         
    indices = [0]*nDim
    for i in arange(nDim) :
        indices[i] = x & (nBin-1)
        x = x >> int(logWidth)
    return indices

Answer 1

您可以避免使用**（幂运算符）来降低计算成本，特别是当您需要将此代码添加到 CUDA 内核时。

下面的方法可能会更有效

void indices(int x, int nDim, int nBin, int indices[]) {
    for(int i=0;i<nDim;i++) {
        indices[i] = x % nBin;
        x /= nBin;
    }
}

如果您的nBin值是 2 的幂，则可以使用>>和&来替换/和%。