Я пытаюсь предоставить свою реализацию Heap, поэтому я создал этот скрипт: < /p>
class BinaryHeap {
array;
comparator;
constructor(comparator) {
this.array = [];
this.comparator = comparator;
}
static getParentIndex(index) {
return (index - 1) >> 1;
}
static getLeftChildIndex(index) {
return 2 * index + 1;
}
static getRightChildIndex(index) {
return 2 * index + 2;
}
#swap(index1, index2) {
[this.array[index1], this.array[index2]] = [
this.array[index2],
this.array[index1],
];
}
#compare(index1, index2) {
return this.comparator(this.array[index1], this.array[index2]);
}
siftDown(index) {
const value = this.array[index];
const end = BinaryHeap.getParentIndex(this.array.length - 1);
while (index = this.array.length || this.#compare(left, right) < 0
? left
: right;
if (this.comparator(value, this.array[childIndex]) < 0) break;
this.array[index] = this.array[childIndex];
index = childIndex;
}
this.array[index] = value;
}
siftUp(index) {
const value = this.array[index];
let parentIndex = BinaryHeap.getParentIndex(index);
while (
parentIndex >= 0 &&
this.comparator(this.array[parentIndex], value) > 0
) {
this.array[index] = this.array[parentIndex];
index = parentIndex;
parentIndex = BinaryHeap.getParentIndex(index);
}
this.array[index] = value;
}
pop() {
if (this.array.length === 0) return;
if (this.array.length === 1) return this.array.pop();
this.#swap(0, this.array.length - 1);
const value = this.array.pop();
this.siftDown(0);
return value;
}
push(item) {
this.array.push(item);
this.siftUp(this.array.length - 1);
}
}
function compareFn(a, b) {
return a - b;
}
const heap = new BinaryHeap(compareFn);
for (let i = 0; i < 10_000_000; i++) { heap.push(i) }
for (let i = 0; i < 10_000_000; i++) { heap.pop() }
< /code>
, а затем профилируйте его с помощью команды, используя 0x, как предложено node.js - Создание страницы документации Flamegraph < /p>
0x -o heap.js
< /code>
Но полученный график пламени, похоже, отсутствует много образцов. Функции Push, POP, Siftup и Siftdown отображаются только один раз, а иногда и в 0 раз из 102 образцов. Куда пошли остальные 100-102 образцов? И какой большой *(анонимный) блок, который был отобран в 84 раза? src = "https://i.sstatic.net/xvdv3gii.png"/>
Перемещение кода в HTML-файл, а затем используя встроенный профилировщик производительности Chrome, я получаю гораздо более подробную визуализацию без столько же отсутствующих данных. Это то, что я тоже хочу от 0x.>
Подробнее здесь: https://stackoverflow.com/questions/795 ... in-the-gen
