Question

是否有更好的方法来递归执行 shuffle 方法而不超出大型数组的最大调用堆栈？

2019-10-31

517

javascript arrays algorithm shuffle

我正在尝试编写一个 RECURSIVE 函数来随机化/打乱数组。

我编写的函数使用 Fisher-Yates 打乱方法，该方法在小型数组上运行良好，但在包含 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

Answer 1

任何像这样的循环：

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);

Answer 2

您始终可以使用 trampolining。

// 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()]));

这可让您将任何递归函数展平为迭代循环。