0

Google のハッシュ マップ google::dense_hash_map の実装を使用しています。

私のはクラスタリングアプリケーションです。したがって、クラスターのペア間の距離を保存する必要があります。各クラスターには、long int であるクラスター ID があります。したがって、キーは (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;
}

私は何百万もの距離を持っています。私がチェックした LasTime では、約 600000000 の距離があり、そのうち 400000000 が一意でした。これは、距離の 1/3 が繰り返されることを意味し、その時間を節約できます。

しかし、このハッシュ マップ構造を使用して距離を格納すると、プログラムの実行速度が大幅に低下します。これは私が正確に見つけたものです。距離関数を使用して距離を保存すると、プログラム全体の実行が約 50 秒遅くなります。(ストレージありで 200 秒、ストレージなしで 150 秒)。しかし、距離を保存し、距離を計算する前にハッシュマップを使用して距離が存在するかどうかを確認すると、プログラムの速度が大幅に低下します (プログラムの 1/25 に 300 秒かかります)。

私はこの行動を理解していません。距離が保存されると、距離を取得する方が高速になるはずです。ここで何が問題なのか、より速くできるかどうかを教えてください。

PS: RAM は問題ではありません。約 160 ギガの RAM を搭載したサーバーでこれを実行しています。また、ハッシュマップを使用した場合のピーク時のメモリ消費量は、総メモリ量の 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).

データを承認するためのすべての要素を見つけていると思います。

さて、ハッシュマップのルックアップ時間の複雑さは O(n) ですが、使用しています 

distanceHash.find(id1)

関数で 2 回getStoredDistancen 回、最悪の場合の総複雑度 O(n*n) になります。

400M * 400M = 160000000000000000 複雑すぎる

于 2012-09-02T09:16:15.520 に答える