現在、私は非常に奇妙なパフォーマンスの問題に苦しんでいます。SlowHeapにかかる平均は1448.623msですが、FastHeapに必要なのは550.425msだけです。私はそれを何度も見てきましたが、2つの違いは、最初の要素が_arrの先頭に「未定義」の要素を使用し、2番目の要素が使用しないことだけです。ただし、どちらも同じ操作を実行します。下のコードで確認したこと。
この問題に光を当てることができる人はいますか?
let slowHeapOperationCount = 0
let fastHeapOperationCount = 0
let slowHeapExchanged = []
let fastHeapExchanged = []
function SlowHeap(cmp = (a, b) => a > b ? 1 : a < b ? -1 : 0) {
this.cmp = cmp
this._arr = [undefined]
this.size = 0
}
function FastHeap(cmp = (a, b) => a > b ? 1 : a < b ? -1 : 0) {
this.cmp = cmp
this._arr = []
this.size = 0
}
SlowHeap.prototype.bubbleUp = function (cmp, _arr, val) {
let idxNr = this.size, parentIdxNr = idxNr >> 1
while (idxNr > 0 && cmp(_arr[parentIdxNr], val) > 0) {
slowHeapExchanged.push([_arr[parentIdxNr], val])
_arr[idxNr] = _arr[parentIdxNr]
_arr[parentIdxNr] = val
idxNr = parentIdxNr
parentIdxNr = idxNr >> 1
slowHeapOperationCount++
}
}
FastHeap.prototype.bubbleUp = function (cmp, _arr, val) {
var idxNr = this.size,
parentIdxNr = ((idxNr - 1) / 2) | 0;
while (idxNr > 0 && cmp(_arr[parentIdxNr], val) > 0) {
fastHeapExchanged.push([_arr[parentIdxNr], val])
_arr[idxNr] = _arr[parentIdxNr];
_arr[parentIdxNr] = val;
idxNr = parentIdxNr;
parentIdxNr = ((idxNr - 1) / 2) | 0;
fastHeapOperationCount++
}
}
SlowHeap.prototype.push = function (val) {
++this.size
this._arr.push(val)
this.bubbleUp(this.cmp, this._arr, val)
return this.size
}
FastHeap.prototype.push = function (val) {
this._arr.push(val);
this.bubbleUp(this.cmp, this._arr, val);
return ++this.size;
}
const itemCount = 4000000
const slowHeap = new SlowHeap()
const fastHeap = new FastHeap()
//
// Append the same Number Collection to each Heap:
const numberCollection = []
for (let idxNr = 0; idxNr < itemCount; idxNr++) numberCollection.push(Math.random())
//
// Benchmark for the Slow Heap:
console.time('SlowHeap')
for (let idxNr = 0; idxNr < itemCount; idxNr++) {
slowHeap.push(numberCollection[idxNr])
}
console.timeEnd('SlowHeap')
//
// Benchmark for the Fast Heap:
console.time('FastHeap')
for (let idxNr = 0; idxNr < itemCount; idxNr++) {
fastHeap.push(numberCollection[idxNr])
}
console.timeEnd('FastHeap')
//
// Verify the "_arr" from the Slow Heap against the Fast Heap:
for (let idxNr = 0; idxNr < itemCount; idxNr++) {
if (slowHeap._arr[idxNr + 1] !== fastHeap._arr[idxNr]) console.log('Unequal value found!')
}
if (slowHeapExchanged.length !== fastHeapExchanged.length) console.log('Help! Comp. is not equal.')
for (let idxNr = 0, maxNr = slowHeapExchanged.length; idxNr < maxNr; idxNr++) {
if (slowHeapExchanged[idxNr][0] !== fastHeapExchanged[idxNr][0] || slowHeapExchanged[idxNr][1] !== fastHeapExchanged[idxNr][1]) {
console.log('Help!')
}
}
console.log(slowHeapOperationCount)
console.log(fastHeapOperationCount)
詳細については何も知りませんが、V8最適化が有効化/無効化されているようです。に置き換えるundefined
と0.0
、SlowHeap
それほど遅くはありません(実際、FastHeap
私よりも高速です)。
私の推測では、配列をfloat(Math.random()
)で埋めているので、配列にすべて同じタイプのアイテムが含まれている限り、実行できる最適化があります。
型の不一致(undefined
floatではない)を導入すると、V8はおそらくより一般的な型の配列に切り替えて、最適化を控える必要があるかもしれません。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加