JS 执行速度的差异在哪一点？

Question

我正在研究 Javascript 算法。

这是 dijkstra 算法的问题。

但在最后一种情况下我总是遇到 TLE（超出时间限制）。

我能知道哪一点使我的代码变慢吗？

我尝试了如下多种方法，

• 没有使用 forEach 的函数构造函数
• 控制台输出，而是
• 使用 require('readline') 进行输入，
• 而不使用递归堆化，

这是问题链接。

https://onlinejudge.u-aizu.ac。 jp/courses/lesson/1/ALDS1/12/ALDS1_12_C

这是我的解决方案。

function MinPQ() {
    this.heap = [];
}
MinPQ.prototype.swap = function (i, j) {
    const temp = this.heap[i];
    this.heap[i] = this.heap[j];
    this.heap[j] = temp;
};
MinPQ.prototype.insert = function (n) {
    const parentIdx = (idx) => Math.floor((idx - 1) * 0.5);

    this.heap.push(n);

    let curr = this.heap.length - 1;
    let parent = parentIdx(curr);

    while (curr > 0 && this.compare(curr, parent)) {
        this.swap(curr, parent);
        curr = parent;
        parent = parentIdx(curr);
    }
};
MinPQ.prototype.shift = function () {
    const heapify = (idx) => {
        let l = idx * 2 + 1;
        let r = idx * 2 + 2;
        let minIdx = idx;

        if (l < this.heap.length && this.compare(l, minIdx)) {
            minIdx = l;
        }
        if (r < this.heap.length && this.compare(r, minIdx)) {
            minIdx = r;
        }

        if (minIdx !== idx) {
            this.swap(idx, minIdx);
            heapify(minIdx);
        }
    };

    this.swap(0, this.heap.length - 1);
    const root = this.heap.pop();
    heapify(0);
    return root;
};
MinPQ.prototype.compare = function (i, j) {
    return this.heap[i][1] < this.heap[j][1];
};

function solution(input) {
    const n = Number(input.shift());
    const G = Array(n);
    for (let i = 0; i < n; i++) {
        const [u, k, ...adjs] = input.shift().split(' ').map(Number);
        G[u] = [];
        for (let j = 0; j < k; j++) {
            const v = adjs[2 * j];
            const c = adjs[2 * j + 1];
            G[u][v] = c;
        }
    }

    return dijkstra(n, G)
        .map((e, idx) => `${idx} ${e}`)
        .join('\n');
}

function dijkstra(n, G) {
    const minPQ = new MinPQ();
    const d = Array(n).fill(Infinity);
    let count = 0;

    minPQ.insert([0, 0]);

    while (count < n) {
        const node = minPQ.shift();
        const [u, cost] = node;

        if (d[u] < Infinity) continue;
        d[u] = cost;
        count++;

        G[u].forEach((e, idx) => {
            minPQ.insert([idx, cost + e]);
        });
    }
    return d;
}

(function (test) {
    const printSolution = (input) => console.log(solution(input));
    if (test) {
        printSolution([
            '5',
            '0 3 2 3 3 1 1 2',
            '1 2 0 2 3 4',
            '2 3 0 3 3 1 4 1',
            '3 4 2 1 0 1 1 4 4 3',
            '4 2 2 1 3 3',
        ]);
        console.log('--');
        printSolution([
            '9',
            '0 2 1 1 3 13',
            '1 3 0 1 2 1 4 11',
            '2 2 5 1 1 1',
            '3 3 4 1 0 13 6 1',
            '4 4 1 11 5 1 3 1 7 4',
            '5 3 2 1 8 7 4 1',
            '6 2 3 1 7 1',
            '7 3 4 4 6 1 8 1',
            '8 2 5 7 7 1',
        ]);
        return;
    }

    printSolution(
        require('fs').readFileSync('/dev/stdin', 'utf-8').split('\n')
    );
})(0);

这是最后一个案例通过的解决方案。

var h = [],hs = 0;
h[0] = new Array(2);
h[0][0] = -1;h[0][1] = -1;
 
function insert(key){
    h[++hs] = key;
 
    var i = hs;
 
    while(h[i][1] < h[Math.floor(i / 2)][1]){
        var ex = h[i];
        h[i] = h[Math.floor(i / 2)];
        h[Math.floor(i / 2)] = ex;
        i = Math.floor(i / 2);
    }
}
 
function extract(){
    if(hs <= 0)
        return;
 
    var ret = h[1];
 
    h[1] = h[hs--];
 
    i = 1;
    while((i * 2 <= hs && h[i][1] > h[i * 2][1]) || (i * 2 + 1 <= hs && h[i][1] > h[i * 2 + 1][1])){
        var l = i * 2;var r = i * 2;
        if(i * 2 + 1 <= hs)
            r++;
        var m = h[l][1] <= h[r][1] ? l : r;
        var ex = h[i];
        h[i] = h[m];
        h[m] = ex;
        i = m;
 
    }
    return ret;
}


function Main(input){
    input = input.split("\n");
    var n = parseInt(input[0],10);

    var graph = new Array(n);

    for(var i = 0;i < n;i++){
        input[i + 1] = input[i + 1].split(" ");
        var u = parseInt(input[i + 1][0],10);
        var k = parseInt(input[i + 1][1],10);
        graph[u] = new Array(k);
        for(var j = 0;j < k;j++)
            graph[u][j] = new Array(2);
        for(var j = 0;j < k;j++){
            graph[u][j][0] = parseInt(input[i + 1][j * 2 + 2],10);
            graph[u][j][1] = parseInt(input[i + 1][j * 2 + 3],10);
        }
    }

    var count = 1;
    var sum = Array(n);
    for(var i = 0;i < n;i++)
        sum[i] = 1000000000;
    sum[0] = 0;
    for(var i = 0;i < graph[0].length;i++){
        insert(graph[0][i]);
    } 
    while(count < n){
        var aa = extract();
        if(sum[aa[0]] < 1000000000)
            continue;

        sum[aa[0]] = aa[1];
        count++;

        for(var i = 0;i < graph[aa[0]].length;i++){
            graph[aa[0]][i][1] += sum[aa[0]];
            insert(graph[aa[0]][i]);
        }
    }

    for(var i = 0;i < n;i++){
        console.log(i + " " + sum[i]);
    }
}

Main(require("fs").readFileSync("/dev/stdin","utf8"));