1

データ構造のクラスの暗号演算を解くプログラムを作成しました。教授は、リンクされたノードで構成されるスタックを利用して、どの文字をどの数字に置き換えたかを追跡することを勧めましたが、整数でも同じことができることに気付きました。スタック {A, 1, B, 2, C, 3, D, 4} の代わりに、1234 で同じ情報を保持できます。

しかし、私のプログラムは、彼が私たちに与えた見積もりよりもはるかに遅く実行されているようです. スタックがはるかに効率的に動作する理由を誰かが説明できますか? メソッド (push、pop、top など) を何度も呼び出すのではなく、「ソリューション」にメソッドを 1 つ追加するだけで、より高速になると想定していました。

これは自由回答形式の質問ではないため、クローズしないでください。さまざまな方法で実装できますが、C++ の中心部で、Stack を介してデータにアクセスすると、int に格納して mod によって抽出するよりもパフォーマンスが向上する理由を知りたいと思います。

これは宿題ですが、私は実際に助けを必要としていません。

ありがとう。新しいことを学ぶのが待ちきれません!

編集（いくつかのコードを追加）

letterAssignments はサイズ 26 の int 配列です。SEND + MORE = MONEY のような問題では、A は使用されないため、letterAssignments[0] は 11 に設定されます。使用されるすべての文字は 10 に初期化されます。answerNum は、固有の文字があるため、桁数が多くなります (この場合は 8 桁)。

int Cryptarithmetic::solve(){
while(!solved()){       
    for(size_t z = 0; z < 26; z++){
        if(letterAssignments[z] != 11) letterAssignments[z] = 10;
    }
    if(answerNum < 1) return NULL;
    size_t curAns = answerNum;

    for(int i = 0; i < numDigits; i++){ 
        if(nextUnassigned() != '$') {
            size_t nextAssign = curAns % 10;
            if(isAssigned(nextAssign)){
                    answerNum--;
                    continue;
                }
            assign(nextUnassigned(), nextAssign);
            curAns /= 10;
        }
    }
    answerNum--;
}
return answerNum;
}

見たい場合の 2 つのヘルパー メソッド:

char Cryptarithmetic::nextUnassigned(){ 
char nextUnassigned = '$';
for(int i = 0; i < 26; i++) {
    if(letterAssignments[i] == 10) return ('A' + i);
}
}

void Cryptarithmetic::assign(char letter, size_t val){
assert('A' <= letter && letter <= 'Z');  // valid letter
assert(letterAssignments[letter-'A'] != 11); // has this letter
assert(!isAssigned(val)); // not already assigned.
letterAssignments[letter-'A'] = val;
}
4

4 に答える 4

1

見た目からすると、あなたがここでやっているやり方はかなり非効率的です。

ループごとに実装が大幅に遅くなるため、原則として、for ループの数をできるだけ少なくするようにしてください。

たとえば、他のすべてのコードを取り除くと、プログラムは次のようになります

while(thing) {
  for(z < 26) {

  }
  for(i < numDigits) {
    for(i < 26) {

    }
    for(i < 26) {

    }
  }
}

これは、実行している while ループごとに ((26+26)*numDigits)+26 ループ操作を意味します。isAssigned()それは、ループを使用しないと仮定しています。

理想的には、次のことが必要です。

while(thing) {
  for(i < numDigits) {
  }
}

コードを変更することで可能だと確信しています。これが、整数配列を使用した実装が、ループを使用しないスタックを使用した実装よりもはるかに遅い理由ですfor(i < 26)(私は推測します)。

ただし、元の質問への回答では、メモリの割り当てや関数の呼び出しなどに伴うオーバーヘッドが増えるため、整数の配列を格納することは、思いつく構造体よりも常に高速になります。

しかし、すべての場合と同様に、遅いプログラムと速いプログラムの主な違いは実装です。

于 2011-09-29T05:38:45.527 に答える
0

mod 関数で使用される div 命令は非常に高価です。目的に合わせて使用​​すると、優れたスタック実装よりも効率が低下する可能性があります。命令のタイミング表は次のとおりです: http://gmplib.org/~tege/x86-timing.pdf

また、意図したとおりに機能することを確認するために、int ベースのスタックの単体テストを作成する必要があります。

于 2011-09-29T05:49:07.043 に答える
0

問題は、数を数えることで繰り返しも考慮していることです。問題が、数値方程式が成り立つように、異なる文字ごとに異なる数字を割り当てるように求めている場合があります。

たとえば、4 文字の場合、それら10*10*10*10=10000の代わりに文字 -> 数字のマッピングをテスト10*9*8*7=5040しています (大きいほど文字の数になり、大きいほど 2 つの数字の比率になります...)。

于 2011-09-29T06:04:33.750 に答える
0

プログラミングは、実際にはメモリを時間と交換することであり、その逆も同様です。ここでは、データを整数にパックしています。あなたは記憶を惜しみませんが、時間を失います。

もちろん、速度はスタックの実装に依存します。C++ はクラスを持つ C です。クラスを使用していない場合は、基本的に C (C と同じくらい高速) です。

const int stack_size = 26;

struct Stack
{
  int _data[stack_size];
  int _stack_p;
  Stack()
  :_stack_size(0)
  {}
  inline void push(int val)
  {
     assert(_stack_p < stack_size); // this won't be overhead 
                                    // unless you compile debug version(-DNDEBUG) 
     _data[_stack_p] = val;
  }

  inline int pop()
  {
    assert(_stack_p > 0);       // same thing. assert is very useful for tracing bugs
    return _data[--_stack_p];  // good hint for RVO
  }

  inline int size()
  {
    return _stack_p;
  }

  inline int val(int i)
  {
    assert(i > 0 && i < _stack_p);      
    return _data[i];
  }
}

vtbp のようなオーバーヘッドはありません。また、pop() と push() は非常に単純なのでインライン化されるため、関数呼び出しのオーバーヘッドはありません。int はプロセッサに最適なサイズであることが保証されているため (アライメントなどの必要がないため)、スタック要素として int を使用すると速度も向上します。

于 2011-09-29T06:37:33.653 に答える