c++ - メモリ管理が悪い？再帰関数のクラスメンバー (ブール値) の値が 1 より大きい

Question

サブグラフマッチング問題 (分子内の化学官能基のマッチング) に取り組んでいます。元のコードは別の学生 (Visual C++ で、MS 固有のライブラリはありません) によって書かれ、Windows で問題なく動作しました。次に、プログラムに新しい関数を追加しましたが、サブグラフマッチングのアルゴリズムは変更しませんでした。新しいプログラムは gcc4.2/Mac OS X で正常にコンパイルされました。ただし、実行時に奇妙な問題が発生しています。

ここで関連するオブジェクトとそのメンバー:

Atom: ID、要素、Bond のリスト (Bond オブジェクトへのポインターのベクトル)、search_mark (bool) が含まれます。変数を取得し、search_mark を true または false に設定する関数。
Bond: アトム A および B への 2 つのポインターの配列と、パラメーター atom* B で呼び出されたときに atom* A を返す関数 (その逆) が含まれています。
Molecule: アトムへのポインタのベクトルと、アトム ID またはベクトル内の位置を使用してアトム*を取得する関数が含まれています。
Atom のサブクラス: HammettAtom。含まれている追加のメンバーは、関連する分子原子への原子ポインターです。

これは再帰関数のアルゴリズムです: 配列 A のすべてのアトムについて、配列 B のアトム (ハメットグループ、通常はサイズが約 10 ～ 20 アトム) と比較します。要素が同じ場合は、それぞれの接続された原子のリストを取得し、繰り返します。テストされたアトムは途中でマークされるため、ある時点でマークされていない接続されたアトムはなくなります。

これがコードです（変更されていません。テストのためにcoutビットのみが追加されています）。関数が最初に呼び出されると、最初のベクトルはテスト分子の単一の原子であり、2 番目のベクトルはハメットグループ分子の 2 番目の原子です。(ハメットの最初の原子の ID は「X」で、何でもかまいません。)

bool HammettCheck::checkSubproblem(vector<Atom*> bonded_atoms, vector<Atom*> my_list) 
{
unsigned int truth=0;
vector<Atom*> unmarked_bonded;
vector<Atom*> unmarked_list;
cout << "\n size of Hammett array: " <<my_list.size()<< " size of mol array: "<< bonded_atoms.size() << endl; //for testing
//If number of connected atoms is different, return false.
if( bonded_atoms.size() != my_list.size() ){
    return false;
}

//Create new lists.
for(unsigned int i=0; i < bonded_atoms.size() ; i++){

    //Create list of unmarked connected atoms in molecule.
    if( !bonded_atoms[i]->isMarked() ){
        unmarked_bonded.push_back(bonded_atoms[i]);
    }

    //Create list of unmarked connected atoms in hammett.
    if( !my_list[i]->isMarked() ){
        unmarked_list.push_back( my_list[i] );
    }
}
cout << "size of unmarked Hammett array: " << unmarked_list.size() << " size of unmarked mol array: "<< unmarked_bonded.size() <<endl; //for testing
//If number of unmarked connected atoms is different, return false.
if( unmarked_bonded.size() != unmarked_list.size() ){
    return false;
}


//Check each unmarked atom connected in the molecule against possible atoms it could be in the hammett group.
for(unsigned int i=0; i < unmarked_bonded.size(); i++){
  cout<< "atom in um_mol array considered ID: " << unmarked_bonded[i]->getID() << " Ele: " << unmarked_bonded[i]->getEle()<< endl;
    /*Unmarked hammett assigned in reverse order so that the undefined "X" atom is only 
      assigned if a connected atom can not possibly be any other atom.*/
    for(int j=(unmarked_list.size()-1); j > -1; j--){
      cout << "atom in um_h_array considered ID: " << unmarked_list[j]->getID() << endl;
        //If hammett atom has already been assigned to a connected atom, it cannot be assigned to another
        if(!unmarked_list[j]->isMarked()){
          cout << unmarked_list[j]->getID() << "is unmarked" <<endl;
            /*If connected atom could only be hammett group's connection 
              to the rest of the molecule, assign it as such.*/
            if( !strcmp(unmarked_list[j]->getEle().c_str(), "X") ){
                unmarked_bonded[i]->mark();
                unmarked_list[j]->mark(unmarked_bonded[i]);
                truth++;
                cout<< "mol atom ID "<< unmarked_bonded[i]->getID() <<" marked as X, current truth: "<< truth << endl;
                cout << unmarked_list[j]->getID() << "is now marked(1)/unmarked(0) " << unmarked_list[j]->isMarked() << " and break loop "<<endl;
                break;
            }

            /*If connected atom is the same element as a possible hammett atom,
              check that atoms connections by running them through the subproblem.*/
            if( !strcmp(unmarked_bonded[i]->getEle().c_str(), unmarked_list[j]->getEle().c_str()) ){
                unmarked_bonded[i]->mark();
                unmarked_list[j]->mark(unmarked_bonded[i]);
                cout<<"found same ele between mol_id "<< unmarked_bonded[i]->getID() <<" and ham_id " << unmarked_list[j]->getID() <<endl;
                vector<Atom*> new_bonded = getAttachedAtoms( unmarked_bonded[i] );
                vector<Atom*> new_list = getAttachedAtoms( unmarked_list[j] );
                if( checkSubproblem( new_bonded, new_list ) ){
                  cout<<"found same atom"<<endl;
                    truth++;
                    break;

                /*If only the elements are the same do not assign 
                  the hammett atom to this connected atom.*/
                }else{
                    unmarked_bonded[i]->demark();
                    unmarked_list[j]->demark();
                }
            }
        }
    }
}

//Return true if all connected atoms can be assigned atoms of the hammett group.
if( truth == unmarked_bonded.size() ){
    return true;
}else{
    return false;
}
}

コンパイルしたプログラムを 29 原子のテスト分子で実行し、それを 2 つの Hammett グループと比較しました。これにはグループ 2 が含まれている必要がありますが、グループ 1 は含まれていません。ただし、同じ要素を持つ 2 つの原子で開始した場合はいつでも true が返されます。以下は出力のサンプルです (分子は実際にはその原子にハメット基を含んでいません)

 currently at molecule atom ID 1

 size of Hammett array: 1 size of mol array: 1
 size of unmarked H array: 1 size of unmarked mol array: 1
 atom in um_mol array considered ID: 1 Ele: N
 atom in um_h_array considered ID: N1
 N1is unmarked
 found same ele between mol_id 1 and ham_id N1

 size of Hammett array: 3 size of mol array: 3
 size of unmarked H array: 3 size of unmarked mol array: 3
 atom in um_mol array considered ID: 2 Ele: H
 atom in um_h_array considered ID: O2
 O2is unmarked
 atom in um_h_array considered ID: O1
 O1is unmarked
 atom in um_h_array considered ID: X
 X is unmarked
 mol atom ID 2 marked as X, current truth: 1
 X is now marked(1)/unmarked(0) 128 and break loop 
 atom in um_mol array considered ID: 8 Ele: C
 atom in um_h_array considered ID: O2
 O2is unmarked
 atom in um_h_array considered ID: O1
 O1is unmarked
 atom in um_h_array considered ID: X
 X is unmarked
 mol atom ID 8 marked as X, current truth: 2
 X is now marked(1)/unmarked(0) 160 and break loop 
 atom in um_mol array considered ID: 17 Ele: C
 atom in um_h_array considered ID: O2
 O2is unmarked
 atom in um_h_array considered ID: O1
 O1is unmarked
 atom in um_h_array considered ID: X
 X is unmarked
 mol atom ID 17 marked as X, current truth: 3
 X is now marked(1)/unmarked(0) 128 and break loop 
 found same atom
 Hammet group 2 checkSubproblem true
 Hammett added to atom 1

長かったらすいません。しかし問題は、'X' アトム (ハメット分子の最初のアトム) をマークして、search_mark ブール値を取得しようとした直後に、1 より大きい値があったことでした。「真実」カウンターは、条件 true == unmarked_bonded.size() に到達するまで上昇しました。

実際の問題が何であるかわかりませんか？値 128 は、メモリ/ポインタの問題が混同されていることを示唆していますが、それを見つける方法は不明です。再帰関数と関係があるかどうかさえわかりません!

誰かが私が試すことができる何かを提案してくれたら、とても感謝しています. 前もって感謝します！

PS Atom クラス関数のコード。

 string Atom::getID()
{
return id;
}

string Atom::getEle()
{
return ele;
}
void Atom::mark()
{
search_mark = true;
}

void Atom::demark()
{
search_mark = false;
}
void HammettAtom::mark(Atom* assigned)
{
search_mark = true;
related_mol_atom = assigned;
}
bool Atom::isMarked()
{
return search_mark;
}

score 1 · Accepted Answer

すべての提案をありがとう。Valgrind でプログラムを実行した後、問題がメモリリークに関連していたことは明らかです。特定された「完全に失われた」問題でアロケータの位置を移動したところ、search_mark の問題が解消されたようです。プログラムは期待どおりに実行されるようになりましたが、メモリリークが発生します。ただし、メモリリークの問題を解決できていないため、ここに新しい質問を投稿しました。

c++ - メモリ管理が悪い？再帰関数のクラス メンバー (ブール値) の値が 1 より大きい

1 に答える 1

Related

Reference

c++ - メモリ管理が悪い？再帰関数のクラスメンバー (ブール値) の値が 1 より大きい