Дана прямоугольная матрица из целых чисел размера M×N, расположенная в памяти построчно в виде непрерывного линейного массива. Написать программу, которая транспонирует эту матрицу in place, используя дополнительную память не более O(max(M,N)).
Бонус: написать программу, которая поворачивает блок целых чисел размера M×N×K in place вокруг псевдо-диагонали, состоящей из элементов с индексами (0,0,0), (1,1,1), (2,2,2), ..., чтобы получился блок K×M×N, используя дополнительную память не более O(max(M,N,K)).
Можно ли улучшить эти алгоритмы, чтобы использовать дополнительную память не более O(log(max(M,N))) и O(log(max(M,N,K))), соответственно?
Здравствуйте, nikov, Вы писали:
N>Дана прямоугольная матрица из целых чисел размера M×N, расположенная в памяти построчно в виде непрерывного линейного массива. Написать программу, которая транспонирует эту матрицу in place, используя дополнительную память не более O(max(M,N)).
Без указания платформы задача выглядит несколько странно. CPU, много CPU, GPU? Там же принципиально разные алгоритмы, насколько помню.
Здравствуйте, nikov, Вы писали:
N>Дана прямоугольная матрица из целых чисел размера M×N, расположенная в памяти построчно в виде непрерывного линейного массива. Написать программу, которая транспонирует эту матрицу in place, используя дополнительную память не более O(max(M,N)).
В чем собственно трудность?
Если поменять функцию доступа к элементам то вообще никакой работы не надо производить
get(i,j)=mtx(i*M+j)
get_tr=get(j,i)
Вариант без затрат по памяти
#include <stdio.h>
int step(int i,int m,int n) { return (i%n)*m+(i/n); }
int need(int i,int m,int n) {
int k=i;
do {
k=step(k,m,n);
if (k<i) return 0;
} while(k!=i);
return 1;
}
void tr(int *x,int m,int n) {
int i,j,k,w,v,mn=m*n;
for(i=1;i<mn;i++) {
if (!need(i,m,n)) continue;
j=step(k=i,m,n); w=x[k];
while(i!=j) {
v=w; w=x[j]; x[j]=v;
j=step(k=j,m,n);
}
x[i]=w;
}
}
void show(int *x,int m,int n,int dm,int dn) {
int i,j;
for(i=0;i<m;i++) {
for(j=0;j<n;j++) {
printf("%3d",x[i*dm+j*dn]);
}
printf("\n");
}
}
int main(int argc,char** argv) {
enum { M=3, N=7 };
int i,x[M*N];
for(i=0;i<M*N;i++) x[i]=i;
show(x,M,N,N,1);printf("\n");
show(x,N,M,1,N);printf("\n");
tr(x,M,N);
show(x,N,M,M,1);printf("\n");
return 0;
}
N>Бонус: написать программу, которая поворачивает блок целых чисел размера M×N×K in place вокруг псевдо-диагонали, состоящей из элементов с индексами (0,0,0), (1,1,1), (2,2,2), ..., чтобы получился блок K×M×N, используя дополнительную память не более O(max(M,N,K)).
Меняем функцию доступа
get_rot(i,j,k)=get(k,i,j)
Со сдвигом индексов примерно так же как и с транспонированием, только длиннее.
N>Можно ли улучшить эти алгоритмы, чтобы использовать дополнительную память не более O(log(max(M,N))) и O(log(max(M,N,K))), соответственно?
До, но работать будут медленнее.
Здравствуйте, nikov, Вы писали:
N>Дана прямоугольная матрица из целых чисел размера M×N, расположенная в памяти построчно в виде непрерывного линейного массива. Написать программу, которая транспонирует эту матрицу in place, используя дополнительную память не более O(max(M,N)).
N>Бонус: написать программу, которая поворачивает блок целых чисел размера M×N×K in place вокруг псевдо-диагонали, состоящей из элементов с индексами (0,0,0), (1,1,1), (2,2,2), ..., чтобы получился блок K×M×N, используя дополнительную память не более O(max(M,N,K)).
N>Можно ли улучшить эти алгоритмы, чтобы использовать дополнительную память не более O(log(max(M,N))) и O(log(max(M,N,K))), соответственно?
Ну раз у нас жёсткие ограничения на память, то можем расслабиться в вопросах времени.
За квадратное время (MN)^2 и (MNK)^2 соответственно это делается очень просто.
1) напишем функцию, возвращающую траекторию обменов для транспонирования
2) бежим строго последовательно по элементам массива
3) для каждого элемента
3.1) делаем сухой прогон траектории; если во время сухого прогона встретился какой-то уже пройденный элемент (с меньшим индексом, то есть) — пропускаем следующий шаг
3.2) выполняем обмены по траектории
Из-за 3.1 мы делаем кучу лишней работы и получаем квадратное время.
Зато память O(1).
Здравствуйте, Кодт, Вы писали:
К>Из-за 3.1 мы делаем кучу лишней работы и получаем квадратное время.
Не так уж моного лишней работы, если взглянуть на реализацию то время субквадратичное. К>Зато память O(1).
Здравствуйте, kov_serg, Вы писали:
К>>Из-за 3.1 мы делаем кучу лишней работы и получаем квадратное время. _>Не так уж моного лишней работы, если взглянуть на реализацию то время субквадратичное. К>>Зато память O(1).
Насчёт субквадратичности есть большие сомнения.
Вот, допустим, размеры такие удачные (что-то по мотивам взаимной простоты?), что в матрице есть ровно три цикла: два вырожденных (0,0) и (M-1,N-1) и один здоровенный по всем остальным клеткам.
Мы с первого же выстрела транспонируем всю матрицу, после чего для каждой оставшейся клетки делаем забег по маршруту. Очевидно, что с каждой точки маршрута до финиша — в сумме получается квадрат.
Здравствуйте, nikov, Вы писали:
N>Дана прямоугольная матрица из целых чисел размера M×N, расположенная в памяти построчно в виде непрерывного линейного массива. Написать программу, которая транспонирует эту матрицу in place, используя дополнительную память не более O(max(M,N)).
В любом случае, нужно будет сделать M*N-2 перемещений.
Сэкономить можно только на сухих прогонах в поисках циклов. Есть тут пара задумок...
N>Можно ли улучшить эти алгоритмы, чтобы использовать дополнительную память не более O(log(max(M,N))) и O(log(max(M,N,K))), соответственно?
В чём суть улучшения, если по первому условию у нас есть O(p), где p=max(M,N), а по второму — добавляем к этому с барского плеча O(log(p)) ? O(p)+O(log(p)) = O(p).
Или тут опечатка-оговорка?
Здравствуйте, Кодт, Вы писали:
К>Мы с первого же выстрела транспонируем всю матрицу, после чего для каждой оставшейся клетки делаем забег по маршруту. Очевидно, что с каждой точки маршрута до финиша — в сумме получается квадрат.
Нужен детектор траекторий. Возможно, есть закономерность.
Нарисуйте траектории на картинке. Может, удастся заметить чего.
К>Сэкономить можно только на сухих прогонах в поисках циклов. Есть тут пара задумок...
Задумка первая. Скользящее окно проверок.
Наивный алгоритм выглядит так.
Встали на клетку i. Сделали проверку, не входит ли она в старый цикл. И если не входит, то пробежали по новому циклу.
Встали на клетку i+1. Сделали проверку...
А теперь давайте заведём s = O(max(N,M)) булевых признаков, отвечающих на вопрос: встречался ли индекс i+0, i+1, ..., i+s-1 в старых циклах.
1) обнулили признаки ("нет полной уверенности, что это не встречалось"; в самом начале, т.е. для i<s — "есть полная уверенность, что это не встречалось")
2) если признак для i — "ой, уже встретилось", то сразу пропускаем (идём к пункту 5)
3) если "нет полной уверенности" — делаем сухой прогон и, если вдруг получим индекс j из [i, i+s), то смотрим:
— "ой уже встретилось" — сразу останавливаемся
— "нет полной уверенности" — помечаем признак для j как "ой" и бежим дальше
4) если сухой прогон был успешный, то выполняем перестановки.
5) после этого сдвигаем окно признаков, — для i больше не нужно, [0..i] "точно уже встречалось", а [i+s] становится "нет полной уверенности".
Задумка вторая. Параллельно-блочная работа.
Нарежем массив на блоки по s.
Для каждого элемента в блоке — сперва выполняем сухой прогон, который считается неуспешным, если попадает в предыдущие блоки, и условно-успешным, — если в этот блок (необязательно в этот же элемент). Запоминаем, в какой именно.
Если условно-успешный элемент приземлился на неуспешный, — помечаем его как неуспешный. Распространяем неуспешность по блоку далее, пока у нас не останутся безусловно успешные.
Для них выполняем переносы. Тут либо надо распараллеливать, одновременно освободив весь блок, либо действовать последовательно, но аккуратно учитывать, что один цикл может проходить через этот блок многажды.
Здравствуйте, T4r4sB, Вы писали:
TB>Правка: во всех траекториях сохраняются общие делители с m*n-1. Может, это зацепка?
А, точно мы же индекс an+b переводим в a+bm. Это ж то же самое, что умножить на m, получив amn+mb и вычесть a*(nm-1), получив a+bm. То есть умножаем на m, берём остаток по модулю mn-1 (для самого mn-1 формула не работает).
Это лишь траектории умножения на m в кольце вычетов по модулю mn-1. Про эти траектории вроде бы всё исследовано, надо вспомнить.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, kov_serg, Вы писали:
К>>>Из-за 3.1 мы делаем кучу лишней работы и получаем квадратное время. _>>Не так уж моного лишней работы, если взглянуть на реализацию то время субквадратичное. К>>>Зато память O(1).
К>Насчёт субквадратичности есть большие сомнения.
Сам в шоке, в худшем случае грубая оценка по времени (до милиона элементов) ~O( n*log(n) ), в лучшем порядка ~O(n)
Здравствуйте, kov_serg, Вы писали:
К>>Насчёт субквадратичности есть большие сомнения. _>Сам в шоке, в худшем случае грубая оценка по времени (до милиона элементов) ~O( n*log(n) ), в лучшем порядка ~O(n)
Ммм. Ну да, точно. Отлуп делается не по достижению финиша, а по заглядыванию себе за спину.
Здравствуйте, Кодт, Вы писали:
N>>Можно ли улучшить эти алгоритмы, чтобы использовать дополнительную память не более O(log(max(M,N))) и O(log(max(M,N,K))), соответственно?
К>В чём суть улучшения, если по первому условию у нас есть O(p), где p=max(M,N), а по второму — добавляем к этому с барского плеча O(log(p)) ? O(p)+O(log(p)) = O(p). К>Или тут опечатка-оговорка?
Дополнительную не по отношению к первому варианту программы, а к памяти M*N, в которой находятся входные данные.
Здравствуйте, kov_serg, Вы писали:
_>Здравствуйте, Кодт, Вы писали:
К>>Здравствуйте, kov_serg, Вы писали:
К>>>>Из-за 3.1 мы делаем кучу лишней работы и получаем квадратное время. _>>>Не так уж моного лишней работы, если взглянуть на реализацию то время субквадратичное. К>>>>Зато память O(1).
К>>Насчёт субквадратичности есть большие сомнения. _>Сам в шоке, в худшем случае грубая оценка по времени (до милиона элементов) ~O( n*log(n) ), в лучшем порядка ~O(n)
Перекуём баги на фичи!
