логические операции над матрицами

[rootkid]

Всем привет, подскажите, пожалуйста, есть ли такая вещь как subj? eg:

0 1 0
1 0 0
0 1 0
&
0 1 0
1 1 0
1 0 0
=
0 1 0
1 0 0
0 0 0

т.е.

A&B=C

интересует более-менее академический подход и алгоритмы луче полного перебора, спасибо.

Comments

[alex_djk1]

А что вы пытаетесь найти? Можно ли так делать? Оптимальные способы? Еще что-то?

[rootkid]

пытаюсь найти результирующую матрицу, каждый элемент которой получается в результате логической операции между двумя данными

[alex_djk1]

Не хочу казаться капитаном очевидность, но может просто к одинаковым элементам (в плане позиции) применить операцию?

[rootkid]

ну да, но придётся перебрать все элементы, а хочется иметь некий профит за счёт того, что данные организованы в матрицу

[visualdoj]

Пример кажется нерепрезентативным, в нём взаимное расположение битов не влияет на результат, т.е. действие чисто поразрядное, а потому не отличается от аналогичных действий просто над массивом бит.

[rootkid]

возможно, но если отвлечься от конкретного примера, в какую сторону можно копать A&B=C ?

[neatfires]

Если отвлечься от конкретного примера, то выходит общий случай. В общем случае матрица отличается от массива бит только тем, что число ее бит делится на m и на n. Поэтому единственная возможность оптимизировать - это как раз используя специфику конкретного случая. В вашем примере такая специфика не просматривается. Примерно вот что хотел сказать товарищ выше.

[shredder_by]

не надо в эту сторону копать.

мой не первой свежести процессор теоретически способен складывать-умножать порядка 3ггц * 64бит = 192 гигабит в секунду. проблема только в том, как эти гигабиты в него скормить. так, скорость чтения с хдд в лучшем случае на два порядка меньше. в итоге процессор 1 такт складывает битики, потом 99 тактов ждет следующей порции.

вот если ваш источник единиц и нулей будет отдавать их в сжатом виде, это разгрузит ввод-вывод и позволит более эффективно использовать цпу.

[oswid]

Правильно ли я понял, что:
1) Все элементы матрицы хранятся в памяти (а не, например, вычисляются на лету)
2) Операция, которую Вам необходимо реализовать - поэлементная. Т.е. C(i,j) = f(A(i,j), B(i,j)) ?

[rootkid]

1. нет. каждый элемент можно вычислить в зависимости от позиции в строке и столбце, т.е. можно хранить и/или вычислять.
2. да, но поэлементно не хочется, т.к. очень долго

[oswid]

Тогда Вашу задачу можно решить так, наверное (на C++):
1) Матрица у Вас - это класс MatrixFunc
2) MatrixFunc - это абстрактный класс с чистой виртуальной функцией eval(int i, int j). Элементы нигде не хранятся.
3) У Вас есть какие-то собственные реализации этого класса ("каждый элемент можно вычислить в зависимости от позиции в строке и столбце")
4) Вы делаете реализацию LogicBinaryMatrixFunc, которая в качестве конструктора принимает пару объектов класса MatrixFunc и объект класса std::binary_function. Элементарным образом реализовываете функцию eval в классе LogicBinaryMatrixFunc.
5) По вкусу добавьте операторы &, | для класса MatrixFunc
6) Аналогичным образом реализуйте класс LogicUnaryMatrixFunc

[pphantom]

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

[urod]

+1

[major_m]

Можно еще раз сформулировать, есть ли какие-то ограничения на тип матриц. Пермутация -- это перестановочная матрица? Почему тогда пример так странно выглядит?

[rootkid]

"пермутация"- аргумент, который был призван убедить собеседника в том, что речь идёт о матрице, а не о векторе, в том смысле, что элементы связаны между собой зависимостью(не важно какой), но это не перестановочная матрица, а сам вопрос касался возможности логических операций(если это практикуется) над любой матрицей A&B=C и известными алгоритмами оптимизации по аналогии с умножением матриц.

[sassa_nf]

в отличие от умножения матриц, сложность здесь MxN - линейная от количества клеток. куда уж проще-то?

[rootkid]

но ведь для умножения открыли ещё более выгодные алгоритмы, может и в этом случае кто знает что такое