欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++ Strassen算法代碼的實(shí)現(xiàn)

 更新時(shí)間:2020年03月31日 08:31:54   作者:Shiroha  
這篇文章主要介紹了C++ Strassen算法代碼的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

本文僅代碼,無(wú)理論解釋

實(shí)話實(shí)說(shuō),我覺(jué)得這個(gè)算法在C系列的語(yǔ)言下,簡(jiǎn)直垃圾到爆炸……畢竟是一群完全不懂程序數(shù)學(xué)家對(duì)著紙弄出來(lái)的,看起來(lái)好像非常的有用,實(shí)際上耗時(shí)是非常爆炸的。

但是《算法導(dǎo)論》里有啊……然后上課又要求手寫(xiě)一個(gè)

于是我就手寫(xiě)了一個(gè)……我盡可能的減少使用的空間同時(shí)加快速度了,當(dāng) n = 512 的時(shí)候,內(nèi)存使用量峰值沒(méi)有超過(guò) 10mb,而且是通過(guò)遞歸實(shí)現(xiàn) Strassen 算法

其中,in.txt 已經(jīng)預(yù)先準(zhǔn)備了 3000000 個(gè)范圍在 0-100 隨機(jī)數(shù),避免程序在運(yùn)算過(guò)程中爆 int(雖然完全可以取1000)

/**
 * Created by Mauve on 3/29/2020.
 * Copyright © 2020 Mauve, All Rights Reserved
 */

#include <bits/stdc++.h>

using namespace std;

/**
 * 矩陣相乘
 * 最終結(jié)果耗時(shí)結(jié)果保存至
 * https://www.desmos.com/calculator/gl4tm5i1zu
 */

struct mat {
  unsigned row, col;

  mat(unsigned r, unsigned c) : row(r), col(c) {}

  virtual int &pos_ref(unsigned i, unsigned j) = 0;

  virtual int pos(unsigned i, unsigned j) const = 0;
};

struct base_mat;
struct sub_mat;

stack<sub_mat *> sub_data;

struct base_mat : mat {
  int *data;

  base_mat(unsigned r, unsigned c) : mat(r, c), data(new int[row * col]) {}

  ~base_mat() {
    delete[] data;
  }

  inline int &pos_ref(unsigned i, unsigned j) override {
    return *(data + i * col + j);
  }

  inline int pos(unsigned i, unsigned j) const override {
    return *(data + i * col + j);
  }
};

unsigned min_mul;

struct sub_mat : mat {
  mat *a, *b;
  bool is_add;
  unsigned offset_ai, offset_aj, offset_bi, offset_bj;

  explicit sub_mat(mat *data) : mat(data->row, data->col), a(data), b(nullptr),
                 is_add(false), offset_ai(0), offset_aj(0),
                 offset_bi(0), offset_bj(0) { sub_data.push(this); }

  sub_mat(mat *data, bool of_i, bool of_j) : mat(data->row >> 1u, data->col >> 1u), a(data), b(nullptr),
                        is_add(false), offset_ai(of_i ? data->row >> 1u : 0),
                        offset_aj(of_j ? data->col >> 1u : 0),
                        offset_bi(0), offset_bj(0) { sub_data.push(this); }

  inline int &pos_ref(unsigned i, unsigned j) override {
    assert(b == nullptr);
    return a->pos_ref(i + offset_ai, j + offset_aj);
  }

  inline int pos(unsigned i, unsigned j) const override {
    if (b == nullptr)
      return a->pos(i + offset_ai, j + offset_aj);
    return a->pos(i + offset_ai, j + offset_aj) + (is_add ? 1 : -1) * b->pos(i + offset_bi, j + offset_bj);
  }

  inline sub_mat *operator+(sub_mat &other) {
    auto res = new sub_mat(this);
    res->b = &other;
    res->is_add = true;
    return res;
  }

  inline sub_mat *operator-(sub_mat &other) {
    auto res = new sub_mat(this);
    res->b = &other;
    res->is_add = false;
    return res;
  }

  mat *operator*(sub_mat &other) {
    assert(col == other.row);
    auto res = new base_mat(row, other.col);
    if (col & 1u || row & 1u || col <= min_mul || row <= min_mul || other.col <= min_mul) {
      memset(res->data, 0, sizeof(int) * res->row * res->col);
      for (int k = 0; k < col; k++)
        for (int i = 0; i < row; ++i)
          for (int j = 0; j < other.col; ++j)
            res->pos_ref(i, j) += pos(i, k) * other.pos(k, j);
    } else {
      size_t sub_data_size = sub_data.size();
#define a(i, j) (*new sub_mat(this, i == 2 , j == 2))
#define b(i, j) (*new sub_mat(&other, i == 2 , j == 2))
      auto m1 = *(a(1, 1) + a(2, 2)) * *(b(1, 1) + b (2, 2));
      auto m2 = *(a(2, 1) + a(2, 2)) * b(1, 1);
      auto m3 = a(1, 1) * *(b(1, 2) - b(2, 2));
      auto m4 = a(2, 2) * *(b(2, 1) - b(1, 1));
      auto m5 = *(a(1, 1) + a(1, 2)) * b(2, 2);
      auto m6 = *(a(2, 1) - a(1, 1)) * *(b(1, 1) + b(1, 2));
      auto m7 = *(a(1, 2) - a(2, 2)) * *(b(2, 1) + b(2, 2));
#undef a
#undef b
      unsigned half_row = row >> 1u, half_col = col >> 1u;
#define m(t) (m##t->pos(i, j))
      // C11
      for (unsigned i = 0; i < half_row; ++i)
        for (unsigned j = 0; j < half_col; ++j)
          res->pos_ref(i, j) = m(1) + m(4) - m(5) + m(7);
      // C12
      for (unsigned i = 0; i < half_row; ++i)
        for (unsigned j = 0; j < half_col; ++j)
          res->pos_ref(i, j + half_col) = m(3) + m(5);
      // C21
      for (unsigned i = 0; i < half_row; ++i)
        for (unsigned j = 0; j < half_col; ++j)
          res->pos_ref(i + half_row, j) = m(2) + m(4);
      // C22
      for (unsigned i = 0; i < half_row; ++i)
        for (unsigned j = 0; j < half_col; ++j)
          res->pos_ref(i + half_row, j + half_col) = m(1) - m(2) + m(3) + m(6);
#undef m
      delete dynamic_cast<base_mat *>(m1);
      delete dynamic_cast<base_mat *>(m2);
      delete dynamic_cast<base_mat *>(m3);
      delete dynamic_cast<base_mat *>(m4);
      delete dynamic_cast<base_mat *>(m5);
      delete dynamic_cast<base_mat *>(m6);
      delete dynamic_cast<base_mat *>(m7);
      while (sub_data.size() > sub_data_size) {
        delete sub_data.top();
        sub_data.pop();
      }
    }
    return res;
  }
};

unsigned N = 2;

void solve() {
  cerr << "N = " << N << endl;
  base_mat a(N, N), b(N, N);
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j)
      cin >> a.pos_ref(i, j);
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j)
      cin >> b.pos_ref(i, j);

  for (int t = 1; t < min(10u, N); t += 3) {
    auto x = new sub_mat(&a), y = new sub_mat(&b);
    min_mul = t;

    auto time_1 = clock();
    auto z = *x * *y;
    auto time_2 = clock();

    cerr << "t = " << t << " time: " << double(time_2 - time_1) / CLOCKS_PER_SEC << endl;
    delete dynamic_cast<base_mat *>(z);
    while (!sub_data.empty()) {
      delete sub_data.top();
      sub_data.pop();
    }
  }

  auto x = new sub_mat(&a), y = new sub_mat(&b);
  min_mul = 10000;

  auto time_1 = clock();
  auto z = *x * *y;
  auto time_2 = clock();

  cerr << "tradition: " << double(time_2 - time_1) / CLOCKS_PER_SEC << endl;
  delete dynamic_cast<base_mat *>(z);
  while (!sub_data.empty()) {
    delete sub_data.top();
    sub_data.pop();
  }
  N *= 2;
  if (N >= 1000) exit(0);
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
#ifdef ACM_LOCAL
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
  long long test_index_for_debug = 1;
  char acm_local_for_debug;
  while (cin >> acm_local_for_debug && acm_local_for_debug != '~') {
    cin.putback(acm_local_for_debug);
    if (test_index_for_debug > 20) {
      throw runtime_error("Check the stdin!!!");
    }
    auto start_clock_for_debug = clock();
    solve();
    auto end_clock_for_debug = clock();
    cout << "Test " << test_index_for_debug << " successful" << endl;
    cerr << "Test " << test_index_for_debug++ << " Run Time: "
       << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
    cout << "--------------------------------------------------" << endl;
  }
#else
  solve();
#endif
  return 0;
}

到此這篇關(guān)于C++ Strassen算法代碼的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++ Strassen算法 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 定義vim配置文件vimrc用于c/c++編程

    定義vim配置文件vimrc用于c/c++編程

    vim作為L(zhǎng)inux下廣受贊譽(yù)的代碼編輯器,其獨(dú)特的純命令行操作模式可以很大程度上方便編程工作,通過(guò)自定義vim配置文件可以實(shí)現(xiàn)對(duì)vim功能的個(gè)性化設(shè)置。這篇文章主要介紹了定義vim配置文件vimrc,用于c/c++編程 ,需要的朋友可以參考下
    2018-10-10
  • C語(yǔ)言實(shí)現(xiàn)刮刮樂(lè)效果是示例代碼

    C語(yǔ)言實(shí)現(xiàn)刮刮樂(lè)效果是示例代碼

    這篇文章主要為大家詳細(xì)介紹了如何C語(yǔ)言模擬實(shí)現(xiàn)刮刮樂(lè)的效果,只要按下鼠標(biāo)左鍵并移動(dòng)就可以刮開(kāi)刮卡層,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2023-01-01
  • 如何用矩形法(梯形法)求定積分

    如何用矩形法(梯形法)求定積分

    思路就是將積分區(qū)間劃分成n等份,然后將這n等份近似看成矩形(或梯形),然后對(duì)所有的矩形(或梯形)的面積進(jìn)行求和
    2013-09-09
  • C/C++ 獲取自身IP與域名片段的示例代碼

    C/C++ 獲取自身IP與域名片段的示例代碼

    這篇文章主要介紹了C/C++ 獲取自身IP與域名片段的示例代碼,幫助大家更好的理解和學(xué)習(xí)C/C++編程,感興趣的朋友可以了解下
    2020-10-10
  • C語(yǔ)言開(kāi)發(fā)實(shí)現(xiàn)貪吃蛇游戲

    C語(yǔ)言開(kāi)發(fā)實(shí)現(xiàn)貪吃蛇游戲

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言開(kāi)發(fā)實(shí)現(xiàn)貪吃蛇游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-07-07
  • C++實(shí)現(xiàn)LeetCode(7.翻轉(zhuǎn)整數(shù))

    C++實(shí)現(xiàn)LeetCode(7.翻轉(zhuǎn)整數(shù))

    這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(7.翻轉(zhuǎn)整數(shù)),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-07-07
  • C語(yǔ)言楊氏矩陣查找算法實(shí)例講解

    C語(yǔ)言楊氏矩陣查找算法實(shí)例講解

    楊氏矩陣是一個(gè)數(shù)字矩陣,矩陣的每一行從左到右一次遞增,矩陣從上到下遞增,在這樣的矩陣中查找一個(gè)數(shù)字是否存在。時(shí)間復(fù)雜度小于O(N),有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步早日升職加薪
    2022-09-09
  • C語(yǔ)言手撕一個(gè)Hash表(HashTable)實(shí)例代碼

    C語(yǔ)言手撕一個(gè)Hash表(HashTable)實(shí)例代碼

    哈希表(HashTable)是一種非常重要的數(shù)據(jù)結(jié)構(gòu),它可以在常量時(shí)間內(nèi)進(jìn)行插入、查找和刪除操作,下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言手撕一個(gè)Hash表(HashTable)的相關(guān)資料,需要的朋友可以參考下
    2023-03-03
  • 使用C語(yǔ)言的fork()函數(shù)在Linux中創(chuàng)建進(jìn)程的實(shí)例講解

    使用C語(yǔ)言的fork()函數(shù)在Linux中創(chuàng)建進(jìn)程的實(shí)例講解

    這篇文章主要介紹了使用C語(yǔ)言的fork()函數(shù)在Linux中創(chuàng)建進(jìn)程的實(shí)例講解,fork在父進(jìn)程下創(chuàng)建出的子進(jìn)程可以與父進(jìn)程一起來(lái)多進(jìn)程運(yùn)行同一個(gè)程序,需要的朋友可以參考下
    2016-06-06
  • 詳解C語(yǔ)言中的指針與數(shù)組的定義與使用

    詳解C語(yǔ)言中的指針與數(shù)組的定義與使用

    這篇文章主要介紹了C語(yǔ)言中的指針與數(shù)組的定義與使用,本文給大家介紹的非常詳細(xì),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2019-12-12

最新評(píng)論