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

[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

[visualdoj]

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

[rootkid]

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

[neatfires]

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

[shredder_by]

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

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

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

[rootkid]

знаю, это не подходит

[visualdoj]

Алгоритмически ничего нового тут не придумать. Аппаратно стоит копать в сторону SSE, параллельных вычислений на GPU и т.д.