Bash - 二维矩阵相乘

Question

假设我有一个 n x n 的二维矩阵，已知 n=4，其值为 1 - 16，如下图所示：

我需要按以下方式进行乘法运算：

Array1*Array2 = result

Array3*result = result1

Array4*result1 = result2

ShowMatrix()
{
echo "MyMatrix is:"
for((i=0;i<$n;i++))do
   for((j=0;j<$n;j++))do
printf '  '${myArray[i*n+j]}
done
printf '\n';
done
}

我尝试按照架构将其分为4个部分，并将每个部分分配给Array1、Array2、Array3和Array4

cut1()
{
for((i=0;i<$n/2;i++))do
   for((j=0;j<$n/2;j++))do
Array1[i*n+j]=${myArray[i*n+j]}
done
done
}

cut2()
{
for((i=0;i<$n/2;i++))do
   for((j=$n/2;j<$n;j++))do
Array2[i*n+j]=${myArray[i*n+j]}
done
done
}

cut3()
{
for((i=$n/2;i<$n;i++))do
   for((j=0;j<$n/2;j++))do
Array3[i*n+j]=${myArray[i*n+j]}
done
done
}

cut4()
{
for((i=$n/2;i<$n;i++))do
   for((j=$n/2;j<$n;j++))do
Array4[i*n+j]=${myArray[i*n+j]}
done
done
}

接下来，我尝试按照如下示意图将它们相乘：

Array1*Array2 = result

Array3*result = result1

Array4*result1 = result2

multiply()
{
 for((i=0;i<$n;i++))do
   for((j=0;j<$n;j++))do
     result[i*n+j]=0
     for((k=0;k<$n;k++))do
let "result[i*n+j]=${result[i*n+j]}+${Array1[i*n+k]}*${Array2[k*n+j]}"
done
done
done
}

multiply1()
{
 for((i=0;i<$n;i++))do
   for((j=0;j<$n;j++))do
     result1[i*n+j]=0
     for((k=0;k<$n;k++))do
let "result1[i*n+j]=${result1[i*n+j]}+${result[i*n+k]}*${Array3[k*n+j]}"
done
done
done
}

multiply2()
{
 for((i=0;i<$n;i++))do
   for((j=0;j<$n;j++))do
     result2[i*n+j]=0
     for((k=0;k<$n;k++))do
let "result2[i*n+j]=${result2[i*n+j]}+${result1[i*n+k]}*${Array4[k*n+j]}"
done
done
done
}

在我调用函数后的结果如下：

cut1
cut2
cut3
cut4
multiply
multiply1
multiply2


echo "result is:"
for((i=0;i<$n;i++))do
   for((j=0;j<$n;j++))do
printf '  '${result[i*n+j]}
done
printf '\n';
done

echo "result1 is:"
for((i=0;i<$n;i++))do
   for((j=0;j<$n;j++))do
printf '  '${result1[i*n+j]}
done
printf '\n';
done

echo "result2 is:"
for((i=0;i<$n;i++))do
   for((j=0;j<$n;j++))do
printf '  '${result2[i*n+j]}
done
printf '\n';
done

- Choletski

---

在我看来，Bash不是进行矩阵乘法的适当语言。虽然你可能可以做到，但并不容易。你可能也可以用sed来做，因为sed是计算上完备的；但这比使用Bash还要荒谬。 - Jonathan Leffler

如果你想在下标中进行乘法运算，${variable[$((3*2+2))]}可以工作（访问元素8），${variable[$(($i*$n+$j))]}和${variable[$((i*n+j))]}也可以适用于合适的i、n和j值。然而，我仍然认为使用Bash来完成这个任务不是一个好主意，但显然变态的老师们认为相反。 - Jonathan Leffler

@Choletski：“它不起作用”是最没有具体信息的错误报告之一；它没有提供任何信息。你是否收到了错误消息？结果是否出乎意料？（如果是，你期望得到什么，实际得到了什么？）还是它只是躺在沙发上看电视？ - rici

@rich 实际上问题是逻辑问题。你看，我有一个 4x4 的矩阵，共 16 个值。当我尝试只获取其中的 4 个值（在 cut1-4 方法中），我却得到了一个 4x4 的矩阵，其中有 4 个实际值和 12 个空值，这就是我无法将它们相乘的原因。所以我需要获得一个只有 2x2 的矩阵，每个 cut1-4 方法中都有 4 个有效值。当我执行我的代码时，result、result1 和 result2 都是 0。 - Choletski

@Choletski：您的分析完全正确。我不明白为什么您会觉得难以修复，假设您实际上编写了您在问题中粘贴的代码，因为这只是计算n/2 x n/2矩阵的下标的问题。 - rici

Answer 1

代码写作中的主要概念问题在于将大数组分成小块，但却没有调整这些块的减小尺寸。具体来说，一个确定的错误出现在"cut"函数中。当存储回到Array1..Array3时，你使用的是较大数组的索引而不是减小后的数组。POSIX shell和bash会愉快地扩展缺失的条目并用零填充它们。因此，bash不会帮助你找到这个错误。

同样，"multiply"函数应该只尝试在减小尺寸的数组边界上进行乘法计算。通过将2D数组存储为线性数组，获取数组的边长有一点棘手：你可以像我下面做的那样传递尺寸，或者你可以从数组中获取大小（假设已经正确初始化）并取平方根。

你提到了你所感知到的随机行为。我怀疑这里发生的事情是来自你的环境或过去执行的动态变量查找正在向各种子例程中输入值。为了防范这种情况，我会在函数内部声明所有局部变量。当然，还有那些不是本地的数组，但同样，在程序内部你也应该声明这些。

这就是为什么我认为其他人建议你使用更合适的语言来完成这样的事情。我同意这些评估。

但是，如果您必须使用POSIX shell，则应该更好地了解和使用它。您可以使用bash -n对代码进行语法检查。如果代码符合POSIX标准，那么我强烈推荐这样做，那么ksh -n将为您提供更全面和详细的程序分析。

为了帮助您在此类程序中找出错误，我建议您使用bash调试器。对于测试代码，我建议使用Kate Ward的Unit Test程序shunit。

我已经重写了代码并修复了错误。据我所知，它遵循了您说的要做的事情和您所拥有的代码。然而，您从未真正描述过您想要做的是什么，也没有给出特定数据的预期答案，因此我无法独立验证事情。

我建议做但以下未实施的一件事是DRY（不要重复自己）代码。4个cut函数可以折叠成一个单一的例程，如果您传递开始和结束点以及要存储结果的数组的名称，则需要在此处使用eval。

同样，通过传递被处理的数组的名称，3个multiply函数可以折叠成一个函数。

通过增强您的ShowMatrix程序，我已经删除了重复的显示数组代码。

typeset -ir n=4
typeset -a Array=()
typeset -a Array1=()
typeset -a Array2=()
typeset -a Array3=()
typeset -a Array4=()
typeset -a Result=()
typeset -a Result1=()
typeset -a Result2=()


ShowMatrix() {
    typeset arr=$1
    typeset n=$2
    typeset -i i
    echo "Matrix $arr is:"
    for ((i=0;i<n;i++)) ; do
        typeset -i j
        typeset -i val
        for ((j=0;j<n;j++)) ; do
            ((val=${arr}[i*n+j]))
            printf '%5d ' $val
        done
        printf '\n';
    done
}

cut1() {
    typeset -i i
    typeset -i k=0
    for((i=0;i<n/2;i++)) ; do
        typeset -i j
        for((j=0;j<n/2;j++)); do
            ((Array1[k++] = Array[i*n+j]))
        done
    done
}

cut2() {
    typeset -i i
    typeset -i k=0
    for((i=0;i<n/2;i++)) ; do
        typeset -i j
        for((j=n/2;j<n;j++)) ; do
            ((Array2[k++] = Array[i*n+j]))
        done
    done
}

cut3() {
    typeset -i i
    typeset -i k=0
    for((i=n/2;i<n;i++)) ; do
        for((j=0;j<n/2;j++)) ; do
            ((Array3[k++] = Array[i*n+j]))
        done
    done
}

cut4() {
    typeset -i i
    typeset -i k=0
    for((i=n/2;i<n;i++)) ; do
        for((j=n/2;j<n;j++));  do
           ((Array4[k++] = Array[i*n+j]))
        done
    done
}

multiply() {
    typeset -i i
    typeset -i n=$1
    ShowMatrix Array1 $n
    ShowMatrix Array2 $n
    for((i=0;i<n;i++)); do
        typeset -i j
        for((j=0; j < n; j++)); do
            typeset -i l
            ((l=i*n+j))
            ((Result[l]=0))
            typeset -i k
            for((k=0; k<n; k++)) ; do
                    ((Result[l] += Array1[i*n+k]*Array2[k*n+j]))
            done
        done
    done
}

multiply1()
{
    typeset -i n=$1
    ShowMatrix Result $n
    ShowMatrix Array3 $n
    typeset -i i
    for((i=0; i < n; i++)) ; do
        typeset -i j
        for((j=0; j < n; j++)); do
            typeset -i l
            ((l=i*n+j))
            ((Result1[i*n+j]=0))
            typeset -i k
            for ((k=0;k<n;k++));  do
                ((Result1[l] += Result[i*n+k]*Array3[k*n+j]))
            done
        done
    done
}

multiply2() {
    typeset -i i
    typeset -i n=$1
    ShowMatrix Result1 $n
    ShowMatrix Array4 $n
    for ((i=0; i<n; i++)) ; do
        typeset -i j
        for ((j=0; j < n; j++)) ; do
            typeset -i l
            ((l=i*n+j))
            ((Result2[i*n+j]=0))
            typeset -i k
            for((k=0;k<n;k++)); do
                ((Result2[l] += Result1[i*n+k]*Array4[k*n+j]))
            done
        done
    done
}


typeset -i i
for((i=0; i<n*n; i++)) ; do
       ((Array[i]=i+1))
done

cut1
cut2
cut3
cut4

typeset -i n2
((n2 = n / 2))

multiply $n2
multiply1 $n2
multiply2 $n2
ShowMatrix Result2 $n2

- rocky