尾部呼叫优化javascript

Question

注意：这只是为了学习和改善自己。我知道数组的可用排序方法。我只是试图让TCO的基础知识降低。

当前尝试使用递归进行排序算法。但是，当我尝试处理大型数据集（+4000对象）时，我仍然遇到堆栈溢出错误。我正在尝试实施TCO。我对这个概念相当陌生，但我认为我有这个主意。但是，我仍然收到堆栈溢出错误。

const sort = (arr, counter) => { 
    if (!counter) { 
    counter = arr.length - 1; 
    } 
    for (let n = 1; n <= counter; n++) { 
    if(arr[n - 1] < arr[n]) { 
     let placeHolder = arr[n]; 
     arr[n] = arr[n - 1]; 
     arr[n - 1] = placeHolder; 
    } 
    } 
    counter -= 1; 
    return counter === 0 ? arr : sort(arr, counter); 
}; 

function sortRecursive(arr) { 
    return sort(arr); 
} 

UPDATE：

我设法得到它的工作，但我不明白为什么。我设法处理了10万次递归，没有任何问题。我必须移动检查计数器是否定义的布尔值。但是，我不太明白为什么会使它工作。

const sort = (arr, counter) => { 
    if (!counter) { 
    counter = arr.length - 1; 
    } 
    for (let n = 1; n <= counter; n++) { 
    if(arr[n - 1] < arr[n]) { 
     let placeHolder = arr[n]; 
     arr[n] = arr[n - 1]; 
     arr[n - 1] = placeHolder; 
    } 
    } 
    counter -= 1; 
    if (counter === 0) { 
    return arr; 
    } else { 
    return sort(arr, counter); 
    } 
}; 

function sortRecursive(arr) { 
    return sort(arr, arr.length - 1); 
} 

OUTPUT：

let firstArr = []; 
let secondArr = []; 

for (let x = 0; x < 100000; x++) { 
    firstArr.push(Math.ceil(Math.random() * 100000)); 
    secondArr.push(Math.ceil(Math.random() * 100000)); 
} 

sortRecursive(firstArr); 
//Array[100000] 

Answer 1

为什么你需要递归（因为这超过了每调用堆栈它决不会与4000+ elems的工作）？不能这样做：

const sort = (arr) => { 
    var counter = arr.length; 
    while(counter-->0){ 
     for (let n = 1; n <= counter; n++) { 
      if(arr[n - 1] < arr[n]) { 
       let placeHolder = arr[n]; 
       arr[n] = arr[n - 1]; 
       arr[n - 1] = placeHolder; 
      } 
     } 
    } 
    return arr; 
} 

如果您想得到怎样的递归，您可以使用qeue保持栈空（需要传递一个回调）：

setTimeout(sort,0,arr,counter);//instead of sort(arr,counter); 

顺便说一句，更容易和更快（因为它本身实现）：

arr.sort((a,b)=>a-b); 

Answer 2

正如你可能知道，尾调用optimizati on是一种编译器技术，可以通过每次递归调用不分配更多的内存来允许程序无限递归。

Javascript is not当前尾部调用优化，但语言规范的ES2015标准包含TCO。每当一个函数在Javascript中调用它自己时，就会创建一个新的堆栈框架，分配新的内存，所以它最终会耗尽并崩溃。

有技巧可以避免这种情况，包括trampolines而不是使用递归循环。但目前你无法在Javascript中无限递归。

Answer 3

你是肯定你正在获得尾部呼叫优化？

下面是您的更新代码的测试。我改变的唯一的东西是：

1. 添加'use strict';将代码置于严格模式。一些支持未来TCO的浏览器可能需要严格的模式才能使用TCO。
2. 添加console.trace()可打印每个sort()调用的调用堆栈。
3. 更改测试阵列设置为使用Math.floor()而不是Math.ceil()由于我上面评论中提到的原因。
4. 将数组长度更改为10。

打开开发人员控制台，然后运行该代码段并观察调用堆栈跟踪。

我在最新版本的Chrome 59.0.3071.109，Firefox 54.0和Edge 15.15063中测试了这个版本。来自所有人的堆栈跟踪显示每次调用都会增加调用堆栈，表明没有调用优化。

只是踢，我也试过在Chrome浏览器length = 100000。它运行了很长时间，大概一分钟左右，然后堆栈达到大约10257个调用深度时发生堆栈溢出失败。为了比较，在大约5秒内完成标准sort(function(a, b) { return b - a; })。

这是一个很好的article about JavaScript tail call optimization and related topics。文章提到的其中一件事是，通过使用--harmony_tailcalls命令行开关以及'use strict';，您可以在node.js中获得TCO。

'use strict'; 
 

 
const sort = (arr, counter) => { 
 
    console.trace(); 
 
    if (!counter) { 
 
    counter = arr.length - 1; 
 
    } 
 
    for (let n = 1; n <= counter; n++) { 
 
    if(arr[n - 1] < arr[n]) { 
 
     let placeHolder = arr[n]; 
 
     arr[n] = arr[n - 1]; 
 
     arr[n - 1] = placeHolder; 
 
    } 
 
    } 
 
    counter -= 1; 
 
    if (counter === 0) { 
 
    return arr; 
 
    } else { 
 
    return sort(arr, counter); 
 
    } 
 
}; 
 

 
function sortRecursive(arr) { 
 
    return sort(arr, arr.length - 1); 
 
} 
 

 
let firstArr = []; 
 
let length = 10; 
 

 
for (let x = 0; x < length; x++) { 
 
    firstArr.push(Math.floor(Math.random() * length)); 
 
} 
 

 
console.clear(); 
 
sortRecursive(firstArr); 
 
//firstArr.sort(function(a, b) { return b - a }); 
 
console.log(firstArr);