第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

JavaScript:mergeSort 返回 RangeError:超出最大調(diào)用堆棧大小

JavaScript:mergeSort 返回 RangeError:超出最大調(diào)用堆棧大小

偶然的你 2022-07-21 21:18:40
我目前正在嘗試在 Javascript 中實現(xiàn) mergeSort。我收到以下錯誤:用戶/stevenaguilar/Desktop/algorithms/merge/merge-sort.js:36 sort(a, lo, hi) { ^ RangeError: 最大調(diào)用堆棧大小在 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 創(chuàng)建合并排序,并且能夠?qū)?shù)組進行排序。不知道為什么我在 JavaScript 中遇到上述錯誤,因為我在Node  v14.0.0 這里運行的是合并排序的實現(xiàn):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條經(jīng)驗 獲得超13個贊

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


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


this.aux在多個方法調(diào)用和調(diào)用之間持續(xù)存在錯誤已經(jīng)成熟,感覺就像過早的優(yōu)化;將其完全設(shè)置為sort方法的本地可以提高可讀性、封裝性并確保在調(diào)用之間沒有陳舊的數(shù)據(jù)存在。是的,為每一幀創(chuàng)建一個數(shù)組merge很昂貴,但是如果需要優(yōu)化,可以將合并數(shù)組添加到閉包中或作為參數(shù)傳遞?;蛘吆喜⒖梢跃偷赝瓿伞T僬f一次,Array#sort如果性能是您的目標(biāo),這是更好的選擇。


我還發(fā)現(xiàn),使用傳統(tǒng)的數(shù)組長度協(xié)議運行所有拆分,其中l(wèi)o包含mid和lo不包含以及包含和不mid包含的第二個塊更直觀。這避免了我覺得更難推理的和循環(huán)。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`);


查看完整回答
反對 回復(fù) 2022-07-21
  • 1 回答
  • 0 關(guān)注
  • 133 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯(lián)系客服咨詢優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動學(xué)習(xí)伙伴

公眾號

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號