首頁猿問 JavaScript：mergeS...

JavaScript：mergeSort 返回 RangeError：超出最大調用堆棧大小

JavaScript

偶然的你 2022-07-21 21:18:40

我目前正在嘗試在 Javascript 中實現 mergeSort。我收到以下錯誤：用戶/stevenaguilar/Desktop/algorithms/merge/merge-sort.js:36 sort(a, lo, hi) { ^ RangeError: 最大調用堆棧大小在 Merge.sort (/Users/stevenaguilar/Desktop/algorithms/merge/合并-sort.js:36:7)輸入不是那么大，是一個包含 16 個元素的元素。a = ["M", "E", "R", "G", "E", "S", "O", "R", "T", "E", "X", "A","M", "P", "L", "E"]我能夠使用 Ruby 創建合并排序，并且能夠對數組進行排序。不知道為什么我在 JavaScript 中遇到上述錯誤，因為我在Node v14.0.0 這里運行的是合并排序的實現：class Merge { constructor() { this.aux = [] } sortPublic(a) { this.sort(a, 0, a.length - 1); } merge(a, lo, mid, hi) { let i = lo let j = hi var mid = mid + 1 for(let k = lo; k <= hi; k++) { this.aux[k] = a[k] } for(let k = lo; k <= hi; k++) { if(i > mid) { a[k] = this.aux[j++] } else if(j > hi) { a[k] = this.aux[i++] } else if(this.aux[j] < this.aux[i]) { a[k] = this.aux[j++] } else { a[k] = this.aux[i++] } } } sort(a, lo, hi) { if(lo >= hi) { return; } var mid = lo + (lo + hi) / 2 this.sort(a, lo, mid) this.sort(a, mid + 1, hi) this.merge(a, lo, mid, hi) }}let mergeSort = new Merge;console.log(mergeSort)let a = ["M", "E", "R", "G", "E", "S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"]mergeSort.sortPublic(a);這里有什么問題？

查看完整描述

1 回答

慕桂英4014372

TA貢獻1871條經驗獲得超13個贊

var mid = lo + (lo + hi) / 2有多個問題。如果您試圖防止溢出，lo + hi則有問題（正確的公式是lo + (hi - lo) / 2）。加lo回來算兩次。/ 2可能會給出一個浮點結果，這將破壞遞歸邏輯并作為索引失敗。

在設計方面，我認為沒有理由讓合并排序成為一個有狀態的類并創建一個實例來對數組進行排序。這是不必要的開銷，使調用代碼冗長，并可能引入錯誤。假設您需要一個類（即使這可能是矯枉過正），使這些方法static更有意義。

this.aux在多個方法調用和調用之間持續存在錯誤已經成熟，感覺就像過早的優化；將其完全設置為sort方法的本地可以提高可讀性、封裝性并確保在調用之間沒有陳舊的數據存在。是的，為每一幀創建一個數組merge很昂貴，但是如果需要優化，可以將合并數組添加到閉包中或作為參數傳遞?；蛘吆喜⒖梢跃偷赝瓿?。再說一次，Array#sort如果性能是您的目標，這是更好的選擇。

我還發現，使用傳統的數組長度協議運行所有拆分，其中lo包含mid和lo不包含以及包含和不mid包含的第二個塊更直觀。這避免了我覺得更難推理的和循環。midhimid + 1hi - 1<=

class MergeSorter {

static merge(a, lo, mid, hi) {

const sorted = [];

let i = lo;

let j = mid;

while (i < mid && j < hi) {

if (a[i] < a[j]) {

sorted.push(a[i++]);

}

else {

sorted.push(a[j++]);

}

while (i < mid) sorted.push(a[i++]);

for (let i = 0; i < sorted.length; i++) {

a[lo++] = sorted[i];

}

static sort(a, lo=0, hi=a.length) {

if (lo < hi - 1) {

const mid = Math.floor((lo + hi) / 2);

MergeSorter.sort(a, lo, mid);

MergeSorter.sort(a, mid, hi);

MergeSorter.merge(a, lo, mid, hi);

}

const a = [..."MERGESORTEXAMPLE"];

MergeSorter.sort(a);

console.log(a.join(""));

const rnd = n => ~~(Math.random() * n);

let passes = 0;

const tests = 10000;

for (let i = 0; i < tests; i++) {

const a = Array(rnd(25)).fill().map(() => rnd(25));

const b = a.slice();

MergeSorter.sort(a);

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

if ("" + a === "" + b) {

passes++;

}

console.log(`${passes}/${tests} tests passed`);

反對回復 2022-07-21

1 回答
0 關注
134 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

JavaScript：mergeSort 返回 RangeError：超出最大調用堆棧大小

JavaScript：mergeSort 返回 RangeError：超出最大調用堆棧大小

1 回答

添加回答