0

Fortran から C++ に移行するコードがあり、元の F77 コードで作成しなければならなかったネストされた for ループ構造の一部を回避したいと考えています。

問題は次のとおりです。ノードと呼ばれるオブジェクトのベクトルがあり、それぞれが (他の重要な情報の中でも) 接続されている他のノード オブジェクトのインデックス (接続グラフ) を保持するベクトルを含んでいます。このような

struct Node {
    vector<int> conNode;
};
vector<Node> listOfNodes;
vector<int> nodeListA;    // a subset of nodes of interest stored as their vector indices

nodeListA 内のノードが接続されているノードを探す必要がありますが、それらのノードが nodeListA 内にもある場合に限られます。現在、私のコードは次のようになっています。

// Loop over the subset of node indices
for (int i=0; i<nodeListA.size(); i++) {
    // Loop over the nodes connected to the node i
    for (int j=0; j<listOfNodes[nodeListA[i]].conNode.size(); j++) {
        // Loop over the subset of node indices again
        for (int k=0; k<nodeListA.size(); k++) {
            // and determine if any of node i's connections are in the subset list
            if (nodeListA[k] == listOfNodes[nodeListA[i]].conNode[j]) {
               // do stuff here
            }
        }
    }
}

これを行うには、もっと簡単な方法が必要です。この方法を複雑にしすぎているようです。おそらく標準アルゴリズムライブラリを使用して、このコードを単純化するにはどうすればよいですか?

4

2 に答える 2

1

の辞書 (O(log n) のようなもの、またはC++11std::setのようなハッシュベースのもの) を使用することをお勧めします。以下は、C++11 のコード例です。std::unordered_setnodeListA

#include <unordered_set>
#include <vector>

struct Node {
  std::vector<int> conNode;
};

int main()
{
  std::vector<Node>       listOfNodes;
  std::unordered_set<int> nodeListA;

  for (int node_id : nodeListA)
    for (int connected_id : listOfNodes[node_id].conNode)
      if (nodeListA.find(connected_id) != end(nodeListA))
        /* Do stuff here.. */
          ;

  return 0;
}

a を使用する利点std::unordered_setは、ルックアップ (つまり、特定のノード ID の検索) が非常に高速であることです。ただし、標準ライブラリに含まれる実装は特に高速ではない場合があります。Google のスパース ハッシュとデンス ハッシュの実装は、同じインターフェイスを提供する代替手段であり、ほとんどの目的に非常に適していることが知られています: http://code.google.com/p/sparsehash/

結果のノードで何をしたいかによっては、上記のコードの内側のループを STL アルゴリズムに置き換えることができる場合があります。たとえば、アルゴリズムによって識別されたすべてのノードをベクトルに配置する場合は、次のようにコーディングできます (これを両方のループの代わりに使用します)。

std::vector<int> results;
for (int node_id : nodeListA)
  std::copy_if(begin(listOfNodes[node_id].conNode),
               end(listOfNodes[node_id].conNode),
               back_inserter(results),
               [&nodeListA](int id){return nodeListA.find(id) != end(nodeListA);});

繰り返しますが、これは C++11 構文です。関数の引数としてラムダを使用します。

于 2012-10-19T16:23:57.040 に答える
1

変数が一連の値を表す必要がある場合は、std::set代わりに を使用しstd::vectorます。それからあなたは持っているでしょう

typedef std::set<int> SetOfIndices;
SetOfIndices setOfIndices; // instead of nodeListA
for(SetOfIndices::const_iterator iter = setOfIndices.begin(); iter != setOfIndices.end(); ++iter)
{
    Node const & node = listOfNodes[*iter];
    for (int j = 0; j < node.conNode.size(); ++j)
    {
        if (setOfIndices.find(node.conNode[j]) != setOfIndices.end())
        {
            // do stuff here
        }
    }
}

EDIT Jerry Coffinが示唆std::set_intersectionするように、外側のループで使用できます:

struct Node {
    SetOfIndices conNode;
}
typedef std::set<int> SetOfIndices;
SetOfIndices setOfIndices; // instead of nodeListA
for(SetOfIndices::const_iterator iter = setOfIndices.begin(); iter != setOfIndices.end(); ++iter)
{
    Node const & node = listOfNodes[*iter];
    std::vector<int> interestingNodes;

    std::set_intersection(setOfIndices.begin(), setOfIndices.end(),
                      node.conNode.begin(), node.conNode.end(),
                      std::back_inserter(interestingNodes));

    for (int j = 0; j < interestingNodes.size(); ++j)
    {
        // do stuff here
    }
}

別の編集
効率について-それは支配的な操作が何であるかによって異なります。「do stuff here」と記載されている部分の実行回数は変わりません。違いは、コレクションをトラバースする時間です。

  1. 元のコード - nodeListA.size()^2 * [conNode の平均サイズ]
  2. 私の最初の解決策 - nodeListA.size() * log(nodeListA.size()) * [conNode の平均サイズ]
  3. Jerry Coffin の提案後 - nodeListA.size()^2 * [興味深い conNode 要素の平均数]

したがってset_intersection、この場合、使用は役に立たないようです。

于 2012-10-19T15:57:31.073 に答える