计算数组中的索引比让编译器更有效吗？

Question

我试图将神经网络函数推广到任意多层,因此我需要多个矩阵来保存每层中每个神经元的权重.我最初明确地在R中声明矩阵对象来保存每个图层的权重.我没有在每层中使用一个矩阵,而是考虑了一种方法(不是说它是原始的),将所有权重存储在一个数组中,并定义了一个"索引函数"来将权重映射到数组中的相应索引.

我将函数定义如下:

哪里 是第i层中第j个神经元的第k个权重,L(r)是第r层中神经元的数量.写完这些定义之后,我意识到stackoverflow不允许像mathoverflow这样的乳胶,这是不幸的.现在的问题是:以这种方式计算权重指数是否更有效,或者效率更低？在查看了一般如何为数组计算索引之后,如果我只是在每个持有权重的层中保留一个矩阵,那么这基本上就是在编译时所做的事情,所以看起来我可能只是让我的代码过于复杂和难以了解时间效率是否没有差异.

Answer 1

TL;DR使用更容易理解的矩阵，并利用优化的 CPU 指令。

用计算机科学的术语来说，算法的效率（可扩展性）是通过使用Big O 成本来推理的。可以对时间复杂度和空间复杂度进行评分。
使用 Big O 表示法来比较这两种方法：

数组法

时间复杂度：
数组索引访问是O(1)时间，无论数组变得有多大，在给定索引的情况下访问元素在计算上都一样容易。

由于您创建了一个函数来计算权重指数k-th，这会增加一些小的复杂性，但可能会在恒定O(1)时间内运行，因为它是一个数学表达式，因此可以忽略不计。

空间复杂度： O(N)其中N是所有层的权重数量。

矩阵法

时间复杂度：
矩阵本质上是一个具有O(1)访问权限的二维数组

空间复杂度
O(N + M)，其中N是神经元数量，M是权重数量。

从概念上讲，我们可以看到这两种方法具有相同的时间和空间复杂度分数。
然而，还涉及其他权衡（并且作为一个好的 SO-er 必须告知您这些）

当涉及到使用数组与矩阵方法中的数据时，数组方法效率较低，因为它规避了MISD 操作的机会。正如@liborm提到的，矢量化（MISD）操作由较低级别的系统库处理，例如LAPACK/BLAS，它为某些矩阵操作“批处理”CPU指令（与每次发送新指令相比，在CPU上传输和计算数据的开销成本更低）

我没有每层有一个矩阵，而是想到了一种方法……将所有权重存储在一个数组中

很难理解为什么您会选择后者，因为它要求您创建一个定制的索引函数。也许把你所有的重量都放在一长排的地方会更好？然而，我认为维护数组映射所需的心理负担高于专用于一个层的多个矩阵。

类似于哈希表的矩阵结构会更容易推理

layers <- list(layer1 = [[...]], layer2 = [[...]], layerN = [[...]])

进一步阅读

http://www.noamross.net/blog/2014/4/16/vectorization-in-r--why.html