我怎样才能使此代码更快运行

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 个测试要执行，目标是在 12 毫秒内完成所有测试。以下函数是一个 AVL Tree 实现。它可以完成工作，但速度不够快。

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

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

我有第二种方法，它更快但仍然不够快。它在 12 毫秒内完成了 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);
}

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

我想了解为什么他们没有达到目标，我该如何改进他们。

Answer 1

这很不错，但我不知道这是为了什么（codewars？）挑战，所以我无法测试它。不使用树木。

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 2

我可以不用树，只需要一个简单的链表就可以做到：

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

function smaller(array){
 return array.reduceRight(function(root, value, i){
  var count = 0;
  for(var prev = root, node; (node = prev.next) && node.value < value; prev = node)
   count += node.count;
  root.counts[i] = count;
  
  if(node && node.value === value){
   node.count++;
  }else{
   prev.next = new Node(value, prev.next);
  }
  
  return root;
 }, {
  next: null, 
  counts: Array(array.length).fill(0) 
 }).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");

在具有 100000 个值的三个四个实现的控制台中进行了快速测试。

你的第一个代码：~700-800ms
你的第二个代码：~350-400ms
我的代码：~15-30ms
James 的代码：~25000ms

所有实施都在相同的预生成 100000 项数组上进行了测试。

从 smaller 导出节点构造函数提高了性能，因此第二次和第三次测试更有可能在 15 毫秒而不是 30 毫秒。这与 JS 引擎如何优化代码有关。此外，用 0 值预填充数组可将代码速度提高约十倍。

但对于短数组或具有超过 100 个不同值的数组，差异应该更小。

Answer 3

好的，我已经让你的代码通过重构来加速。

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

我很想知道他们抛出了这个需要很长时间才能计算的函数。我们谈论的是在 12 秒而不是 12 毫秒内进行 100 次计算。我猜是大数组和许多不同的值（浮点数或使用整个整数范围，而不仅仅是 8 位：0 ... 255）。

仍在尝试不同的方法。

我怎样才能使此代码更快运行

How can I make this code to run faster

javascript

avl-tree

binary-search-tree

我怎样才能使此代码更快 运行

How can I make this code to run faster

javascript

avl-tree

binary-search-tree

我怎样才能使此代码更快运行