4

Javaで効率的な優先キューを実装しようとしています。バイナリヒープの適切な実装に到達しましたが、理想的なキャッシュパフォーマンスがありません。このために、私はバイナリヒープでVan Emde Boasレイアウトの調査を開始しました。これにより、バイナリヒープの「ブロック」バージョンが作成されました。ここでの秘訣は、子と親のインデックスを計算することです。

これはできましたが、キャッシュの動作（および実行時間）が悪化しました。問題は次のとおりだと思います。Javaであるため、参照の局所性が達成されていない可能性があります。オブジェクトの配列を使用すると、実際にオブジェクトがJavaのメモリ内で連続するかどうかはわかりませんが、誰かがこれを確認できますか？

また、JavaのネイティブPriorityQueueがどのようなデータ構造を使用しているのかを知りたいと思います。

4

3 に答える 3

2

一般に、キュー内のオブジェクトに連続したメモリ チャンクを強制的に占有させる良い方法はありません。ただし、特殊なケースに適したテクニックがいくつかあります。

大まかに言うと、これらの手法には、バイト配列の使用と、配列との間でのデータの「シリアル化」が含まれます。これは、非常に単純なオブジェクトを格納している場合、実際には非常に効果的です。たとえば、多数の 2D ポイント + 重みを格納している場合、重み、x 座標、y 座標に相当するバイトを単純に書き込むことができます。

もちろん、この時点での問題は、ピーク/ポッピング中にインスタンスを割り当てることです。これは、コールバックを使用することで回避できます。

格納されるオブジェクト自体が複雑な場合でも、これと同様の手法を使用して、重み用に 1 つの配列を保持し、実際のオブジェクトの参照の別の配列を保持することで、絶対に必要になるまでオブジェクト参照をたどることを回避できることに注意してください。

単純な不変の値型を格納するためのアプローチに戻ると、これは何ができるかの不完全なスケッチです。

abstract class LowLevelPQ<T> {

  interface DataHandler<R, T> {
    R handle(byte[] source, int startLoc);
  }

  LowLevelPQ(int entryByteSize) { ... }
  abstract encode(T element, byte[] target, int startLoc);
  abstract T decode(byte[] source, int startLoc);
  abstract int compare(byte[] data, int startLoc1, int startLoc2);

  abstract <R> R peek(DataHandler<R, T> handler) { ... }
  abstract <R> R pop(DataHandler<R, T> handler) { ... }
}

class WeightedPoint {
  WeightedPoint(int weight, double x, double y) { ... }
  double weight() { ... }
  double x() { ... }
  ...
}

class WeightedPointPQ extends LowLevelPQ<WeightedPoint> {
  WeightedPointPQ() {
    super(4 + 8 + 8); // int,double,double
  }

  int compare(byte[] data, int startLoc1, int startLoc2) {
    // relies on Java's big endian-ness
    for (int i = 0; i < 4; ++i) {
      int v1 = 0xFF & (int) data[startLoc1];
      int v2 = 0xFF & (int) data[startLoc2];
      if (v1 < v2) { return -1; }
      if (v1 > v2) { return  1; }
    }
    return 0;
  }

  ...
}
于 2011-04-05T08:14:43.413 に答える
1

そうは思わない。「オブジェクトの配列」はオブジェクトの配列ではなく、オブジェクト参照の配列であることを忘れないでください（実際にはプリミティブの配列であるプリミティブの配列とは異なります）。オブジェクト参照はメモリ内で連続していると思いますが、これらの参照はいつでも必要なオブジェクトを参照できるため、参照の配列によって参照されるオブジェクトがメモリ内で連続しているという保証はありません。

価値のあることとして、アレイに関するJLSセクションでは、隣接性の保証については何も述べていません。

于 2011-04-04T23:56:24.403 に答える
1

ここでFUDが発生していると思います。配列の実装が連続したメモリを使用しないことは基本的に考えられません。また、.classファイル形式を説明するときにJVM仕様でこの用語が使用される方法は、他の実装が想定されていないことを明確に示しています。

java.util.PriorityQueueは、Javadocに記載されているように、配列を介して実装されたバイナリヒープを使用します。

于 2011-04-05T04:48:39.783 に答える