string - unordered_map 插入正在造成瓶颈
问题描述
所以在这里我试图创建一个 Graph 数据结构,在其中我必须根据它们的 id 跟踪边缘。所以我在字符串数据结构中创建边缘ID作为eid:sourceid_destinationid
using namespace std;
class Edge{
public:
bool operator==(const Edge* &obj) const
{
return eid==obj->eid;
}
std::string eid;
set<int> rrids;
int sourceid;
int destid;
int strength;
public:
Edge(std::string eid,int from,int to);
std::string getId();
void addRRid(int rrid);
void removeRRid(int rrid);
void setRRid(set<int> rrids);
void setId(std::string eid);
};
这是我用来添加和删除边缘的另一个类。hpp 文件
使用命名空间标准;
class RRassociatedGraph{
public:
unordered_map<int,vertex*> vertexMap;
std::unordered_map<std::string,Edge*> EdgeMap;
int noOfEdges;
public:
RRassociatedGraph();
unordered_set<vertex> getVertices();
int getNumberOfVertices();
void addVertex(vertex v);
vertex* find(int id);
Edge* findedge(std::string id);
void addEdge(int from, int to, int label);
void removeEdge(int from, int to,int rrSetID);
};
当我调试代码时,我发现在函数 add edge here 中我正在执行 EdgeMap.insert 的地方执行不会转到下一行。它保留在哈希表中,用于某些存储桶条目的循环。我不能经常调试这段代码,因为我必须等待 3 个小时才能得到这个问题。该代码与小图完美配合。但是对于 edgeMap 必须存储 800k 边的较大图。它进入这个哈希表无限循环。我没有得到这个哈希表代码。但是我创建 Edgemap 的数据结构有问题吗?
#include "RRassociatedGraph.hpp"
RRassociatedGraph::RRassociatedGraph() {
noOfEdges=0;
}
void RRassociatedGraph::addVertex(vertex v) {
vertexMap.insert(pair<int,vertex*>(v.getId(), &v));
}
vertex* RRassociatedGraph::find(int id) {
unordered_map<int,vertex*>::const_iterator got=vertexMap.find(id);
if(got != vertexMap.end() )
return got->second;
return nullptr;
}
Edge* RRassociatedGraph::findedge(std::string id){
unordered_map<std::string,Edge*>::const_iterator got=EdgeMap.find(id);
if(got != EdgeMap.end() )
return got->second;
return nullptr;
}
void RRassociatedGraph::addEdge(int from, int to, int label) {
vertex* fromVertex = find(from);
if (fromVertex == nullptr) {
fromVertex = new vertex(from);
vertexMap.insert(pair<int,vertex*>(fromVertex->getId(), fromVertex));
}
vertex* toVertex = find(to);
if (toVertex == nullptr) {
toVertex = new vertex(to);
vertexMap.insert(pair<int,vertex*>(toVertex->getId(), toVertex));
}
if(fromVertex==toVertex){
// fromVertex->outDegree++;
//cout<<fromVertex->getId()<<" "<<toVertex->getId()<<"\n";
return;
}
std::string eid=std::to_string(from);
eid+="_"+std::to_string(to);
Edge* edge=findedge(eid);
if(edge==nullptr){
edge=new Edge(eid,from,to);
edge->addRRid(label);
fromVertex->addOutGoingEdges(edge);
EdgeMap.insert(pair<std::string,Edge*>(edge->getId(), edge));
noOfEdges++;
}
else{
edge->addRRid(label);
fromVertex->outDegree++;
}
}
void RRassociatedGraph::removeEdge(int from, int to,int rrSetID) {
vertex* fromVertex = find(from);
std::string eid=std::to_string(from);
eid+="_"+std::to_string(to);
if(EdgeMap.count(eid)==1){
Edge* e=EdgeMap.find(eid)->second;
if(fromVertex->removeOutgoingEdge(e,rrSetID)){
EdgeMap.erase(eid);
delete e;
}
}
}
这是它不断进入这个 for 循环的地方。map 的插入时间应该非常少,但这在我的代码中造成了瓶颈。
template <class _Tp, class _Hash, class _Equal, class _Alloc>
void
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc)
{
#if _LIBCPP_DEBUG_LEVEL >= 2
__get_db()->__invalidate_all(this);
#endif // _LIBCPP_DEBUG_LEVEL >= 2
__pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc();
__bucket_list_.reset(__nbc > 0 ?
__pointer_alloc_traits::allocate(__npa, __nbc) : nullptr);
__bucket_list_.get_deleter().size() = __nbc;
if (__nbc > 0)
{
for (size_type __i = 0; __i < __nbc; ++__i)
__bucket_list_[__i] = nullptr;
__next_pointer __pp = __p1_.first().__ptr();
__next_pointer __cp = __pp->__next_;
if (__cp != nullptr)
{
size_type __chash = __constrain_hash(__cp->__hash(), __nbc);
__bucket_list_[__chash] = __pp;
size_type __phash = __chash;
for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr;
__cp = __pp->__next_)
{
__chash = __constrain_hash(__cp->__hash(), __nbc);
if (__chash == __phash)
__pp = __cp;
else
{
if (__bucket_list_[__chash] == nullptr)
{
__bucket_list_[__chash] = __pp;
__pp = __cp;
__phash = __chash;
}
else
{
__next_pointer __np = __cp;
for (; __np->__next_ != nullptr &&
key_eq()(__cp->__upcast()->__value_,
__np->__next_->__upcast()->__value_);
__np = __np->__next_)
;
__pp->__next_ = __np->__next_;
__np->__next_ = __bucket_list_[__chash]->__next_;
__bucket_list_[__chash]->__next_ = __cp;
}
}
}
}
}
}
我有很多文件,所以我不能把整个代码。我在 C++ 中不是那么好。如果我必须以其他方式实现它,请告诉我。我必须使用 hashMap 因为我还需要更快的搜索。
解决方案
您可能在插入时遇到重新散列。Unordered_map 有多个桶。当它们被填充时,最坏情况下的插入时间是 O(size())。 http://en.cppreference.com/w/cpp/container/unordered_map/insert 仅当新元素数大于 max_load_factor()*bucket_count() 时才会发生重新散列。
您可以对当前设置执行的操作是: 1. 程序初始化时的增长图,因为通常存储桶的数量不会减少。2. 从 std::unordered_map 更改为 Boost::intrusive_map,您可以在其中手动管理存储桶的数量。
推荐阅读
- c++ - Excel C API xlfGetCell 与范围
- php - 如何调试 Dockerfile 的入口点?
- tizen - 在 EDC 脚本中将过渡从线性更改为减速
- .net-core - BackgroundService QueueHostedService
- python - 在 matplotlib 中获取每周时间序列数据的异常折线图
- html - 使用 flexbox 的可滚动全高 div
- javascript - 如何使按钮适用于单击的确切元素而不是渲染列表上的所有元素
- javascript - Eclipse IDE 在 HTML 文件中调用 onclick 属性错误
- python - 在 python 中使用多线程访问 api
- validation - NetCore SwaggerUI - 获取路由 - 参数验证不向用户显示