3

行列を右循環シフトする効率的な方法を知っている人はいますか? ところで、行列はバイナリですが、非バイナリ行列を解く方法も問題ありません。

現在、行列の行に循環配列を実装し、シフト操作が必要なときはいつでも各行を更新することを考えています。

私が検討していた別の方法は、ベクトルで表される (行列の) 列へのポインターのベクトルを実装し、シフト操作が発生したときにそれらを交換することでした。

例えば

1 2 3
4 5 6
7 8 9

右シフト

3 1 2
6 4 5
9 7 8

マトリックスも下にシフトする必要がある場合、これらすべてのソリューションで別の問題が発生します。両方の操作を効率的に実装することは、完全に私を超えています。

シフトダウン

9 7 8
3 1 2
6 4 5
4

7 に答える 7

2

このようなものは、おそらく、

class matrix {
    std::vector<bool> elements;
    int rows, cols, row_ofs, col_ofs;

    std::size_t index(int r, int c) {
        r = (r + row_ofs) % rows;
        c = (c + col_ofs) % cols;
        return std::size_t(r)*cols + c; // row major layout
    }
public:
    matrix() : rows(0), cols(0) {}
    matrix(int r, int c)
    : elements(std::size_t(r)*c), rows(r), cols(c) {}

    int num_rows() const { return rows; }
    int num_cols() const { return cols; }

    std::vector<bool>::reference operator()(int r, int c) {
        return elements.at(index(r,c));
    }

    bool operator()(int r, int c) const {
        return elements.at(index(r,c));
    }

    void rotate_left()  { col_ofs = (col_ofs+1     ) % cols; }
    void rotate_right() { col_ofs = (col_ofs+cols-1) % cols; }
    void rotate_up()    { row_ofs = (row_ofs+1     ) % rows; }
    void rotate_down()  { row_ofs = (row_ofs+rows-1) % rows; }
};

(未テスト)

編集:ここに代替手段があります:内部で std::deque<std::deque<T> > を使用します。;-) はい、ランダムアクセスをサポートしています。両端キューはリストではありません。さらに、モジュロ演算を気にする必要はもうありません。

于 2009-09-25T19:17:45.057 に答える
1

私が検討していた別の方法は、ベクトルで表される (行列の) 列へのポインターのベクトルを実装し、シフト操作が発生したときにそれらを交換することでした。

列に対してこれを行い（水平シフト）、行に対して別のベクトルを実行します（垂直シフト）。

また、Matrix オブジェクトを作成して、「実際の」行列とこれら 2 つのベクトルをカプセル化します。オブジェクトのゲッター/セッターは、これらの 2 つのベクトルを参照して「実際の」マトリックスのデータにアクセスし、「horizo​​ntalShift(...)」や「verticalShift(...)」などのメソッドを使用して、値のみを交換します。あなたが提案したように、2つのベクトル。

それは最速の実装でしょうか？データにアクセスする間接的な方法がもう 1 つあり (それでも O(1))、スワッピングは、ベクトルを使用した水平シフトの場合は O(m)、垂直シフトの場合は O(n) (by m 行列の場合) になります。

于 2009-09-25T19:13:09.590 に答える
1

あなたが正確に何を意味するのか分かりません。通常、右シフトはバッファーまたは行ベクトルに適用されます。答えは、マトリックスの保存方法によって異なります。

メモリ レイアウトで許可されている場合、配列を回転させる効率的な方法は、最初の値を配列の末尾にコピーしてから、配列へのポインターを 1 要素上に移動することです。これは、配列に十分なスペースを割り当て、何度もローテーションしない場合にのみ機能します。

または、配列を所定の位置に保持し、「左端」への追加のポインターを持ち、他の操作ですべてのラップアラウンドを正しく処理するように注意することもできます。

そうしないと、おそらく多くのメモリコピーを実行する必要があります。

編集：この回答を含めるように質問を更新したばかりです。

その他の編集:例から、行と列を個別にシフトする必要はないようです。その場合は、「左上」のインデックスの座標を保存し、すべての行列演算を変更して、データ構造内の値を適切に検索するだけです。

あなたにとっての問題は、効率をどこに求めるかという問題になります。多くのシフト操作を実行する予定ですか? そうでない場合は、追加のルックアップですべての乗算演算を遅くしても意味がないかもしれません。

また、ルックアップのアイデアを使用する場合は、絶対に mod 演算子を使用しないでください。それは信じられないほど非効率的です。代わりに、シフトの場合は、行または列の長さを超えているかどうかをテストし、必要に応じて長さを差し引きます。

于 2009-09-25T18:04:23.893 に答える
0

シフト自体を非常に速く行う方法がありますが、マトリックスを「使用」しようとすると非効率になります。

たとえば、「int m[3][2];」のように定義された行列があるとします。インデックスを使用して、最初の列のインデックスを定義するだけかもしれません。したがって、シフトはその 1 つのインデックスの単なる加算/減算です (データの変更はありません)。

もう一つの例; 行列をバイナリに制限したい場合は、行列を単一の変数にパックし、ビット シフト (左\右に回転) を使用できます。

ただし、これらの方法はどちらも他の操作をより複雑にします。

それはすべて、マトリックスの使用方法の範囲と、マトリックスをどの程度一般化するかによって決まると思います。

于 2009-09-25T18:40:29.510 に答える