2

これは、私がやりたいことに時間がかかりすぎています。これを速くする方法はありますか?

編集申し訳ありませんが、品質の郵便番号の問題が続いていたので、最低限のものを投稿しました。

私がやろうとしているのは、オマハ ポーカーのエクイティ計算機です。

A-彼に渡した 4 枚のカード (myhand[4]) を取り、可能な手のすべての組み合わせをチェックして、重複がないかどうかを確認します。

B-重複がある場合、そのハンドを含むベクトルの行を削除したい (したがって、後でエクイティを計算するときに、誰かが持つことが不可能なハンドに対しては計算しません)

int myhand[4] = { 3, 12, 22, 10 };
    vector<vector<int> > vec(4, vector<int>(270725));
    for (int m = 0; m < vec[0].size(); m++) { // A
        for (int k = 0; k < 4; k++) {
            for (int j = 0; j < 4; j++)
                if (myhand[k] == vec[j][m]) {
                    for (int i = 0; i < 4; i++) {
                        vec[i].erase(vec[i].begin() + m); // B
                    }
                    k = 0;
                    j = 0;
                    break;
                }
        }
    }

このコードをより効率的に使用する方法はありますか?

ありがとう、カヴェン

4

3 に答える 3

1

std::vector のような非連想コンテナーでの検索はコストがかかりすぎます。

std::set は手だけが見つかった場合は問題ありませんが、問題のキーは問題のドメインに関して複合キー (カードの 4 タプル) であり、std::set には対処する特別な手段がありません。のようなもの

「特定のコンポーネントを含むすべてのキーを検索します。」

std::map も問題の一部しか解決しません。

boost::bimap を検討することもできますが、別のアプローチを提案します。


問題のデータは、二部グラフ (カードは左、ハンドは右、l<->r エッジは、「カードの頂点」から見れば「ハンドにある」ことを意味し、「ハンドの頂点」から見れば「カードを含む」ことを意味します) によってモデル化できます。

したがって、自己コーディングされた STL ベースのソリューションよりも (STL ベースの) boost::graph を使用することをお勧めします。


もう 1 つの実用的なアプローチは、SQLite を使用して簡単に作成できるインメモリ データベースに依存することです。http://www.sqlite.org/inmemorydb.htmlに参加して ください

于 2013-05-16T23:13:12.093 に答える
0

次のようなループを介して処理したい組み合わせを構築する方が良いでしょう:

#include <cassert>
#include <algorithm>
#include <vector>
#include <iostream>
#include <numeric>

int main (int, char* [])
{
    // Build a deck of cards
    std::vector<int> deck( 52 );
    std::iota( deck.begin(), deck.end(), 0 );

    // Remove 'myhand'
    const int myhand[] =  { 3, 12, 22, 10 };
    for (int i = 0; i < 4; ++i) {
        deck[myhand[i]] = -1;
    }
    deck.resize( std::remove( deck.begin(), deck.end(), -1 ) - deck.begin() );

    // Iterate over all possible remaining entries.
    size_t num_processed = 0;
    for (auto c1 = deck.begin(); c1 != deck.end(); ++c1) {
        for (auto c2 = c1 + 1; c2 != deck.end(); ++c2) {
            for (auto c3 = c2 + 1; c3 != deck.end(); ++c3) {
                for (auto c4 = c3 + 1; c4 != deck.end(); ++c4) {
                    // Compute equity of (*c1, *c2, *c3, *c4) here.

                    ++num_processed;
                }
            }
        }
    }
    // Verify that 48! / (44! * 4!) entries were processed.
    assert ( num_processed == (48*47*46*45) / (4*3*2*1) );
    return 0;
}

ところで、私はホールデム ポーカーのエクイティ計算機を書きました。

于 2013-05-16T18:24:53.207 に答える