fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. class Matrix {
  4. private:
  5.     int** v;
  6.     int size;
  7.     Matrix merge(const Matrix& c11, const Matrix& c12, const Matrix& c21, const Matrix& c22) const {
  8.         Matrix m(size);
  9.         int cursize = size / 2;
  10.         for (int i = 0; i < cursize; i++) {
  11.             for (int j = 0; j < cursize; j++) {
  12.                 m(i, j) = c11(i, j);
  13.                 m(i + cursize, j) = c21(i, j);
  14.                 m(i, j + cursize) = c12(i, j);
  15.                 m(i + cursize, j + cursize) = c22(i, j);
  16.             }
  17.         }
  18.         return m;
  19.     }
  20. public:
  21.     static bool added;
  22.     Matrix() : size(0), v(nullptr) {}
  23.     Matrix(int s) : size(s) {
  24.         v = new int* [size];
  25.         for (int i = 0; i < size; i++) {
  26.             v[i] = new int[size];
  27.         }
  28.     }
  29.  
  30.     Matrix(const Matrix& m, const int index1, const int index2) {
  31.         size = m.size / 2;
  32.         v = new int* [size];
  33.         for (int i = 0; i < size; i++) {
  34.             v[i] = new int[size];
  35.         }
  36.         for (int i = index1; i - index1 < size; i++) {
  37.             for (int j = index2; j - index2 < size; j++) {
  38.                 int item = m(i, j);
  39.                 v[i - index1][j - index2] = item;
  40.             }
  41.         }
  42.     }
  43.     void getMatrix(int size) {
  44.         int n = size;
  45.         if (n % 2 != 0) {
  46.             size++;
  47.             added = true;
  48.         }
  49.         this->size = size;
  50.         v = new int* [size];
  51.         for (int i = 0; i < size; i++) {
  52.             v[i] = new int[size];
  53.         }
  54.         for (int i = 0; i < n; i++) {
  55.             for (int j = 0; j < n; j++) {
  56.                 v[i][j] = rand() % 100;
  57.             }
  58.         }
  59.     }
  60.     void display() const {
  61.         int n = added ? size - 1 : size;
  62.         for (int i = 0; i < n; i++) {
  63.             for (int j = 0; j < n; j++) {
  64.                 cout << v[i][j] << " ";
  65.             }
  66.             cout << endl;
  67.         }
  68.     }
  69.     int& operator() (const int index1, const int index2) const {
  70.         return v[index1][index2];
  71.     }
  72.  
  73.     Matrix(const Matrix& m) {
  74.         if (m.v == nullptr) return;
  75.         this->v = new int*[m.size];
  76.         for (int i = 0; i < m.size; ++i)
  77.             v[i] = new int[m.size];
  78.         this->size = m.size;
  79.     }
  80.  
  81.     Matrix(Matrix&& m) {
  82.         this->v = m.v;
  83.         this->size = m.size;
  84.         m.v = nullptr;
  85.         m.size = 0;
  86.     }
  87.  
  88.     ~Matrix() {
  89.         if(v != nullptr)
  90.             for (int i = 0; i < size; ++i)
  91.                 delete[] v[i];
  92.         delete[] v;
  93.         v = nullptr;
  94.         size = 0;
  95.     }
  96.  
  97.     const Matrix operator+(const Matrix& m) const {
  98.         Matrix r(size);
  99.         for (int i = 0; i < size; i++) {
  100.             for (int j = 0; j < size; j++) {
  101.                 r(i, j) = v[i][j] + m(i, j);
  102.             }
  103.         }
  104.         return r;
  105.     }
  106.     const Matrix operator-(const Matrix& m) const {
  107.         Matrix r(size);
  108.         for (int i = 0; i < size; i++) {
  109.             for (int j = 0; j < size; j++) {
  110.                 r(i, j) = v[i][j] - m(i, j);
  111.             }
  112.         }
  113.         return r;
  114.     }
  115.  
  116.     Matrix& operator =(const Matrix& other) {
  117.         if (this == &other || other.v == nullptr)
  118.             return *this;
  119.         this->~Matrix();
  120.         v = new int* [other.size];
  121.         for (int i = 0; i < other.size; ++i) {
  122.             v[i] = new int[other.size];
  123.             for (int j = 0; j < other.size; ++j)
  124.                 v[i][j] = other.v[i][j];
  125.         }
  126.         size = other.size;
  127.         return *this;
  128.     }
  129.  
  130.     Matrix simpleMultiplication(const Matrix& m) const {
  131.         Matrix res(size);
  132.         int prom = 0;
  133.         for (int i = 0; i < size; i++) {
  134.             for (int j = 0; j < size; j++) {
  135.                 for (int k = 0; k < size; k++) {
  136.                     prom += v[i][k] * m(k, j);
  137.                 }
  138.                 res(i, j) = prom;
  139.             }
  140.         }
  141.         return res;
  142.     }
  143.     const Matrix operator* (const Matrix& B) const {
  144.         if (size == 1) {
  145.             Matrix m(size);
  146.             m(0, 0) = v[0][0] * B(0, 0);
  147.             return m;
  148.         }
  149.         // init of base matrixes
  150.         Matrix A11(*this, 0, 0);
  151.         Matrix A12(*this, 0, size / 2);
  152.         Matrix A21(*this, size / 2, 0);
  153.         Matrix A22(*this, size / 2, size / 2);
  154.         Matrix B11(B, 0, 0);
  155.         Matrix B12(B, 0, size / 2);
  156.         Matrix B21(B, size / 2, 0);
  157.         Matrix B22(B, size / 2, size / 2);
  158.         // end of init
  159.         //prom matrixes S
  160.         Matrix s1 = A21 + A22;
  161.         Matrix s2 = s1 - A11;
  162.         Matrix s3 = A11 - A21;
  163.         Matrix s4 = A12 - s2;
  164.         Matrix s5 = B12 - B11;
  165.         Matrix s6 = B22 - s5;
  166.         Matrix s7 = B22 - B12;
  167.         Matrix s8 = s6 - B21;
  168.         // end of prom matrixes
  169.         Matrix p1 = s2 * s6;
  170.         Matrix p2 = A11 * B11;
  171.         Matrix p3 = A12 * B21;
  172.         Matrix p4 = s3 * s7;
  173.         Matrix p5 = s1 * s5;
  174.         Matrix p6 = s4 * B22;
  175.         Matrix p7 = A22 * s8;
  176.  
  177.         Matrix t1 = p1 + p2;
  178.         Matrix t2 = t1 + p4;
  179.  
  180.         Matrix c11 = p2 + p3;
  181.         Matrix c12 = t1 + p5 + p6;
  182.         Matrix c21 = t2 - p7;
  183.         Matrix c22 = t2 + p5;
  184.  
  185.         return merge(c11, c12, c21, c22);
  186.     }
  187. };
  188.  
  189. class Test {
  190. private:
  191.     int matrixSizes[6] = { 4, 16, 32, 64,128,256 };
  192.  
  193. public:
  194.     void getTests() {
  195.         for (int size : matrixSizes) {
  196.             clock_t average1 = 0;
  197.             clock_t average2 = 0;
  198.             for (int i = 0; i < 1; i++) {
  199.                 Matrix m1;
  200.                 m1.getMatrix(size);
  201.                 Matrix m2;
  202.                 m2.getMatrix(size);
  203.                 clock_t start1 = clock();
  204.                 Matrix m = m1 * m2;
  205.                 clock_t finish1 = clock() - start1;
  206.                 clock_t start2 = clock();
  207.                 m = m1.simpleMultiplication(m2);
  208.                 clock_t finish2 = clock() - start2;
  209.                 average1 += finish1;
  210.                 average2 += finish2;
  211.             }
  212.             cout << "For size of matrix: " << size << endl;
  213.             cout << "Time in seconds for shtrassen alghoritm: " << average1 * 1.0 / CLOCKS_PER_SEC << endl;
  214.             cout << "Time in seconds for simple alghoritm: " << average2 * 1.0 / CLOCKS_PER_SEC << endl;
  215.         }
  216.     }
  217. };
  218. bool Matrix::added = false;
  219. int main() {
  220.     Test t;
  221.     t.getTests();
  222.     return 0;
  223. }
Success #stdin #stdout 3.33s 6428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
For size of matrix: 4
Time in seconds for shtrassen alghoritm: 3e-05
Time in seconds for simple alghoritm: 2e-06
For size of matrix: 16
Time in seconds for shtrassen alghoritm: 0.001032
Time in seconds for simple alghoritm: 5e-06
For size of matrix: 32
Time in seconds for shtrassen alghoritm: 0.007232
Time in seconds for simple alghoritm: 4.3e-05
For size of matrix: 64
Time in seconds for shtrassen alghoritm: 0.049087
Time in seconds for simple alghoritm: 0.00025
For size of matrix: 128
Time in seconds for shtrassen alghoritm: 0.478719
Time in seconds for simple alghoritm: 0.002311
For size of matrix: 256
Time in seconds for shtrassen alghoritm: 2.76165
Time in seconds for simple alghoritm: 0.024733
https://ideone.com/aIewpK
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!