意外行为 java 优先级队列。对象添加一次但轮询两次。怎么可能?
Unexpected behaviour java priority queue. Object added once but polled out twice. How could it be possible?
import java.util.*;
public class Main {
public static void main (String[] args) {
Solution solution = new Solution();
int[] res = solution.assignTasks(new int[]{3,3,2}, new int[]{1,2,3,2,1,2});
}
}
class Solution {
public int[] assignTasks(int[] servers, int[] tasks) {
PriorityQueue<Pair> free = new PriorityQueue(); // (wt, id, time)
PriorityQueue<Pair> busy = new PriorityQueue(); // (time, wt, id)
for (int i = 0; i < servers.length; i++) {
free.add(new Pair(servers[i], i, 0));
System.out.println("Free Added " + i + " " + servers[i] + " " + i + " " + 0 + " " + free.size());
}
int[] ans = new int[tasks.length];
for (int i = 0; i < tasks.length; i++) {
Pair b = busy.peek();
while (b != null && b.a <= i) {
busy.poll();
System.out.println("Busy Polled " + i + " " + b.a + " " + b.b + " " + b.c + " " + busy.size());
free.add(new Pair(b.b, b.c, b.a));
System.out.println("Free Added " + i + " " + b.b + " " + b.c + " " + b.a + " " + free.size());
b = busy.peek();
}
Pair p = free.poll();
int wt = p.a;
int id = p.b;
// int time = p.c;
System.out.println("Free Polled " + i + " " + p.a + " " + p.b + " " + p.c + " " + free.size());
ans[i] = id;
busy.add(new Pair(i + tasks[i], wt, id));
System.out.println("Added to Busy " + i + " " + (i + tasks[i]) + " " + p.a + " " + p.b + " " + busy.size());
}
return ans;
}
}
class Pair implements Comparable<Pair> {
int a, b, c;
Pair(int x, int y, int z) {
a = x;
b = y;
c = z;
}
public int compareTo(Pair p) {
if (this.a == p.a) {
if (this.b == p.b) return this.c - p.c;
return this.b = p.b;
}
return this.a - p.a;
}
}
我在优先级队列中使用 Pair class 插入了三胞胎,并且 一对从队列中被轮询两次并且只被插入一次。怎么可能?
我还附上了我添加到调试中的打印语句的控制台输出。突出显示异常行为。
代码的输出:(注意输出中的行为。突出显示它 (3,0,0) 轮询两次?)
Free Added 0 3 0 0 1 (Added to the queue)
Free Added 1 3 1 0 2
Free Added 2 2 2 0 3
Free Polled 0 2 2 0 2
Added to Busy 0 1 2 2 1
Busy Polled 1 1 2 2 0
Free Added 1 2 2 1 3
Free Polled 1 2 2 1 2
Added to Busy 1 3 2 2 1
Free Polled 2 3 0 0 1 (Polled 1st time)
Added to Busy 2 5 3 0 2
Busy Polled 3 3 2 2 1
Free Added 3 2 2 3 2
Free Polled 3 2 2 3 1
Added to Busy 3 5 2 2 2
Free Polled 4 3 0 0 0 (Polled 2nd time)
Added to Busy 4 5 3 0 3
Busy Polled 5 5 3 0 2
Free Added 5 3 0 5 1
Busy Polled 5 5 3 0 1
Free Added 5 3 0 5 2
Busy Polled 5 5 3 2 0
Free Added 5 3 2 5 3
Free Polled 5 3 0 5 2
Added to Busy 5 7 3 0 1
问题来自最近的 Leetcode 竞赛,现在已经结束了。 Link 到 discussion section of the question. Link to question
Link 至 IDE run
不是很清楚,但我认为你的问题是由于 compareTo
.
的不正确实现引起的
public int compareTo(Pair p) {
if (this.a == p.a) {
if (this.b == p.b) return this.c - p.c;
return this.b = p.b;
}
return this.a - p.a;
}
问题 #1
return this.b = p.b;
这个 returns p.b
作为副作用,它将 p.b
分配给 this.b
。这是完全错误的。
你的意思可能是return this.b - p.b;
请注意,由于您的 compareTo
方法正在 更改 Pair
对象之一,因此结果将变得一团糟。这可能就是为什么某些 Pair
对象 出现 不止一次被返回的原因。 (事实上 ,它们是不同的 Pair
对象......但是你已经改变它们以便它们在 c
字段中具有相同的值。)
问题 #2
表达式 this.c - p.c
在极端情况下给出了错误的答案。例如,this.c
非常大而 p.c
为负数,则减法可能溢出为负数,表示 this.c
“小于” p.c
...事实并非如此。
有关详细信息,请参阅 Java Integer compareTo() - why use comparison vs. subtraction?。
以下是比较两个 int
值以给出与 compareTo
合同兼容的结果的几种正确方法:
手写:
if (this.c == p.c) {
return 0;
} else if (this.c < p.c) {
return -1;
} else {
return +1;
}
使用条件表达式:
return (this.c == p.c) ? 0 : ((this.c < p.c) ? -1 : +1);
使用Integer.compare
return Integer.compare(this.c, p.c);
正确实施
如果我们假设 Pair
对象应该是不可变的,那么这是一个正确的1 实现:
class Pair implements Comparable<Pair> {
final int a, b, c;
Pair(int x, int y, int z) {
a = x;
b = y;
c = z;
}
public int compareTo(Pair p) {
if (this.a == p.a) {
if (this.b == p.b) {
return Integer.compare(this.c, p.c);
} else {
return Integer.compare(this.b, p.b);
}
} else {
return Integer.compare(this.a, p.a);
}
}
}
问:为什么要将字段声明为 final
?
答:为了防止 意外 更改字段,在 Pair
class 本身以及其他 classes class 及其字段是可访问的。
问:为什么要用if ... else
?
A:因为比较清楚。并且因为 JIT 编译器在任何一种情况下都应该生成等效(最佳)代码。
问:compare
呢?方法调用会不会效率低下?
答:可能不会。方法调用可能会被 JIT 编译器内联。
问:效率重要吗?
答:在你的例子中是无关紧要的。一般情况下是可能无关2.
1 - class 名称 Pair
也不正确。应该是Triple
。
2 - 只有在 1) 对代码进行基准测试,2) 对其进行概要分析,以及 3) 确定 compareTo
方法确实 之后,您才应该尝试手动优化它热点.
import java.util.*;
public class Main {
public static void main (String[] args) {
Solution solution = new Solution();
int[] res = solution.assignTasks(new int[]{3,3,2}, new int[]{1,2,3,2,1,2});
}
}
class Solution {
public int[] assignTasks(int[] servers, int[] tasks) {
PriorityQueue<Pair> free = new PriorityQueue(); // (wt, id, time)
PriorityQueue<Pair> busy = new PriorityQueue(); // (time, wt, id)
for (int i = 0; i < servers.length; i++) {
free.add(new Pair(servers[i], i, 0));
System.out.println("Free Added " + i + " " + servers[i] + " " + i + " " + 0 + " " + free.size());
}
int[] ans = new int[tasks.length];
for (int i = 0; i < tasks.length; i++) {
Pair b = busy.peek();
while (b != null && b.a <= i) {
busy.poll();
System.out.println("Busy Polled " + i + " " + b.a + " " + b.b + " " + b.c + " " + busy.size());
free.add(new Pair(b.b, b.c, b.a));
System.out.println("Free Added " + i + " " + b.b + " " + b.c + " " + b.a + " " + free.size());
b = busy.peek();
}
Pair p = free.poll();
int wt = p.a;
int id = p.b;
// int time = p.c;
System.out.println("Free Polled " + i + " " + p.a + " " + p.b + " " + p.c + " " + free.size());
ans[i] = id;
busy.add(new Pair(i + tasks[i], wt, id));
System.out.println("Added to Busy " + i + " " + (i + tasks[i]) + " " + p.a + " " + p.b + " " + busy.size());
}
return ans;
}
}
class Pair implements Comparable<Pair> {
int a, b, c;
Pair(int x, int y, int z) {
a = x;
b = y;
c = z;
}
public int compareTo(Pair p) {
if (this.a == p.a) {
if (this.b == p.b) return this.c - p.c;
return this.b = p.b;
}
return this.a - p.a;
}
}
我在优先级队列中使用 Pair class 插入了三胞胎,并且 一对从队列中被轮询两次并且只被插入一次。怎么可能? 我还附上了我添加到调试中的打印语句的控制台输出。突出显示异常行为。
代码的输出:(注意输出中的行为。突出显示它 (3,0,0) 轮询两次?)
Free Added 0 3 0 0 1 (Added to the queue)
Free Added 1 3 1 0 2
Free Added 2 2 2 0 3
Free Polled 0 2 2 0 2
Added to Busy 0 1 2 2 1
Busy Polled 1 1 2 2 0
Free Added 1 2 2 1 3
Free Polled 1 2 2 1 2
Added to Busy 1 3 2 2 1
Free Polled 2 3 0 0 1 (Polled 1st time)
Added to Busy 2 5 3 0 2
Busy Polled 3 3 2 2 1
Free Added 3 2 2 3 2
Free Polled 3 2 2 3 1
Added to Busy 3 5 2 2 2
Free Polled 4 3 0 0 0 (Polled 2nd time)
Added to Busy 4 5 3 0 3
Busy Polled 5 5 3 0 2
Free Added 5 3 0 5 1
Busy Polled 5 5 3 0 1
Free Added 5 3 0 5 2
Busy Polled 5 5 3 2 0
Free Added 5 3 2 5 3
Free Polled 5 3 0 5 2
Added to Busy 5 7 3 0 1
问题来自最近的 Leetcode 竞赛,现在已经结束了。 Link 到 discussion section of the question. Link to question Link 至 IDE run
不是很清楚,但我认为你的问题是由于 compareTo
.
public int compareTo(Pair p) {
if (this.a == p.a) {
if (this.b == p.b) return this.c - p.c;
return this.b = p.b;
}
return this.a - p.a;
}
问题 #1
return this.b = p.b;
这个 returns p.b
作为副作用,它将 p.b
分配给 this.b
。这是完全错误的。
你的意思可能是return this.b - p.b;
请注意,由于您的 compareTo
方法正在 更改 Pair
对象之一,因此结果将变得一团糟。这可能就是为什么某些 Pair
对象 出现 不止一次被返回的原因。 (事实上 ,它们是不同的 Pair
对象......但是你已经改变它们以便它们在 c
字段中具有相同的值。)
问题 #2
表达式 this.c - p.c
在极端情况下给出了错误的答案。例如,this.c
非常大而 p.c
为负数,则减法可能溢出为负数,表示 this.c
“小于” p.c
...事实并非如此。
有关详细信息,请参阅 Java Integer compareTo() - why use comparison vs. subtraction?。
以下是比较两个 int
值以给出与 compareTo
合同兼容的结果的几种正确方法:
手写:
if (this.c == p.c) { return 0; } else if (this.c < p.c) { return -1; } else { return +1; }
使用条件表达式:
return (this.c == p.c) ? 0 : ((this.c < p.c) ? -1 : +1);
使用
Integer.compare
return Integer.compare(this.c, p.c);
正确实施
如果我们假设 Pair
对象应该是不可变的,那么这是一个正确的1 实现:
class Pair implements Comparable<Pair> {
final int a, b, c;
Pair(int x, int y, int z) {
a = x;
b = y;
c = z;
}
public int compareTo(Pair p) {
if (this.a == p.a) {
if (this.b == p.b) {
return Integer.compare(this.c, p.c);
} else {
return Integer.compare(this.b, p.b);
}
} else {
return Integer.compare(this.a, p.a);
}
}
}
问:为什么要将字段声明为 final
?
答:为了防止 意外 更改字段,在 Pair
class 本身以及其他 classes class 及其字段是可访问的。
问:为什么要用if ... else
?
A:因为比较清楚。并且因为 JIT 编译器在任何一种情况下都应该生成等效(最佳)代码。
问:compare
呢?方法调用会不会效率低下?
答:可能不会。方法调用可能会被 JIT 编译器内联。
问:效率重要吗?
答:在你的例子中是无关紧要的。一般情况下是可能无关2.
1 - class 名称 Pair
也不正确。应该是Triple
。
2 - 只有在 1) 对代码进行基准测试,2) 对其进行概要分析,以及 3) 确定 compareTo
方法确实 之后,您才应该尝试手动优化它热点.