作者kiwistar (暴风雪之喀秋莎)
看板java
标题[问题] PriorityQueue的同步问题？
时间Thu Mar 22 19:34:35 2018
这里使用的是Java API提供的PriorityQueue.class
java.util.PriorityQueue<E>
我建构一个资料类别MapNode，当中Override了compareTo方法
依照MapNode下面的一个叫做distance的int型态变数作为比较标准
实作Dijkstra's algorithm，始终得到奇怪的结果
作业要求找出1到其他10个点的最小距离(共200个点)
我输出的结果有大概6个是正确数字，另外4个答案则不对
使用Eclipse 做debug发现，在前面几个cycle，PriorityQueue都能从我的清单里面
找出正确的那个，poll出来(我用过remove(), poll()，结果都依样)
从某一步开始，PriorityQueue给出来的东西不再是距离最小的那一个
应该说，PriorityQueue本身是用heap实作，
所以他应该会把我要的东西放在root，前几次cycle有看到这个现象
但某次开始突然就不这麽做了
因为前面几次的结果都正确，我想应该不是override定义的问题
有没有可能是synchronization还是什麽其他的问题......
5
这问题困扰我很久，结果真的跳进去debug 200个节点的图，发现是官方的资料结构
没有正确运作，还满傻眼的。原先一直以为是我的演算法有逻辑问题......
感谢大家！！
--
1F：推 perry27: 要红就要有特色 想到盗总就是盗垒 锋哥就是轰炮 建民就是10/02 10:37
2F：→ xyz4594: 持久10/02 10:37
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 123.194.179.102
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/java/M.1521718479.A.D2A.html
3F：→ kiwistar: 自问自答：根据h3ap 03/22 20:08
4F：→ kiwistar: 根据heap的原理，要让他洗牌，需要做insert 或是remove 03/22 20:09
5F：→ kiwistar: 的操作，所以修改距离後加上一行add(E)就可以了，呜呜， 03/22 20:09
6F：→ kiwistar: 还我数十小时的光阴来 03/22 20:09