Есть ли лучший метод для рекурсивного выполнения метода shuffle без превышения максимального стека вызовов для больших массивов? - PullRequest
Новая
       36

Есть ли лучший метод для рекурсивного выполнения метода shuffle без превышения максимального стека вызовов для больших массивов?

0 голосов
/ 31 октября 2019

Я пытаюсь написать функцию RECURSIVE, которая рандомизирует / перемешивает массив.

Написанная мною функция использует метод случайного преобразования Фишера-Йейтса, который отлично работает на небольших массивах, но выдает «Максимальная ошибка превышения стека вызовов» в моем предполагаемом массиве, содержащем 5000 элементов

Я задавался вопросом, может ли кто-нибудь помочь мне исправить этот метод так, чтобы он все еще работал рекурсивно на больших массивах?

Вот функция ниже: 

shuffleArray = (array, currentIndex=0) => {
    if (currentIndex >= array.length) {
      return array;
    }

    let randomIndex = Math.floor(Math.random() * currentIndex);

    let tempValue = array[currentIndex];
    array[currentIndex] = array[randomIndex];
    array[randomIndex] = tempValue;
    let newIndex = currentIndex += 1;
    return this.shuffleArray(array, newIndex);
  }

console.log(shuffleArray([1, 2, 3, 4, 5, 6]));
// returns a random array like [3,4,6,1,2,5]

console.log(shuffleArray([...Array(5000).keys()]));
// an example array of 5000 elements returns error: Uncaught RangeError: Maximum call stack size exceeded

Ответы [ 2 ]

1 голос
/ 31 октября 2019

Любой цикл, подобный следующему: 

for (let i = 0; i < n; i++) {
    // do something with i
}

Может быть бессмысленно, но рекурсивно расширен в пространство O (log n): 

function foo(start, end) {
    if (start + 1 === end) {
        // do something with start
    } else {
        let mid = start + Math.floor((end - start) / 2);
        foo(start, mid);
        foo(mid, end);
    }
}

foo(0, n);
0 голосов
/ 31 октября 2019

Вы всегда можете использовать прыжки на батуте. 

// data Trampoline a where

// Result :: a -> Trampoline a
const Result = result => ({ bounce: false, result });

// Bounce :: (a -> Trampoline b) -> a -> Trampoline b
const Bounce = func => (...args) => ({ bounce: true, func, args });

// trampoline :: Trampoline a -> a
const trampoline = t => {
    while (t.bounce) t = t.func(...t.args);
    return t.result;
};

// _shuffleArray :: ([a], Int) -> Trampoline [a]
const _shuffleArray = Bounce((array, currentIndex) => {
    if (currentIndex >= array.length) return Result(array);
    let randomIndex = Math.floor(Math.random() * currentIndex);
    [array[currentIndex], array[randomIndex]] = [array[randomIndex], array[currentIndex]];
    return _shuffleArray(array, currentIndex + 1);
});

// shuffleArray :: [a] -> [a]
const shuffleArray = array => trampoline(_shuffleArray(array, 0));

// Shuffle 100k numbers without a stack overflow.
console.log(shuffleArray([...Array(1e5).keys()]));

Это позволяет объединить любую рекурсивную функцию в итерационный цикл.

...