staticval_t&val(element_t& el) { return std::get<2>(el); }
staticconstrow_t NONEXISTENT_ROW = (row_t)-1;
staticconstcol_t NONEXISTENT_COL = (col_t)-1;
};
static inline bool is_this_coord(constelement_t& el, int r, int c)
{
returnelement_traits::row(el) == static_cast<element_traits::row_t>(r) &&
element_traits::col(el) == static_cast<element_traits::col_t>(c);
}
returnelement_traits::row(el) <static_cast<element_traits::row_t>(r) ||
(element_traits::row(el) == static_cast<element_traits::row_t>(r) &&
element_traits::col(el) <static_cast<element_traits::col_t>(c));
}
static inline bool is_same(constelement_t& a, constelement_t& b)
{
returnis_this_coord(b, (int)element_traits::row(a), (int)element_traits::col(a));
}
bool operator==(constelement_t& a, constelement_t& b)
{
returnis_same(a, b);
}
bool operator>(constelement_t& a, constelement_t& b)
{
returnis_further_coord(b, element_traits::row(a), element_traits::col(a));
}
Исходный текст модуля алгоритмов sp_m_algo.h
#pragma once
#include <assert.h>
#include <algorithm>
voidsp_mm_add(coo_mtx& a, coo_mtx& b, coo_mtx& c)
{
assert(a.nrows == b.nrows);
assert(a.ncols == b.ncols);
if (!a.is_empty()) {
a.sort();
a.check();
}
if (!b.is_empty()) {
b.sort();
b.check();
}
assert(c.is_empty());
c.nrows = a.nrows;
c.ncols = a.ncols;
if (a.is_empty()) {
c.elems.insert(c.elems.end(), b.elems.begin(), b.elems.end());
c.nnz = (int)c.elems.size();
return;
}
if (b.is_empty()) {
c.elems.insert(c.elems.end(), a.elems.begin(), a.elems.end());
c.nnz = (int)c.elems.size();
return;
}
c.merge(a, b);
c.nrows = a.nrows;
c.ncols = a.ncols;
c.nnz = (int)c.elems.size();
size_tnremoved = 0;
auto it2 = c.elems.begin() + 1;
for (auto it = c.elems.begin(); it != c.elems.end(); ++it, ++it2) {
if (it2 != c.elems.end()) {
if (is_same(*it, *it2)) {
auto& a = *it;
auto& b = *it2;
element_traits::val(a) += element_traits::val(b);
element_traits::row(b) = element_traits::NONEXISTENT_ROW;
element_traits::col(b) = element_traits::NONEXISTENT_COL;
nremoved++;
}
}
}
if (nremoved) {
c.remove_nonexistents();
c.check();
}
}
voidsp_m_transpose(coo_mtx& a)
{
for (auto it = a.elems.begin(); it != a.elems.end(); ++it) {
auto r = static_cast<element_traits::row_t>(element_traits::col(*it));
auto c = static_cast<element_traits::col_t>(element_traits::row(*it));
element_traits::row(*it) = r;
element_traits::col(*it) = c;
}
std::swap(a.nrows, a.ncols);
a.sort(true);
}
voidsp_mm_multiply(coo_mtx& a, coo_mtx& b, coo_mtx& c)
{
assert(a.ncols == b.nrows);
assert(c.is_empty());
if (a.is_empty() || b.is_empty())
return;
a.sort();
a.check();
b.sort();
b.check();
c.nrows = a.nrows;
c.ncols = b.ncols;
sp_m_transpose(b);
autoa_it = a.elems.begin();
autob_it = b.elems.begin();
autoa_row_start_it = a.elems.begin();
element_traits::row_ttarget_row = element_traits::row(*a_it);
element_traits::col_ttarget_col = static_cast<element_traits::col_t>(element_traits::row(*b_it));
boolgo_to_next_row = false;
element_traits::val_tacc = 0;
booltarget_col_changed = false;
boolacc_updated = false;
for (;;) {
if (b_it == b.elems.end()) {
go_to_next_row = true;
b_it = b.elems.begin();
target_col_changed = true;
}
if (target_col != static_cast<element_traits::col_t>(element_traits::row(*b_it))) {
target_col_changed = true;
}
if (target_col_changed) {
if (acc_updated) {
c.add(element_t(target_row, target_col, acc), false);
acc_updated = false;
}
target_col = static_cast<element_traits::col_t>(element_traits::row(*b_it));
acc = 0;
while (target_row == element_traits::row(*a_it)) {
++a_it;
if (a_it == a.elems.end())
break;
}
}
if (a_it == a.elems.end() || target_row != element_traits::row(*a_it)) {
if (go_to_next_row) {
if (a_it == a.elems.end())
break;
target_row = element_traits::row(*a_it);
a_row_start_it = a_it;
go_to_next_row = false;
}
else {
a_it = a_row_start_it;
if (!target_col_changed) {
while (target_col == static_cast<element_traits::col_t>(element_traits::row(*b_it))) {
++b_it;
if (b_it == b.elems.end())
break;
}
if (acc_updated) {
c.add(element_t(target_row, target_col, acc), false);
acc_updated = false;
}
target_col = static_cast<element_traits::col_t>(element_traits::row(*b_it));
acc = 0;
}
}
}
target_col_changed = false;
if (b_it == b.elems.end())
continue;
auto c1 = element_traits::col(*a_it);
auto c2 = element_traits::col(*b_it);
if (c1 == c2) {
acc += element_traits::val(*a_it) * element_traits::val(*b_it);
acc_updated = true;
++b_it;
++a_it;
}
else if (c1 > c2) {
++b_it;
}
else {
++a_it;
}
}
sp_m_transpose(b);
}
Курсовой структуры
В настоящее время объектно-ориентированное программирование (ООП) является доминирующим стилем при создании больших программ и программных систем. Процедурно-ориентированное программирование, широко использовавшееся до появления ООП, обычно позволяет создавать более эффективные в вычислительном отношении реализации приложений, что является существенным фактором при разработке систем реального времени. На практике эти два стиля программирования часто используются совместно, позволяя варьировать степень их применения в программах.
Использование объектно-ориентированного (ОО) подхода при разработке программного обеспечения (ПО) позволяет преодолеть естественную сложность разрабатываемого ПО, упростить процесс отладки и последующего сопровождения, расширения и переноса ПОна другие платформы.
В данной курсовой работе в процессе проектирования и реализации конкретного приложения используются комбинация процедурно-ориентированного и объектно-ориентированного подхода и проводится сравнительный анализ их свойств и возможностей применения.
Разрежённая матрица -- это матрица с преимущественно нулевыми элементами. В противном случае, если бомльшая часть элементов матрицы ненулевые, матрица считается плотной.
Огромные разрежённые матрицы часто возникают при решении таких задач, как интегрирование систем дифференциальных уравнений в частных производных.
При хранении и преобразовании разрежённых матриц в компьютере бывает полезно, а часто и необходимо, использовать специальные алгоритмы и структуры данных, которые учитывают разрежённую структуру матрицы. Операции и алгоритмы, применяемые для работы с обычными, плотными матрицами, применительно к большим разрежённым матрицам работают относительно медленно и требуют значительных объёмов памяти. Однако разрежённые матрицы могут быть легко сжаты путём записи только своих ненулевых элементов, что снижает требования к компьютерной памяти.
Один из возможных вариантов хранения: координатный, часто обозначаемый в литературе аббревиатурой «COO». В базовом варианте этого формата, каждому ненулевому элементу матрицы соответствует триплет из двух координат (номера строки и номера столбца) и значения элемента, а триплеты хранятся в виде простого одномерного массива с произвольным доступом.
Если значение элемента представлено числом с плавающей точкой, а координаты элемента - целыми числами, то общий расход памяти соответствует числу ненулевых элементов (NNZ), умноженному на объём памяти, требуемый для хранения значения и координат. Если для хранения координат используются 32-битные целые, а для хранения значения 32-битное число с плавающей точкой (одинарной точности), то суммарный расход памяти равен в байтах: 3 * 4 * NNZ. В этом случае только треть памяти используется для хранения собственно данных, а две трети - для хранения координат. Вообще говоря, это не самый экономичный с точки зрения использования памяти формат хранения разреженной матрицы, так как известны форматы (например, CSR), которые имеют более экономичные характеристики. Однако, работа с координатным форматом (COO) заметно проще: реализация базовых алгоритмов работы с матрицами оказывается не такой сложной, как для форматов типа CSR.
Дополнительный недостаток формата COO -- доступ к произвольному элементу за O(NNZ) или O(log(NNZ)), где NNZ -- число ненулевых элементов в матрице. Такая скорость достигается либо поиском по индексу полным перебором для неупорядоченного варианта хранения элементов или бинарным поиском по индексу для хранения в виде отсортированного массива. Однако при реализации базовых алгоритмов работы с матрицами можно найти такие пути, которые позволяют не осуществлять доступы к произвольному элементу, тем самым устранив эту затратную операцию. Это возможно, например, если всё время хранить ненулевые элементы матрицы в отсортированном по координатам виде. Порядок сортировки по координатам должен быть таким, что при сравнении координат вначале сравнивается номер строки, а при равенстве - номер столбца.
Операция сортировки после произвольной модификации матрицы имеет сложность классических вариантов сортировки, то есть O(NNZ*log(NNZ)), где NNZ - число ненулевых элементов в матрице. В целом, можно избежать выполнения этой операции вообще в том случае, если формирование матрицы сразу осуществляется в требуемом порядке по координатам. Базовые алгоритмы работы с матрицами также можно постараться построить так, чтобы на их выходе автоматически получалась правильно упорядоченная матрица.