3

我有两个大小相同的数组：

A = [a1, a2, a3]
B = [b1; b2; b3]

我需要执行数组乘法以构建以下矩阵：

            |a1|
M = A * B = |a2| * |b1 b2 b3|  //M31 * M13 ==> M33 and M13 * M31 ==> M11.  Mnk: Matrix with n lines and k columns.
            |a3|


    | a1b1 a1b2 a1b3 |
M = | a2b1 a2b2 a2b3 |
    | a3b1 a3b2 a3b3 |

哪个是完成这项任务的最快算法？

更详细：我需要使用 8086 指令集来完成这项工作，但在这里我更愿意接收 C 代码中的算法。

4

6 回答 6

1

查看 BLAS 和 LAPACK。这些都是高度优化的。除非您有理由避免使用库，否则不要重新发明轮子。这两个都有 C API。

于 2013-10-31T18:59:30.520 回答
1

它看起来像矩阵乘法算法 更准确地说，我认为您正在寻找一种有效的方法。

矩阵相乘的一般方法是 O(n^3)，但如果采用有效的方法，您将得到 O(n^2.807)。是否值得您花时间实施有效的方法？我不知道，但你必须评估它。

如果您只有一维数组，那么唯一的方法是双循环，在这种情况下，您正在查看运行时间 O(n^2)。想出它不应该那么复杂：

for(int i = 0; i < A.length; i++)
{
    for(int j = 0; j < B.length; j++)
    {
        C[i][j] = A[i] * B[j];
    }
}
于 2013-10-31T19:01:07.373 回答
1

可能对于这种简单的 3x3 情况和编译器优化，最简单的O(N^2)算法将足够快。如果有人想进行基准测试，我们非常欢迎您：

#include <stdio.h>

void lean_and_mean_mul(int a[3], int b[3], int out[3][3])
{
    int i, j;
    for (i = 0; i < 3; i++)
    {
        for (j = 0; j < 3; j++)
        {
            out[i][j] = a[i] * b[j];
        }
    }
}

int main(void)
{
    int a[] = { 1, 2, 3 };
    int b[] = { 4, 5, 6 };
    int out[3][3];
    lean_and_mean_mul(a, b, out);
    int i, j;
    for (i = 0; i < 3; i++)
    {
        for (j = 0; j < 3; j++)
        {
            printf("%d ", out[i][j]);
        }
        printf("\n");
    }
    return 0;
}

让我们看看lean_and_mean_mul()生成的程序集gcc -O2 -S：

    xorl    %eax, %eax         
.L2:
    movl    (%rsi), %ecx
    imull   (%rdi), %ecx
    movl    %ecx, (%rdx,%rax)
    movl    4(%rsi), %ecx
    imull   (%rdi), %ecx
    movl    %ecx, 4(%rdx,%rax)
    movl    8(%rsi), %ecx
    imull   (%rdi), %ecx
    addq    $4, %rdi
    movl    %ecx, 8(%rdx,%rax)
    addq    $12, %rax
    cmpq    $36, %rax
    jne .L2
    rep
    ret

请注意，编译器决定展开一个循环。

随着gcc -O3编译器展开两个循环。代码。它真的很快，因为它根本没有跳跃。

于 2013-10-31T19:53:37.997 回答
0

如果您的数组很大并且您想尽可能快地将它们相乘，那么您应该查看BLAS库。

于 2013-10-31T18:59:18.883 回答
0

我建议您以最简单/最愚蠢的方式编写代码（使用 2 个 fors 和 if/else），以便让您的编译器决定可以/不可以进行哪些优化（不要忘记将标志设置为 - O3)。这比尝试通过反转矩阵访问等来优化缓存/内存访问来尝试优化代码要好。如果您想进行真正的优化，请找到更好的算法，否则编码简单。

于 2013-10-31T19:08:47.810 回答
0

关于矩阵乘法的维基百科文章告诉你你需要的一切。

在这种情况下，您不会比O(n^2)更快。

在一般情况下，矩阵乘法的最佳性能是O(n ^log2(7))
（大约是O(n^2.8)）

于 2013-10-31T19:17:24.097 回答