このコードをより速く実行するにはどうすればいいですか

Question

配列には数字が含まれており、ソートされません。その長さは100000倍になる可能性があります。 各桁の右に小さい数字を数える必要があります。

例：

100, 10, 10, 10, 10]should return 4, 0, 0, 0, 0 

    1, 2, 3    should return 0, 0, 0 

    1, 2, 0    should return 1, 1, 0 

    1, 2, 1    should return 0, 1, 0 

タスク：私は実行するための100回のテストを持っており、目標はそれらをすべて下に12msのを行うことです。 次の関数は、AVLツリーの実装です。仕事は終わりますが、十分に速くはありません。

12秒で100のうち48を実行します。私が持っている

===============

function smaller(arr) { 
    function TreeNode(key) { 
    this.key = key; 
    this.size = 1; 
    this.height = 1; 
    this.left = null; 
    this.right = null; 
    this.count = 1; 
    } 
    var size  = (node) => node == null ? 0 : node.size + node.count - 1; 
    var height  = (node) => node == null ? 0 : node.height; 
    var getBalance = (node) => node == null ? 0 : height(node.left) - height(node.right); 

    var rotateRight = function(root) { 
    var newRoot  = root.left; 
    var rightSubTree = newRoot.right; 
    newRoot.right = root; 
    root.left  = rightSubTree; 
    root.height  = Math.max(height(root.left), height(root.right)) + 1; 
    newRoot.height = Math.max(height(newRoot.left), height(newRoot.right)) + 1; 
    root.size  = size(root.left) + size(root.right) + 1; 
    newRoot.size  = size(newRoot.left) + size(newRoot.right) + 1; 
    return newRoot; 
    } 
    var rotateLeft = function(root) { 
    var newRoot  = root.right; 
    var leftSubTree = newRoot.left; 
    newRoot.left = root; 
    root.right  = leftSubTree; 
    root.height  = Math.max(height(root.left), height(root.right)) + 1; 
    newRoot.height = Math.max(height(newRoot.left), height(newRoot.right)) + 1; 
    root.size  = size(root.left) + size(root.right) + 1; 
    newRoot.size = size(newRoot.left) + size(newRoot.right) + 1; 
    return newRoot; 
    } 
    var insertIntoAVL = function(node, key, count, index) { 
    if(node == null)return new TreeNode(key); 
    if(key < node.key){node.left = insertIntoAVL(node.left, key, count, index);} 
    if(key == node.key){count[index] = count[index] + size(node.left); node.count++; return node;} 
    if(key > node.key){node.right = insertIntoAVL(node.right, key, count, index); count[index] = count[index] + size(node.left) + node.count;} 
    node.height = Math.max(height(node.left), height(node.right)) + 1; 
    node.size = size(node.left) + size(node.right) + 1; 
    var balance = getBalance(node); 
    if(balance > 1 && key < node.left.key){return rotateRight(node);} 
    if(balance < -1 && key > node.right.key){return rotateLeft(node);} 
    if(balance > 1 && key > node.left.key){node.left = rotateLeft(node.left); return rotateRight(node);} 
    if(balance < -1 && key < node.right.key){node.right = rotateRight(node.right); return rotateLeft(node);} 
    return node; 
    } 
    var countSmallerOnRight = function(arr) { 
    var result = new Array(arr.length).fill(0); 
    var root = null; 
    for (var i = arr.length; i--;){root = insertIntoAVL(root, arr[i], result, i);} 
    return result; 
    } 
    return countSmallerOnRight(arr); 
    } 

=================

速いがまだ十分に速くない第2のアプローチ。 12msで100のうち84を実行します。

=================

function smaller(arr) { 
    function BSTNode(val, count) { 
    this.dup = 1; 
    this.left = null; 
    this.right = null; 
    this.val = val; 
    this.count = count; 
    } 
    var countSmaller = arr => { 
    var result = []; 
    var root = null; 
    for (var i = arr.length; i--;){root = insert(root, arr[i], result, 0, i);} 
    return result; 
    } 
    var insert = (root, num, result, sum, i) => { 
    if (root == null) { 
     root = new BSTNode(num, 0); 
     result[i] = sum; 
     return root; 
    } else if (root.val == num) { 
     root.dup++; 
     result[i] = sum + root.count; 
     return root; 
    } else if (root.val > num) { 
     root.count++; 
     root.left = insert(root.left, num, result, sum, i); 
    } else { 
     root.right = insert(root.right, num, result, sum + root.count + root.dup, i); 
    } 
    return root; 
    } 
    return countSmaller(arr); 
} 

=================

Iなぜ彼らは目標を達成していないのか、どのように改善できるかを理解したいと思います。

Answer 1

OK、リファクタリングを実行することでスピードを上げることができました。

function BSTNode(val) { 
    this.dup = 1; 
    this.left = null; 
    this.right = null; 
    this.val = val; 
    this.count = 0; 
} 

var insert = (root, num, result, sum, i) => { 
    if (root === null) { 
     result[i] = sum; 
     return new BSTNode(num); 
    } 

    if (root.val === num) { 
     root.dup++; 
     result[i] = sum + root.count; 
    } else if (root.val > num) { 
     root.count++; 
     root.left = insert(root.left, num, result, sum, i); 
    } else { 
     root.right = insert(root.right, num, result, sum + root.count + root.dup, i); 
    } 
    return root; 
} 

function smaller(arr) { 
    var result = Array(arr.length).fill(0); 
    var root = null; 
    for (var i = arr.length; i--;) 
     root = insert(root, arr[i], result, 0, i); 
    return result; 
} 

私はこの機能を実行するには時間がかかることに気付いています。我々は12msではなく12秒で100回の計算を話している。私は大きな配列と多くの異なる値（浮動小数点数または8ビットのような整数の全範囲を使用するか0：255）を推測します。

まだ異なるアプローチを試しています。

Answer 2

これはちゃんとしていますが、私は何のためにこれに挑戦しているのですか（コードワーアですか？）私はそれをテストできません。木は使わない。私は単純なリンクリストで、ツリーなしでそれを行うことができます

function smaller(arr) { 
    var out = [0]; 
    var len = arr.length; 
    for (var i=len - 2; i >= 0; i--) { 
     var c = 0; 
     for (var j = i + 1; j < len; j++) { 
     if (arr[i] == arr[j]) { 
      c += out[j - i - 1]; 
      break; 
     } else if (arr[i] > arr[j]) { 
      c++; 
     } 
     } 
     out.unshift(c); 
    } 
    return out; 
} 
var testArr = [1,5,2,7,44,878,1,22,999,222,1,1,1,1,1,1,1,1,1,1,1,1,1]; 
alert(smaller(testArr).join(",")); 

Answer 3

：

function Node(value, next){ 
 
\t this.value = value; 
 
\t this.next = next; 
 
\t this.count = 1; 
 
} 
 

 
function smaller(array){ 
 
\t return array.reduceRight(function(root, value, i){ 
 
\t \t var count = 0; 
 
\t \t for(var prev = root, node; (node = prev.next) && node.value < value; prev = node) 
 
\t \t \t count += node.count; 
 
\t \t root.counts[i] = count; 
 
\t \t 
 
\t \t if(node && node.value === value){ 
 
\t \t \t node.count++; 
 
\t \t }else{ 
 
\t \t \t prev.next = new Node(value, prev.next); 
 
\t \t } 
 
\t \t 
 
\t \t return root; 
 
\t }, { 
 
\t \t next: null, 
 
\t \t counts: Array(array.length).fill(0) 
 
\t }).counts; 
 
} 
 

 
console.log("100, 10, 10, 10, 10 -> " + smaller([100, 10, 10, 10, 10])); 
 
console.log("1, 2, 3 -> " + smaller([1, 2, 3])); 
 
console.log("1, 2, 0 -> " + smaller([1, 2, 0])); 
 
console.log("1, 2, 1 -> " + smaller([1, 2, 1])); 
 

 
var sampleData = Array.from({length: 100000},() => 0|(Math.random() * 100)); 
 

 
console.time("100000 items"); 
 
smaller(sampleData); 
 
console.timeEnd("100000 items");

はと 4実装のコンソールで簡単なテストをしました100000値。

• あなたの最初のコード：〜
• 2番目のコード700-800ms：〜

を25000ms：〜は

ジェームスコード15-30ms：〜することは

私のコードを350-400msすべての実装は、同じ事前生成された100000項目の配列でテストされます。

ノードコンストラクタをsmallerからエクスポートすると、2番目と3番目のテストが30msよりも15msで実行される可能性が高くなります。これは、JSエンジンがコードを最適化する方法と関係があります。また、配列を0の値でプリフィルすると、コードが10倍ほど速くなりました。

ただし、100以上の異なる値を持つ短い配列または配列では、その差は小さくなります。