在下面的代码中,在我的测试用例中,indexOfSlow
大约比indexOf
慢17倍,尽管前者进行的比较比后者少.
Why is that?个
(我的直觉是,indexOf
的卓越性能归功于顺序数组访问,它具有缓存等好处--但我想确切地知道)
来self 的机器的性能数据:
| elementCount | indexOf msec | indexOfSlow msec | slow/fast |
|--------------+--------------+------------------+-----------|
| 10000 | 41 | 852 | 21 |
| 20000 | 232 | 3387 | 15 |
| 30000 | 375 | 6642 | 18 |
| 40000 | 710 | 12699 | 18 |
| 50000 | 1197 | 19182 | 16 |
|--------------+--------------+------------------+-----------|
| average | | | 17.6 |
注:Java的PriorityQueue.indexOf()
与我的indexOf
类似,所以它不会像我的indexOfSlow
那样try 爬树和早点停车.
class Heap<T extends Comparable<T>> {
public static void main(String[] args) {
int elementCount = 50_000;
final List<Integer> elements = new ArrayList<>(elementCount);
for (int i = 0; i < elementCount; i++)
elements.add(i);
for (int j = 0; j < 3; j++) {
final var heap = new Heap<Integer>();
for (int i : elements)
heap.add(i);
assert heap.peek() == 0;
final long nanoBefore = System.nanoTime();
for (int i = elementCount; i > 0; i--)
heap.indexOf(i - 1);
// heap.indexOfSlow(i - 1);
final long nanoAfter = System.nanoTime();
if (j > 0) // discard first round as warmup
System.out.println("Time taken: " + (nanoAfter - nanoBefore) / 1_000_000 + " msec");
}
}
private final ArrayList<T> list = new ArrayList<>();
public T peek() {
return list.isEmpty() ? null : list.get(0);
}
private void siftUp(int i, T value) {
while (i > 0) {
int parentI = (i - 1) / 2;
final T parentValue = list.get(parentI);
if (parentValue.compareTo(value) <= 0)
return;
list.set(parentI, value);
list.set(i, parentValue);
i = parentI;
}
}
public void add(T value) {
list.add(value);
siftUp(list.size() - 1, value);
}
public int indexOf(T value) {
final int size = list.size();
if (size > 0) {
for (int i = 0; i < list.size(); i++) {
if (value.compareTo(list.get(i)) == 0)
return i;
}
}
return -1;
}
public int indexOfSlow(T value) {
final int size = list.size();
if (size > 0) {
Queue<Integer> childrenToVisit = new LinkedList<>();
childrenToVisit.add(0);
while (!childrenToVisit.isEmpty()) {
int i = childrenToVisit.poll();
final int cmp = list.get(i).compareTo(value);
if (cmp == 0)
return i;
if (cmp > 0)
continue;
int rightChildIdx = (i + 1) * 2;
int leftChildIdx = rightChildIdx - 1;
if (leftChildIdx < size)
childrenToVisit.add(leftChildIdx);
if (rightChildIdx < size)
childrenToVisit.add(rightChildIdx);
}
}
return -1;
}
}