如何让此代码更快运行
该数组包含数字并且未排序。它的长度可能大到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树的实现。它完成了工作,但速度不够快。
它在12s中执行48中的100个。
===============
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);
}
=================
我有一个第二种方法虽然速度更快但仍不够快。 它在12ms内执行84次中的100次;
=================
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);
}
=================
我想了解为什么他们没有达到目标,我该如何改进他们。
好的,我已经通过做一些重构来提高代码速度。
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秒内讨论100个计算,而不是12ms。我猜想大数组和很多不同的值(浮点数或使用整个范围的整数,不只是8位:0 ... 255)。
仍在尝试不同的方法。
非常感谢你,我真的没有想到制作这种小小的改变会产生变化。 –
您从'small'中提取'BSTNode'和'insert'所获得的主要改进,因此它不会为每个'smaller'调用创建一个新的Class和Function,因此引擎可以优化所有内容,因为它们总是使用相同的类型。通过以适当的大小初始化'result'数组,并填充零值,所以引擎不必调整数组的大小,也不必处理访问未定义的属性/索引,因为所有的值是整数,它可以在内部优化这个数组,因为它更快,更高效地存储数组。 – Thomas
这是体面的,但我不知道什么(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(","));
https://www.codewars.com/kata/how-many-are-smaller-than-me-ii/train/javascript –
我可以做无本之木,只是一个简单的链表:
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");
在 3个四种实现与控制台做了一个快速测试100000个值。
- 您的第一个代码:〜700-800ms
- 你的第二个代码:〜350-400ms
- 我的代码:〜15-30ms
- 詹姆斯代码:〜25000ms
所有实现都在相同的100000项的预生成数组上进行测试。
从smaller
中导出节点构造函数会提高性能,因此第2次和第3次测试更有可能在15ms时比30ms时更长。这与JS引擎如何优化代码有关。同时用0
值预填充阵列可使代码速度提高约10倍。
但是,对于短阵列或具有超过100个不同值的阵列,差异应该更小。
你需要比O(n^2)更快的东西。你可以自己做这个练习:https://www.codewars.com/kata/how-many-are-smaller-than-me-ii/train/javascript –
这属于codereview – mplungjan
在更快的机器上运行它。 – destoryer