寻找一种在 C++ 中计算某些值的有效方法[已关闭]

Question

我正在用 C++ 编写代码。我有一些向量，现在我使用 for 循环来计算我需要的向量。但是，事实证明这是非常耗时的，特别是当向量的大小相对较大时。请在下面找到代码作为示例。我想知道是否有其他方法可以更有效地进行此计算。

在此代码中，我们有两组参数，由向量 U 和 Landa 给出，均为 float 类型。我想确定对应于 Landa 和 U 相乘之和的最大值的索引，然后将其保存在向量 L 上。抱歉，如果有点不清楚。

vector<int> L = vector<int>(n);
    for (int i = 0; i < n; i++)
    {
        float maxL = 0;
        int maxL_index = 0;
        for (int j = 0; j < m; j++)
        {
            float sumUL = 0;
            for (int s = 0; s < Ses; s++)
                sumUL = sumUL + Landa[s] * U[s][i][j];

            if (sumUL > maxL)
            {
                maxL = sumUL;
                maxL_index = j;
            }

        }
        L[i]=maxL_index;
        
    }

当我运行这段代码时，特别是当向量的大小有点大时，计算所有计算需要太多时间。例如，对于 Ses=500，大约需要一分钟才能完成计算。我想知道除了 for 循环之外，是否还有其他方法来进行此计算。例如，在Matlab中使用一种Matrix的东西。

Answer 1

因此，

U

是一个 n x m 的数学向量数组。每个向量都有

Ses

个元素。

Landa

也是一个数学向量。

计算

Landa

点

U[i][j]

以找到第二维中最大的点积，然后将索引存储到

L[i]

中。

点积是沿向量的投影，根据用于点积的向量的大小进行缩放。因此

Landa

的两个重要部分是它的（Ses 维）符号方向和它的大小。

大小无关紧要，因为我们只关心哪个是最大值，而不是最大值。因此，您要计算的是数组

U[i]

中的哪个元素沿

Landa

方向最远。

您正在进行高维排序。

假设我们有一个相对固定的

U

数组，并且我们给它提供了许多

Landa

，并且我们想要预处理 U 以使其更快，我们将想要排列

U

以便我们可以搜索它 而无需检查每个元素.

想象一下，如果 Ses 为 1。那么我们可以将每个

U[i][j]

从最小到最大排序，并找到给定

Landa

的最大值只需要知道它是指向正数还是负数。

如果 Ses 为 2，我们可以构建一棵四叉树。为了找到点缀有

Landa

的最大向量，我们只需从原点朝那个方向看，并从最远的四叉树单元开始，剔除任何无法到达它的单元。

四叉树之类的技术扩展到更高的维度（八叉树、k-d 树和二元空间划分树）。这个想法是排列

U[i][...]

以便搜索不需要访问所有元素。

现在，使点积本身更快是另一个挑战。这可能取决于向量的结构 - 它们是否倾向于均匀，或者它们是否倾向于由几个值主导？由几个值主导的向量可以被视为伪稀疏向量，并且通过仅将“重要”分量（如果它们匹配）相乘，可以更快地计算点积的有界近似，其中所有分量的有界误差包括其他产品。

当确定a点x和b点x是否更大时，这种快速有界近似通常就足够了。如果不是，您可以将问题减少到更少的候选者，以达到更高的准确度。

然而，设计良好的空间划分可能会使更快的点积变得多余；如果你的向量确实由相对少量的大型组件主导，那么智能空间分区将利用这一点。

但是，所有这些都将 (a) 如果您的数据需要深入了解，并且 (b) 并不容易做到。

有很容易解决的暴力解决方案。您可以确保您的代码被转换为 SIMD（单指令多数据），甚至可以在 GPU 上正确完成。与简单的 CPU 实现相比，这可以使您的速度提高 100 倍到 1000 倍。

所以，需要注意的事项：

1. SIMD 和 GPU 加速。一般来说只是加速。
2. 您生成的向量是否近似“稀疏”？稀疏点积近似。如果

   Ses

   很大，这会减少工作量。

3. U[i][...]

   的空间分区排序，因此如果

   m

   相对恒定且

   U[i][j]

   发生变化，则无需检查所有

   Landa

   元素。
4. 如果

   n

   很大，则无能为力。