Wie kann ich diesen Code schneller ausführen

Question

Das Array enthält Ziffern und es ist unsortiert. Seine Länge könnte so groß wie 100000 sein. Ich muss die kleineren Zahlen rechts von jeder Ziffer zählen.

Beispiel:

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 

Aufgabe: Ich habe 100 Tests durchzuführen und das Ziel ist es, sie alle unter 12ms zu tun. Die folgende Funktion ist eine AVL Tree Implementierung. Es erledigt den Job, aber nicht schnell genug.

Es führt 48 von 100 in 12s.

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

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); 
    } 

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

Ich habe ein zweiter Ansatz, der schneller, aber immer noch nicht schnell genug ist. Es führt 84 von 100 in 12ms;

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

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 Ich möchte verstehen, warum sie das Ziel nicht erreichen und wie ich sie verbessern kann.

Answer 1

OK, ich habe Ihren Code durch Refactoring beschleunigt.

Ich wäre neugierig zu wissen, dass sie auf diese Funktion werfen, dass es so lange dauert, um zu berechnen. Wir sprechen von 100 Berechnungen in 12 Sekunden, nicht in 12 ms. Ich würde sagen, große Arrays und viele verschiedene Werte (entweder schwebt oder die gesamte Palette von Ints, nicht nur wie 8 Bit: 0 ... 255).

Noch verschiedene Ansätze versuchen.

Answer 2

Das ist in Ordnung, aber ich weiß nicht, was (codewars?) Herausforderung ist, denn ich kann es nicht testen. Verwendet keine Bäume.

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

ich es ohne einen Baum tun, nur mit einer einfachen verlinkte Liste:

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");

hätte einen schnellen Test in der Konsole der drei vier Ausführungen mit 100000 Werte.

• erster Code: ~ 700-800ms
• Ihr zweiten Code: ~ 350-400ms
• meinen Code: ~ 15-30ms
• James' Code: ~ 25000ms

Alle Implementierungen wurden auf demselben vorgenerierten Array mit 100.000 Elementen getestet.

Das Exportieren des Node-Konstruktors aus smaller erhöht die Leistung, so dass der 2. und 3. Test eher bei 15ms als bei 30ms ist. Dies hat damit zu tun, wie die JS Engine den Code optimieren kann. Auch das Vorfüllen des Arrays mit 0 Werten beschleunigte den Code um das Zehnfache.

Aber die Unterschiede sollten für kurze Arrays oder Arrays mit mehr als 100 verschiedenen Werten kleiner sein.