Java优先级队列实现-内存位置

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Java优先级队列实现-内存位置，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1953字，纯文字阅读大概需要3分钟。

内容图文

我正在尝试在Java中实现高效的优先级队列.我已经很好地实现了二进制堆,但是它没有理想的缓存性能.为此,我开始研究二进制堆中的Van Emde Boas布局,从而使我得到了二进制堆的“阻塞”版本,其中的诀窍是计运算符索引和父索引.

尽管我能够做到这一点,但缓存行为(和运行时间)变得更糟.我认为问题是：由于是Java,因此可能无法实现引用的局部性-我不确定使用对象数组是否实际上会使对象在Java内存中是连续的,请问有人可以确认吗？

我也非常想知道Java的本机PriorityQueue使用哪种数据结构,如果有的话.

解决方法:

通常,没有一种好的方法可以强制队列中的对象占用连续的内存块.但是,有些技术适用于特殊情况.

从高层次上讲,这些技术涉及使用字节数组以及将数据“串行化”到阵列或从阵列中“串行化”.如果要存储非常简单的对象,这实际上非常有效.例如,如果要存储一堆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;
  }

  ...
}

内容总结

以上是互联网集市为您收集整理的Java优先级队列实现-内存位置全部内容，希望文章能够帮你解决Java优先级队列实现-内存位置所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端