/itmo-cpp-opt-matrix

Primary LanguageC++

Задание на лабораторную работу №4 про курс «Программирование на С++». Работа с разреженными векторами и матрицами.

В том случае, когда подавляюще большое количество элементов вектора или матрицы равны нулям для их хранения имеет смысл использовать структуры данных, позволяющие существенно экономить память, за счёт того, что нули можно не хранить.

Задание

Разработать шаблонные классы для хранения разреженных вектора и 2D матрицы для чего:

  • Предложить структуры данных для хранения значений исходных векторов и матриц. (подсказка: использование хеш-таблиц — хорошая идея),
  • рассмотрите необходимость поддержки собственных итераторов;
  • Реализовать набор унарных и бинарных операций для вектора и матриц;
    • транспонирование,
    • сложение,
    • произведение векторов (вспоминаем линейную алгебру),
    • обращение матрицы,
    • возведение матрицы в степень
    • подумать на тему относительно того, как решить вопрос с возведением в степень т. е. в степень можно возводить только квадратные матрицы,
    • произведение вектора и матрицы.
    • Реализовать поэлементные операции для элементов векторов и матриц
      • арифметические операции со скалярной величиной,
      • поэлементное возведение в степень.
  • Провести сравнение скоростей обработки предложенного вами способа хранения и
  • обработки разреженных матриц и выполнение тех же действий над векторами и матрицами,
  • хранящимся с помощью стандартного контейнера vector.
  • Результаты работы оформить в виде отчета или файла readme если код будет на Git.

Необходимость поддержки собственных итераторов

Было принято решение не использовать итераторы, так как они добавляют дополнительные накладные расходы на управление состоянием и памятью, что может снизить общую производительность системы, особенно при работе с большими объемами данных.

Решение о вопросе с возведением матрицы в степень

Было принято решение "выбрасывать" исключение когда происходит попытка возвести неквадратную матрицу в степень для минимизации количества абстракций и боилерплейт кода.

Результат работы программы

=== Matrix Transpose ===
Original matrix:
1 3 
2 25 
Transposed matrix:
1 2 
3 25 
=== Matrix Inverse ===
Original matrix:
1 3 
2 4 
Inverse matrix:
-2 1.5 
1 -0.5 
=== Vector add ===
Vector 1:
1 2 
Vector 2:
3 4 
Vector addition:
4 6 
=== Vector dot product ===
Vector 1:
1 2 
Vector 2:
3 4 
Dot product: 11
=== Test with std matrix ===
Matrix Size 300x300
HashMap Matrix        1091ms
Std Vector Matrix     14022ms