4

我正在尝试在 Java 中实现一个有效的优先级队列。我得到了一个很好的二进制堆实现，但它没有理想的缓存性能。为此，我开始研究二进制堆中的 Van Emde Boas 布局，这使我找到了二进制堆的“阻塞”版本，其中的诀窍是计算子索引和父索引。

尽管我能够做到这一点，但缓存行为（和运行时间）变得更糟。我认为问题是：引用的局部性可能没有实现，因为它是 Java -我不太确定使用对象数组是否真的使对象在 Java 中的内存中是连续的，有人可以确认一下吗？

此外，我非常想知道 Java 的本机 PriorityQueue 使用什么样的数据结构，如果有人知道的话。

4

3 回答 3

2

一般来说，没有好的方法可以强制队列中的对象占用一块连续的内存。但是，有些技术适用于特殊情况。

在高层次上，这些技术涉及使用字节数组和从数组中“序列化”数据。如果您要存储非常简单的对象，这实际上非常有效。例如，如果您要存储一堆 2D 点 + 权重，您可以简单地写入权重、x 坐标、y 坐标的字节等效值。

当然，此时的问题在于在查看/弹出时分配实例。您可以通过使用回调来避免这种情况。

请注意，即使在存储的对象本身很复杂的情况下，使用与此类似的技术，您可以为权重保留一个数组，为实际对象保留一个单独的引用数组，这样您就可以避免遵循对象引用，直到绝对必要为止。

回到存储简单不可变值类型的方法，这是您可以做什么的不完整草图：

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。数组的任何实现都不会使用连续内存，这基本上是不可想象的。在 JVM 规范中描述 .class 文件格式时使用该术语的方式非常清楚地表明没有考虑其他实现。

java.util.PriorityQueue 使用二进制堆，正如它在 Javadoc 中所说，通过数组实现。

于 2011-04-05T04:48:39.783 回答