& Quot; Расщепление & Quot; матрица в постоянном времени
Я пытаюсь реализовать алгоритм Штрассена для умножения матриц в C ++, и я хочу найти способ разбить две матрицы на четыре части в постоянное время. Вот текущий способ, которым я делаю так:
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
A11[i][j] = a[i][j];
A12[i][j] = a[i][j+n];
A21[i][j] = a[i+n][j];
A22[i][j] = a[i+n][j+n];
B11[i][j] = b[i][j];
B12[i][j] = b[i][j+n];
B21[i][j] = b[i+n][j];
B22[i][j] = b[i+n][j+n];
}
}
Этот подход, очевидно, O (n ^ 2), и он добавляет n ^ 2 * log (n) во время выполнения, как он вызывается для каждого рекурсивного вызова.
Кажется, что способ сделать это в постоянное время — создать указатели на четыре подматрицы, а не копировать значения, но мне трудно разобраться, как создать эти указатели. Любая помощь будет оценена.
Решение
Не думайте о матрицах, думайте о матричных представлениях.
Матричное представление имеет указатель на буфер T, ширина, высота, смещение и шаг между столбцами (или строками).
Мы можем начать с типа представления массива.
template<class T>
struct array_view {
T* b = 0; T* e = 0;
T* begin() const{ return b; }
T* end() const{ return e; }
array_view( T* s, T* f ):b(s), e(f) {}
array_view( T* s, std::size_t l ):array_view(s, s+l) {}
std::size_t size() const { return end()-begin(); }
T& operator[]( std::size_t n ) const { return *(begin()+n); }
array_view slice( std::size_t start, std::size_t length ) const {
start = (std::min)(start, size());
length = (std::min)(size()-start, length);
return {b+start, length};
}
};
Теперь наш матричный вид:
temlpate<class T>
struct matrix_view {
std::size_t height, width;
std::size_t offset, stride;
array_view<T> buffer;
// TODO: Ctors
// one from a matrix that has offset and stirde set to 0.
// another that lets you create a sub-matrix
array_view<T> operator[]( std::size_t n ) const {
return buffer.slice( offset+stride*n, width ); // or width, depending on if row or column major
}
};
Теперь ваш код работает на matrix_viewс, а не матрицы.
Другие решения
Вы могли бы создать класс подматрицы, который содержит местоположение в родительской матрице меньшей матрицы, которую вы хотите использовать. В основном это то, что у вас уже есть для вашей матрицы, за исключением того, что вам нужно хранить начальные индексы для строки и столбцов, а затем смещать индексирование этими смещениями. Если все сделано правильно, основная / корневая матрица будет подматрицей с полной матрицей в качестве границ.