在多维数组的Leu中使用哈希表

Question

EDIT:找到解决方案了!就像评论者建议的那样，使用memset是一个更好的方法。将整个for循环替换为

memset(lookup->n, -3, (dimensions*sizeof(signed char)));

,

long int dimensions = box1 * box2 * box3 * box4 * box5 * box6 * box7 * box8 * memvara * memvarb * memvarc * memvard * adirect * tdirect * fs * bs * outputnum;

<标题>介绍

现在，我看到的是一个for循环:

    for (j = 0;j < box1; j++)
        {
            for (k = 0; k < box2; k++)
            {
                for (l = 0; l < box3; l++)
                {
                    for (m = 0; m < box4; m++)
                    {
                        for (x = 0;x < box5; x++)
                        {
                            for (y = 0; y < box6; y++)
                            {
                                for (xa = 0;xa < box7; xa++)
                                {
                                    for (xb = 0; xb < box8; xb++)
                                    {
                                        for (nb = 0; nb < memvara; nb++)
                                        {
                                            for (na = 0; na < memvarb; na++)
                                            {
                                                for (nx = 0; nx < memvarc; nx++)
                                                {
                                                    for (nx1 = 0; nx1 < memvard; nx1++)
                                                    {
                                                        for (naa = 0; naa < adirect; naa++)
                                                        {
                                                            for (nbb = 0; nbb < tdirect; nbb++)
                                                            {
                                                                for (ncc = 0; ncc < fs; ncc++)
                                                                {
                                                                    for (ndd = 0; ndd < bs; ndd++)
                                                                    {
                                                                        for (o = 0; o < outputnum; o++)
                                                                        {
                                                                            lookup->n[j][k][l][m][x][y][xa][xb][nb][na][nx][nx1][naa][nbb][ncc][ndd][o] = -3;     //set to default value
                                                                        }
                                                                    }
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

<标题>

这个循环在主运行的每个循环中被调用，将值重置到初始状态。不幸的是，对于程序的结构来说，有必要将这么多值保存在一个数据结构中。

这里有一个问题:对于每60秒的程序运行时间，57秒仅用于这个函数。<标题>

我的问题是:哈希表是线性数组的合适替代品吗?这个数组的基数是O(n^17)，而哈希表的理想基数是O(1)。

• 如果是的话，你会推荐什么哈希库?这个程序是C语言的，没有原生哈希支持。
• 如果没有，你会推荐什么替代?
• 你能提供一些你认为应该如何实现的伪代码吗?

<标题> 指出

OpenMP被用来尝试并行化这个循环。许多实现只会导致运行时间的轻微或大幅增加。
1. 内存使用不是一个特别的问题——这个程序旨在在一个疯狂的高规格计算机上运行。
2. 我们是学生研究人员，被推进到迄今未知的优化和并行化世界-请容忍我们，并感谢您的任何帮助

Answer 1

散列vs数组

正如注释所指出的，数组在这里不应该是一个问题。查找具有已知偏移量的数组O(1)。

<标题>瓶颈h1> 我看来，这里的大部分工作(也是它很慢的原因)是内循环中指针取消引用的数量。 为了更详细地解释，考虑以下代码中的myData[x][y][z]:

for (int x = 0; x < someVal1; x++) {
   for (int y = 0; y < someVal2; y++) {
      for (int z = 0; z < someVal3; z++) {
         myData[x][y][z] = -3; // x and y only change in outer-loops.
      }
   }
}

为了计算-3的位置，我们进行查找并添加值-一次是myData[x]，然后再一次是myData[x][y]，最后是myData[x][y][z]。

由于该查找位于循环的最内部部分，因此有冗余读取。myData[x]和myData[x][y]正在被重新计算，即使只有z的值在改变。查找是在之前的迭代中执行的，但是没有存储结果。

对于你的循环，每次迭代都会计算许多层查找，即使内部循环中只有o的值发生变化。

瓶颈改进

要在每个循环迭代、每个循环级别进行一次查找，只需存储中间查找。使用int*作为间接类型(尽管这里可以使用任何类型)，上面的示例代码(使用myData)将变成:

int **a, *b;
for (int x = 0; x < someVal1; x++) {
   a = myData[x]; // Store the lookup.
   for (int y = 0; y < someVal2; y++) {
      b = a[y]; // Indirection based on the stored lookup.
      for (int z = 0; z < someVal3; z++) {
         b[z] = -3; // This can be extrapolated as needed to deeper levels.
      }
   }
}

这只是示例代码，可能需要进行一些小的调整才能使其编译(强制类型转换等)。注意，在三维数组中使用这种方法可能没有任何优势。但是，对于具有简单内循环操作(例如赋值)的17维大型数据集，这种方法应该会有很大帮助。

最后，我假设你实际上不只是分配-3的值。您可以使用memset来更有效地完成这个目标。