Uncaught RangeError: Максимальный размер стека вызовов превышен в p5. js - PullRequest
Новая
       14

Uncaught RangeError: Максимальный размер стека вызовов превышен в p5. js

1 голос
/ 25 апреля 2020

Am Пытается запустить алгоритм слияния в p5. js, но function mergesort(arr, start, end) выдает ошибку (превышен максимальный размер стека вызовов). Вывод должен быть отсортированным массивом, отображаемым в виде строк в окне браузера.

Вот мой код: 

var values = []

function setup(){
    createCanvas(600,400);
    values.length = width;
    for(let i=0; i<values.length; i++){
        values[i] = random(height);
    }
    mergesort(values, 0, values.length-1)
}

function draw(){
    background(0);
    for (let i=0; i< values.length; i++){
        stroke(255,0,255);
        line(i, height, i, height - values[i]);
    }
}

function mergesort(arr, start, end){
    if(arr.length <= 1)
        return;

    let middle =arr.length/2

    mergesort(arr, start, middle);
    mergesort(arr, middle +1, end);
    merge(arr, start, middle, end);
}
function merge(arr, start, middle, end){
    let sizeL = middle - start;
    let sizeR = middle - end;
    let arrL = [];
    let arrR = [];
    for (let i = start; i < sizeL; i++) 
        arrL.push(arr[i])
    for (let j = sizeR; j < end; j++) 
        arrR.push(arr[j])
    let a = 0; 
    let b = 0;
    let k = 1;
    while (a< sizeL && b < sizeR){
        if (arrL[i] <= arrR[b]){
            arr[k] = arrL[a]; 
            a++; 
        } 
        else{
            arr[k] = arrR[b]; 
            b++; 
        } 
        k++; 
    } 
    while (a < sizeL){ 
        arr[k] = arrL[b]; 
        a++; 
        k++; 
    } 
    while (b < sizeR) { 
        arr[k] = arrR[b]; 
        b++; 
        k++; 
    }
}

Пожалуйста, исправьте ошибку

1 Ответ

1 голос
/ 25 апреля 2020

Длина массива никогда не изменяется, поэтому условие if(arr.length <= 1) никогда не прекратится, и результат let middle = arr.length/2 всегда будет одинаковым.

Вам необходимо оценить, если end - start <= 1, и вычислить middel by (start + end)/2: 

function mergesort(arr, start, end){
    if(end - start <= 0)
        return;

    let middle = Math.floor((start + end)/2);

    mergesort(arr, start, middle);
    mergesort(arr, middle+1, end);
    merge(arr, start, middle, end);
}

Более того, есть некоторые проблемы с индексацией. Обратите внимание, что в merge аргументы start, middle, end являются индексами. Следовательно, длины массивов middle - start + 1 соответственно end - middle. И вы должны поместить отсортированные элементы, начиная с start, таким образом k = start: 

function merge(arr, start, middle, end){
    let sizeL = middle - start + 1;
    let arrL = [];
    for (let i = start; i < middle+1; i++) 
        arrL.push(arr[i])

    let sizeR = end - middle;
    let arrR = [];
    for (let j = middle+1; j < end+1; j++) 
        arrR.push(arr[j])

    let a = 0, b = 0, k = start;

    // [...]
}

Код можно упростить, используя Array slice() метод : 

let arrL = arr.slice(start, middle+1);
let arrR = arr.slice(middle+1, end+1);

См. Пример: 

var values = []

function setup(){
    createCanvas(600,400);
    values.length = width;
    for(let i=0; i<values.length; i++){
        values[i] = random(height);
    }
    mergesort(values, 0, values.length-1)
}

function draw(){
    background(0);
    for (let i=0; i< values.length; i++){
        stroke(255,0,255);
        line(i, height, i, height - values[i]);
    }
}

function mergesort(arr, start, end){
    if(end - start <= 0)
        return;

    let middle = Math.floor((start + end)/2);

    mergesort(arr, start, middle);
    mergesort(arr, middle+1, end);
    merge(arr, start, middle, end);
}

function merge(arr, start, middle, end){
    let sizeL = middle - start + 1;
    let arrL = arr.slice(start, middle+1);
    
    let sizeR = end - middle;
    let arrR = arr.slice(middle+1, end+1);
    
    let a = 0, b = 0, k = start;
    while (a< sizeL && b < sizeR){
        if (arrL[a] <= arrR[b]){
            arr[k++] = arrL[a++]; 
        } 
        else{
            arr[k++] = arrR[b++];  
        } 
    } 
    while (a < sizeL){ 
        arr[k++] = arrL[a++]; 
    } 
    while (b < sizeR) { 
        arr[k++] = arrR[b++]; 
    }
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/1.0.0/p5.min.js"></script>
...