Preferably I would use C++ to execute the code, but I would be open to any suggestion for a better language for the situation. I essentially want to use Strassen's algorithm to solve matrices, and I want to know how I would solve a matrices and measure its runtime. # Version 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
I found the code above for the algorithm.
#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;
}
I found this code for measuring the runtime of the code. However I saw I could use
/usr/bin/time ./MyProgram if I have cygwin installed.
In short, how would I use my code to solve actual matrices using Strassen's algorithm and other matrice solving algorithms? Also how would I run the code? Thank you for the help, I am a novice to coding, and I am doing this in order to test the algorithmic efficiency of different matrice solving algorithms in different scenarios.
Time measurement
measuring of time depends on platform so what OS? On windows I would use Performance Counters. If you got access to x86 assembly you could also use RDTSC instruction but that needs some knowledge to use properly like setting affinity to single CPU, obtaining and stabilizing CPU frequency etc.
The OS time granularity is an issue too so if your measured process is too short you might need of some filtering of multiple measurements in order to get the correct values.
You can avoid some of the problems by measuring multiple repetitions of the process so the times get above 100ms and divide the resulting time by number of repetitions.
Also while reusing the same code/data while measuring the CACHE can be a problem too messing up your results.
running the code
The code of yours looks like Python so you can not use that in C/C++ directly instead you need to invoke it somehow with Python interpreter for example by creating python process with parameters telling it to open and run your source code. However in this case you need to wait until the code finishes by scanning its Handle if it is still valid... Of coarse you need to write and execute your python stuff in a way that when finished it closes. However I am afraid This will add big overhead as starting/stopping the python process alone could be much much slower than the matrix multiplication you measure ...
Other option is to having it in DLL or OBJ form and importing that into your C/C++ instead (however not sure if that is possible for Python code). This way you just have to call a function within your C/C++ app so no problems there ...
For some inspiration see:
In case the code is not too complex or does not require other libs and stuff you can try to port it to C/C++ code and use it directly.