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

Question

编辑：找到解决方案！就像评论者建议的那样，使用 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-loop 的怪兽：

    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 用于尝试并行化此循环。许多实施只导致运行时间略有增加。
内存使用量不是特别大的问题 -- 该程序旨在运行在超高规格的计算机上运行。
我们是学生研究人员，被推向一个迄今为止未知的优化和并行化世界——请耐心等待，感谢您的帮助

Answer 1

哈希与数组

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

瓶颈

在我看来，这里的大部分工作（以及速度慢的原因）是内部循环中指针取消引用的数量。

为了更详细地解释，请考虑以下代码中的 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.
      }
   }
}

这只是示例代码，可能需要进行小的调整才能编译（强制转换等）。请注意，将此方法用于 3 维数组可能没有任何优势。但是，对于一个17维的大数据集，内循环操作简单（比如赋值），这种方法应该会有很大的帮助。

最后，我假设您实际上不只是分配 -3 的值。您可以使用 memset 更有效地实现该目标。

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

Using Hash Tables in Leu of Multidimensional Array

c

arrays

hash

multidimensional-array

neural-network

简介

问题

问题

备注

哈希与数组

瓶颈

瓶颈的改进