0

Python(sage) プログラムを C++ プログラムに変換しています。

行列を操作する関数を作成する必要があり、行列内の最大要素のインデックスを見つける必要があります。

これをできるだけ効率的にしたいのですが、これまでに思いついたのは非常に非効率的です。

私のアルゴリズムの擬似コードは、

  1. 行列を指定して、各行で max_element 関数を呼び出します
  2. ベクトルを作成し、max_element から返された反復子を push_back します
  3. イテレータを逆参照して、もう一度 max_element 関数を呼び出します
  4. 列のインデックスを見つける
  5. 行のインデックスを見つける

これは非常に面倒で遅くなります..このタスクを実行するためのより良いアルゴリズムを持っている人はいますか? ありがとうございました。

4

2 に答える 2

3

外側のループを自分で書くのがおそらく最も簡単です:

if (matrix.size() == 0 || matrix[0].size() == 0) {
    // matrix is empty, handle special case
    throw std::logic_error("empty");
}
int best = matrix[0][0];
size_t rowidx = 0, colidx = 0;
for (auto it = matrix.begin(); it != matrix.end(); ++it) {
    auto maxit = max_element(it->begin(), it->end());
    if (*maxit > best) {
        best = *maxit;
        rowidx = it - matrix.begin();
        colidx = maxit - it->begin();
    }
}

または、マトリックス全体を反復処理する反復子クラスを作成することもできます。

struct MatrixIterator : std::iterator<std::forward_iterator_tag, int> {
    typedef vector<vector<int> > Matrix;
    Matrix &m;
    size_t rowidx, colidx;
    explicit MatrixIterator(Matrix &m, size_t row = 0, size_t col = 0) : m(m), rowidx(row), colidx(col) {};
    int &operator*() { return m[rowidx][colidx]; }
    MatrixIterator &operator++() {
        ++colidx;
        if (colidx == m[rowidx].size()) {
            colidx = 0;
            ++rowidx;
        }
        return *this;
    }
    MatrixIterator operator++(int) {
        MatrixIterator result = *this;
        ++*this;
        return result;
    }
    bool operator==(const MatrixIterator &rhs) {
        return rowidx == rhs.rowidx && colidx == rhs.colidx;
    }
    bool operator!=(const MatrixIterator &rhs) {
        return ! (*this == rhs);
    }
    static MaxtrixIterator end(Matrix &m) {
        return MatrixIterator(m, m.size() - 1, m.back().size());
    }
};

これで、次のことができます。

MatrixIterator result = std::max_element(MatrixIterator(m), MatrixIterator::end(m));
size_t rowidx = result.rowidx, colidx = result.colidx;
于 2013-07-02T17:37:52.667 に答える