Q.グラフ ファイルに対して行っているように、ネストされたセマンティック アクションを使用しても問題ありませんか? これはパフォーマンスに影響しますか?
私はそれをしません。エッジのホールセールを追加する方がおそらくはるかに簡単です。
x3::parse(file_iterator, eof,
*((x3::int_ >> '\t' >> x3::int_ >> x3::eol)[add_edge])
);
次のように簡単add_egeにできます。
auto add_edge = [&](auto& ctx){
// Add edge from from context
vertex_decriptor source, target;
auto tup = std::tie(source, target);
fusion::copy(x3::_attr(ctx), tup);
boost::add_edge(map_vertex(source), map_vertex(target), g);
};
Q. Spirit X3 で一度にファイル全体を解析することをお勧めしますか、それとも、Spirit X3 ですべての行を個別に解析する必要がありますか?
スピリットが推奨するものではないと思います。ファイル全体を一度に実行します。また、メモリ マップト ファイルを使用して効率を高めることをお勧めします (multi_passイテレータの適応なしのランダム アクセス イテレーション)。
総論:
スペース認識パーサーを使用しようとしていますが、 istream_iterators で使用しています。その後、ストリームのフラグをリセットすることを忘れないでください。skipws
verticesマップはリソースの無駄遣いのようです。[user]に変換する代わりに、 thing( vertex_id) を直接使用できるかどうかを検討してくださいvertex_descriptor。
これは、 https: //snap.stanford.edu/data/loc-gowalla.html からのファイルを約 19 秒で問題なく解析する、クリーンアップされたバージョンです(すでにかなり高速です)。
Live On Coliru
#include <boost/fusion/adapted/std_tuple.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/spirit/home/x3.hpp>
#include <boost/spirit/include/support_istream_iterator.hpp>
#include <fstream>
#include <iostream>
namespace x3 = boost::spirit::x3;
namespace fusion = boost::fusion;
struct vertex_property {
double longitude;
double latitude;
};
struct edge_property { };
struct Reader {
bool read_edges(std::string fname) {
// Lambda function that adds edge to graph
auto add_edge = [this](auto& ctx){
// Add edge from from context
vertex_decriptor source, target;
auto tup = std::tie(source, target);
fusion::copy(x3::_attr(ctx), tup);
boost::add_edge(this->map_vertex(source), this->map_vertex(target), g);
};
// Parse the gowalla edge file
std::ifstream edge_file(fname);
if (!edge_file) return false;
boost::spirit::istream_iterator file_iterator(edge_file >> std::noskipws), eof;
x3::parse(file_iterator, eof, *((x3::int_ >> '\t' >> x3::int_ >> x3::eol)[add_edge]));
// Fail if we couldn't parse the whole edges file
return (file_iterator == eof);
}
bool read_locations(std::string fname) {
// Lambda function that adds locations to vertices in the graph
auto add_location = [&](auto& ctx){
// _attr(ctx) returns a boost fusion tuple
auto attr = x3::_attr(ctx);
auto vertex_id = fusion::at_c<0>(attr);
if (!location_already_added.insert(vertex_id).second)
return true; // Exit, as we already stored the location for this vertex
// Test if vertex is in our graph
// We are parsing locations from a different file than the graph, so
// there might be inconsistencies
auto mapped = mapped_vertices.find(vertex_id);
if (mapped == mapped_vertices.end()) {
std::cerr << "Tried to add location to vertex " << vertex_id << ", but this vertex is not in our graph" << std::endl;
return false;
}
// Add location to the vertex
auto& props = g[mapped->second];
props.latitude = fusion::at_c<1>(attr);
props.longitude = fusion::at_c<2>(attr);
return true;
};
// Parse the gowalla location file
std::ifstream location_file(fname);
if (!location_file) return false;
boost::spirit::istream_iterator file_iterator(location_file >> std::noskipws), eof;
x3::parse(file_iterator, eof,
// [vertex_id] [time of checkin] [latitude] [longitude] [location] id
*((x3::int_ >> '\t' >> x3::omit[*x3::graph] >> '\t' >> x3::double_ >> '\t' >> x3::double_)[add_location] >> '\t' >> x3::int_ >> x3::eol)
);
// Fail if we couldn't parse the whole location file
return (file_iterator == eof);
}
private:
// We use setS to enforce our graph not to become a multigraph
typedef boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS, vertex_property, edge_property> graph;
using vertex_decriptor = graph::vertex_descriptor;
std::map<int, vertex_decriptor> mapped_vertices;
std::set<int> location_already_added;
graph g;
// Lambda function that adds vertex to graph if not already added
vertex_decriptor map_vertex(int id) {
auto match = mapped_vertices.find(id);
if (match != mapped_vertices.end())
return match->second; // vertex already known
else // Otherwise add vertex
return mapped_vertices[id] = boost::add_vertex(g);
};
};
int main() {
Reader reader;
if (!reader.read_edges("loc-gowalla_edges.txt"))
std::cerr << "Couldn't parse whole edges file" << std::endl;
if (!reader.read_locations("loc-gowalla_totalCheckins.txt"))
std::cerr << "Couldn't parse whole location file" << std::endl;
}
マップされたファイル
比較のために、メモリ マップされたファイルに置き換えると、はるかに高速になります。3秒で完了します (これも 6 倍以上高速です)。
Live On Coliru
変更されたフラグメントの例:
boost::iostreams::mapped_file_source mm(fname);
auto f = mm.begin(), l = mm.end();
x3::parse(f, l, *((x3::int_ >> '\t' >> x3::int_ >> x3::eol)[add_edge]));
メモリのオーバーヘッド
プロファイリング後。マップ/セットを持っていることはおそらくそれほど悪くないようです:
私が見たところ、このプログラムは 152MiB を使用しており、location_already_added一見しただけで 4.1 しか表示されません。
メモリ使用量と時間の削減
それでも、set<int> location_already_addedを動的ビットセットに置き換えて を削除すると、メモリ使用量とプログラムの実行時間map<int, vertex_descriptor>がさらに削減されます。
今回は2 秒未満で完了します (さらに 33% オフ)。
明らかな理由で、必要なメモリが約10% 少なくなります: 138.7 MiB。
Live On Coliru
変更点:
#include <boost/fusion/adapted/std_tuple.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/spirit/home/x3.hpp>
#include <boost/iostreams/device/mapped_file.hpp>
#include <boost/dynamic_bitset.hpp>
#include <fstream>
#include <iostream>
namespace x3 = boost::spirit::x3;
namespace fusion = boost::fusion;
struct vertex_property {
double longitude;
double latitude;
};
struct edge_property { };
struct Reader {
Reader() {
g.m_vertices.reserve(1024);
}
bool read_edges(std::string fname) {
// Lambda function that adds edge to graph
auto add_edge = [this](auto& ctx){
// Add edge from from context
vertex_decriptor source, target;
auto tup = std::tie(source, target);
fusion::copy(x3::_attr(ctx), tup);
boost::add_edge(this->map_vertex(source), this->map_vertex(target), g);
};
// Parse the gowalla edge file
boost::iostreams::mapped_file_source mm(fname);
auto f = mm.begin(), l = mm.end();
x3::parse(f, l, *((x3::int_ >> '\t' >> x3::int_ >> x3::eol)[add_edge]));
// Fail if we couldn't parse the whole edges file
return f == l;
}
bool read_locations(std::string fname) {
boost::dynamic_bitset<> location_already_added(num_vertices(g));
// Lambda function that adds locations to vertices in the graph
auto add_location = [&](auto& ctx){
// _attr(ctx) returns a boost fusion tuple
auto const& attr = x3::_attr(ctx);
auto vertex_id = fusion::at_c<0>(attr);
if (location_already_added.test(vertex_id))
return true; // Exit, as we already stored the location for this vertex
location_already_added.set(vertex_id);
// Test if vertex is in our graph
// We are parsing locations from a different file than the graph, so
// there might be inconsistencies
auto mapped = this->mapped_vertex(vertex_id);
if (graph::null_vertex() == mapped) {
std::cerr << "Tried to add location to vertex " << vertex_id << ", but this vertex is not in our graph" << std::endl;
return false;
}
// Add location to the vertex
auto& props = g[mapped];
props.latitude = fusion::at_c<1>(attr);
props.longitude = fusion::at_c<2>(attr);
return true;
};
// Parse the gowalla location file
std::ifstream location_file(fname);
if (!location_file) return false;
boost::iostreams::mapped_file_source mm(fname);
auto f = mm.begin(), l = mm.end();
x3::parse(f, l,
// [vertex_id] [time of checkin] [latitude] [longitude] [location] id
*((x3::int_ >> '\t' >> x3::omit[*x3::graph] >> '\t' >> x3::double_ >> '\t' >> x3::double_)[add_location] >> '\t' >> x3::int_ >> x3::eol)
);
// Fail if we couldn't parse the whole location file
return f == l;
}
typedef boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS, vertex_property, edge_property> graph;
private:
// We use setS to enforce our graph not to become a multigraph
using vertex_decriptor = graph::vertex_descriptor;
graph g;
#if USE_VERTEX_DESCRIPTOR_MAPPING
std::map<int, vertex_decriptor> mapped_vertices;
vertex_decriptor map_vertex(int id) {
auto match = mapped_vertices.find(id);
if (match != mapped_vertices.end())
return match->second; // vertex already known
else // Otherwise add vertex
return mapped_vertices[id] = boost::add_vertex(g);
};
vertex_decriptor mapped_vertex(int id) const {
auto mapped = mapped_vertices.find(id);
return mapped == mapped_vertices.end()
? return graph::null_vertex()
: mapped->second;
}
#else
static vertex_decriptor map_vertex(int id) { return id; }
static vertex_decriptor mapped_vertex(int id) { return id; }
#endif
};
int main() {
Reader reader;
if (!reader.read_edges("loc-gowalla_edges.txt"))
std::cerr << "Couldn't parse whole edges file" << std::endl;
if (!reader.read_locations("loc-gowalla_totalCheckins.txt"))
std::cerr << "Couldn't parse whole location file" << std::endl;
}