03/04/2025 11:36:56

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2766. Порядок вычислений

Ограничения: время – 250ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Сравнить время умножения матриц размером $1000 xx 1000$ , меняя порядок циклов всеми 6 способами для уровня оптимизации -O3

#include <vector>
#include <iostream>
#include <chrono>
#include <utility>
#include <stdexcept>
using namespace std;

class Matrix {
  int n,m;
  vector<vector<double>> data;
public:
  Matrix(int n, int m):n(n),m(m),data(n,vector<double>(m,0.0)) {}
  friend Matrix operator*(const Matrix &a, const Matrix &b);
  pair<int,int> size() const { return {n,m}; }
};
Matrix operator*(const Matrix &a, const Matrix &b) {
  if (a.m!=b.n) throw runtime_error("неверные размеры");
  Matrix c(a.n,b.m);
  for (int i = 0; i < c.n; i++)
      for (int j = 0; j < c.m; j++)
        for (int k = 0; k < a.m; k++)
            c.data[i][j]+=a.data[i][k]*b.data[k][j];
  return c;
}
int main()
{
  Matrix a(1000,1000),b(1000,1000);
  auto start = std::chrono::high_resolution_clock::now();
  Matrix c=a*b;
  auto end = std::chrono::high_resolution_clock::now();
  std::cout << "ijk " << std::chrono::duration_cast<std::chrono::microseconds>(end-start).count() << "\n";
}

В качестве решения отправить текстовый файл с таблицей, в которой будет указан порядок выполнения циклов в порядке увеличения времени и время выполнения в мкс.

Пример текстового файла

ijk 100000
ikj 100001
jik 100002
jki 100003
kij 100004
kji 200000