2

最好我会使用 C++ 来执行代码，但我愿意接受任何关于这种情况的更好语言的建议。我本质上想使用 Strassen 的算法来求解矩阵，并且我想知道如何求解矩阵并测量其运行时间。# 版本 3.6

import numpy as np 

def split(matrix): 
""" 
    Splits a given matrix into quarters. 
    Input: nxn matrix 
    Output: tuple containing 4 n/2 x n/2 matrices corresponding to a, b, c, d 
"""
row, col = matrix.shape 
row2, col2 = row//2, col//2
return matrix[:row2, :col2], matrix[:row2, col2:], matrix[row2:, :col2], 
matrix[row2:, col2:] 

def strassen(x, y): 
""" 
Computes matrix product by divide and conquer approach, recursively. 
Input: nxn matrices x and y 
Output: nxn matrix, product of x and y 
"""

# Base case when size of matrices is 1x1 
if len(x) == 1: 
    return x * y 

# Splitting the matrices into quadrants. This will be done recursively 
# untill the base case is reached. 
a, b, c, d = split(x) 
e, f, g, h = split(y) 

# Computing the 7 products, recursively (p1, p2...p7) 
p1 = strassen(a, f - h) 
p2 = strassen(a + b, h)      
p3 = strassen(c + d, e)        
p4 = strassen(d, g - e)      
p5 = strassen(a + d, e + h)      
p6 = strassen(b - d, g + h) 
p7 = strassen(a - c, e + f) 

# Computing the values of the 4 quadrants of the final matrix c 
c11 = p5 + p4 - p2 + p6 
c12 = p1 + p2        
c21 = p3 + p4            
c22 = p1 + p5 - p3 - p7 

# Combining the 4 quadrants into a single matrix by stacking horizontally and vertically. 
c = np.vstack((np.hstack((c11, c12)), np.hstack((c21, c22)))) 

return c

我找到了上面的算法代码。

#include <time.h>
int main(void) {
clock_t tStart = clock();
/* Do your stuff here */
printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
return 0;

}

我发现此代码用于测量代码的运行时间。但是我看到我可以使用

/usr/bin/time ./MyProgram if I have cygwin installed.

简而言之，我将如何使用我的代码来使用 Strassen 算法和其他矩阵求解算法来求解实际矩阵？另外我将如何运行代码？谢谢大家的帮助，我是一个编码新手，做这个是为了测试不同的矩阵求解算法在不同场景下的算法效率。

4

1 回答 1

2

  1. 时间测量

    时间的测量取决于平台那么什么操作系统？在 Windows 上，我会使用Performance Counters。如果您可以访问 x86 程序集，您也可以使用 RDTSC 指令，但这需要一些知识才能正确使用，例如设置与单个 CPU 的关联、获取和稳定 CPU 频率等。

    操作系统时间粒度也是一个问题，因此如果您的测量过程太短，您可能需要对多个测量进行一些过滤以获得正确的值。

    您可以通过测量该过程的多次重复来避免一些问题，以便时间超过 100 毫秒，然后将结果时间除以重复次数。

    此外，在测量CACHE时重用相同的代码/数据可能会导致结果混乱。

  2. 运行代码

    您的代码看起来像 Python，因此您不能直接在 C/C++ 中使用它，而是需要使用 Python 解释器以某种方式调用它，例如通过创建带有参数的 Python 进程来告诉它打开并运行您的源代码。但是，在这种情况下，如果代码仍然有效，您需要通过扫描其句柄等到代码完成...粗略地说，您需要以完成后关闭的方式编写和执行您的 python 内容。但是我担心这会增加很大的开销，因为单独启动/停止 python 进程可能比您测量的矩阵乘法慢得多......

    其他选择是将其以 DLL 或 OBJ 形式导入到您的 C/C++ 中（但不确定这是否适用于 Python 代码）。这样你只需要在你的 C/C++ 应用程序中调用一个函数，所以那里没有问题......

    有关一些灵感，请参阅：

    如果代码不太复杂或不需要其他库和东西，您可以尝试将其移植到 C/C++ 代码并直接使用它。

于 2021-02-11T08:46:32.873 回答