0

我正在使用 google 的哈希映射 google::dense_hash_map 的实现。

我的是一个集群应用程序。所以我必须存储成对集群之间的距离。每个集群都有一个集群 id，它是一个 long int。所以密钥必须是 (long int id1, long int id2);

所以我决定在 hashMap 中需要一个 hashMap 才能工作。

这是我的距离存储哈希图的结构：

    google::dense_hash_map<long int, google::dense_hash_map<long int, double> > distanceHash;

这是将距离插入哈希映射并检索它的代码

template<class Point>
void CoverTree<Point>:: insertDistance(long int id1, long int id2, long double distance)
{

  //Always id1 < id2;
  if(id1 < id2)
  {
    long temp = id1;
    id1 = id2;
    id2 = temp;
  }


  if(distanceHash.find(id1) == distanceHash.end())
  {
    google::dense_hash_map<long int, double> insideHash;
    insideHash.set_empty_key(-9999  );
    insideHash[id2] = distance;
    distanceHash[id1] = insideHash;
  }
  else
  {
    (distanceHash[id1])[id2] = (distanceHash[id1])[id2];
  }
}

template<class Point>
double CoverTree<Point>::getStoredDistance(long int id1, long int id2)
{
  if(id1 < id2)
  {
    long temp = id1;
    id1 = id2;
    id2 = temp;
  }

  google::dense_hash_map<long int, double>::iterator it;

  if(distanceHash.find(id1) != distanceHash.end())
  {

    if( distanceHash[id1].find(id2) != distanceHash[id1].end() ) 
      return distanceHash[id1][id2];
  }

  return -1;
}

我有数百万的距离。上次我检查过，大约有 600000000 个距离，其中 400000000 个是唯一的。这意味着重复 1/3 的距离，可以节省时间。

但是当我使用这个散列映射结构来存储距离时，程序运行得更慢了。这正是我发现的：如果我只使用距离函数存储距离，那么整个程序的运行速度会慢约 50 秒。（200 秒带存储，150 秒不带）。但是如果我存储距离，然后在计算距离之前使用哈希图检查距离是否存在，程序会变得慢得多（程序的 1/25 需要 300 秒）。

我不明白这种行为。我猜想一旦存储了距离，检索距离应该会更快。请让我知道这里出了什么问题以及是否可以更快。

PS：内存不是问题。我在具有大约 160 GB RAM 的服务器上运行它。并且使用 hashmap 时的峰值内存消耗仅为总内存的 1.8%（使用 top 看到）。所以分页和抖动应该不是问题。

4

1 回答 1

0

But If I store the distances and then use the hashmap to check whether the distances exist before computing them, the program becomes way way slower(1/25th of the program takes 300 seconds).

我怀疑您正在找到所有元素来批准数据。

好的，hashmap 查找时间复杂度是 O(n)，但是你正在使用 

distanceHash.find(id1)

在getStoredDistance函数 n 次中两次，这使得最坏情况下的总复杂度为 O(n*n)

400M * 400M = 160000000000000000 太复杂了

于 2012-09-02T09:16:15.520 回答