テールコールの最適化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

ご存知のとおり、テールコール最適化（tail call optimizati） onは、各再帰呼び出しごとにより多くのメモリを割り当てないことによってプログラムが無限に繰り返すことを可能にするコンパイラ技術です。

JavaScriptはではありません。現在テールコールは最適化されていますが、言語仕様のES2015規格にはTCOが含まれています。関数がJavascriptで関数を呼び出すたびに、新しいスタックフレームが作成され、新しいメモリが割り当てられるため、最終的にメモリが使い果たされてクラッシュします。

trampolinesなど、再帰的ループを使用しないなど、これを回避する方法があります。しかし、現時点ではJavascriptで無限に再帰的にすることはできません。

Answer 3

あなたはテールコールの最適化を取得していますか？

ここには、更新されたコードのテストがあります。私が変更したのは以下の通りです：

1. 厳密なモードでコードを入力するために'use strict';が追加されました。将来TCOをサポートする一部のブラウザでは、TCOを使用するために厳密なモードが必要になる場合があります。
2. sort()呼び出しごとにコールスタックを出力するためにconsole.trace()が追加されました。
3. Math.ceil()の代わりにMath.floor()を使用するようにテストアレイの設定を変更しました。
4. 配列の長さを10に変更しました。

スニペットを実行する前に開発者用コンソールを開いて、コールスタックのトレースを観察します。

私はこれをChrome 59.0.3071.109、Firefox 54.0、およびEdge 15.15063の最新バージョンでテストしました。すべてのスタックトレースは、各コールでコールスタックが増加していることを示し、テールコールの最適化がないことを示します。

ちょうどキックのために、私もlength = 100000でChromeで試しました。スタックはスタックが約10257コールの深さに達したときにスタックオーバーフローが発生し、非常に長い時間（おそらく1分ほど）実行されました。比較のために、標準sort(function(a, b) { return b - a; })が約5秒で完了した。

ここはいいarticle about JavaScript tail call optimization and related topicsです。この記事で言及していることの1つは、'use strict';と一緒に--harmony_tailcallsコマンドラインスイッチを使用して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);