代码之家 › 专栏 › 技术社区 › epsilon

大堆通过递归减少实现

algorithm javascript

epsilon · 技术社区 · 8 年前

我正在尝试实现数组。reduce()方法通过递归,它对我有用

var index = 0;
function reduce(arr, fn, initial) {
    if (index >= arr.length) {
        return initial;
    }
    if (!initial) {
        initial = arr[index];
        index++;
    }
    initial = fn(initial, arr[index], index, arr);
    index++;
    return reduce(arr, fn, initial);
}

但验证者不接受我的回答。我做错了什么?

3 回复 | 直到 8 年前

trincot 8 年前

一些问题:

您定义 index 作为一个永远不会重置为0的全局变量 reduce 如果多次调用,则其值将错误。有几种解决方案。我建议使用 this 跟踪您所在位置的价值。
这个 initial 参数是可选的,但您的代码使用 !initial 这还不够好:如果 最初的 为0或任何其他falsy值,则不应将其视为不存在。使用 arguments.length 相反
当您增加索引时,因为 最初的 未提供参数,您不会检查该索引是否变得太大。绝不应使用无效索引调用回调函数。将两者互换 if 声明。
当传递的空数组没有初始值时, 减少 退货 undefined ,但它应该抛出一个错误,就像本机一样 减少 方法
当数组有“间隙”(即,它是一个稀疏数组)时,该函数仍会对缺少的索引调用回调函数。相反,不应该迭代那些不存在的条目。可以通过使用数组迭代器来实现这一点,该迭代器只生成有效的索引。

以下是您可以如何处理这些问题:

function reduce(arr, fn, initial) {
    // Get iterator for the indexes from `this`. 
    // The first time it will not be an iterator, so get it from arr.keys().
    const iter = Object(this).next ? this : arr.keys(); 
    let item = iter.next();
    if (arguments.length < 3) { // Solid check for presence of initial argument
        // Throw error when there's nothing to reduce
        if (item.done) {
            throw new TypeError("reduce of empty array with no initial value"); 
        }
        initial = arr[item.value];
        item = iter.next();
    }
    // Check end of array only after having dealt with missing initial value
    if (item.done) return initial;
    initial = fn(initial, arr[item.value], item.value, arr);
    return reduce.call(iter, arr, fn, initial); // Pass on the index via `this`
}

// Some test cases
console.log(reduce([1, 2, 3], (a, b) => a+b, 0), "should be 6");
console.log(reduce([1, 2, 3], (a, b) => a+b, 0), "should be 6");
console.log(reduce([1, 2, 3], (a, b) => a+b), "should be 6");
console.log(reduce([1], (a, b) => a+b), "should be 1");
console.log(reduce([1], (a, b) => a+b, 2), "should be 3");
console.log(reduce([], (a, b) => a+b, 1), "should be 1");
try {
    console.log(reduce([], (a, b) => a+b), "error");
} catch(e) {
    console.log("Error was raised as expected");
}

这个 这 引用是函数的私有引用,调用方无法看到它,因此使用它传播当前状态(迭代器)似乎很理想。备选方案包括:

使用额外参数
向数组或回调函数参数添加属性。

最后一个选项的缺点是调用方可以检测到这种突变。在调用方冻结这些对象的极端情况下,代码甚至会出现异常而失败。

所有解决方案都有一个缺陷:原始调用方可以通过初始调用传递状态。因此,对于每个解决方案,调用方都可以传递索引(或迭代器)的特定值,如下所示:

用一个值传递一个额外的参数——比如说5。
设置特殊 指数 传递给的函数的属性 减少 值为5。
呼叫 减少 具有 call 或 apply ,为其提供特定 这 值(迭代器)。

对此无能为力,因为要求使用递归。由于递归要求,函数在递归调用中所能做的一切都是原始调用方所不能做的。

Nina Scholz 8 年前

一种可能的解决方案是将实际索引放入函数参数中,并检查数组中是否存在索引。

为了找到 initialValue 您需要一个符号来表示未定义的值,以便在未定义的值和未设置的值之间进行区分。

function reduce(array, fn, initialValue, index) {
    index = index || 0;

    if (arguments.length === 0) {
        throw 'Reduce: No array';
    }

    if (arguments.length === 1 || typeof fn !== 'function') {
        throw 'Reduce: No function';
    }

    if (arguments.length === 2) {
        while (index < array.length && !(index in array)) {
            index++;
        }
        if (index in array) {
            return reduce(array, fn, array[index], index + 1)
        }
        throw 'Reduce: Empty array without initial value';
    }

    if (index >= array.length) {
        return initialValue;
    }

    return reduce(array, fn, index in array ? fn(initialValue, array[index], index, array) : initialValue, index + 1);                
}
   
// console.log(reduce());                     // throws Reduce: No array
// console.log(reduce([]));                   // throws Reduce: No function
// console.log(reduce([], (a, b) => a + b));  // throws Reduce: Empty array without initial value
console.log(reduce([], (a, b) => a + b, 42));
console.log(reduce([3, 4], (a, b) => a + b));

×××¢× ××¨×§× 8 年前

正如您所发现的那样,将索引参数放置在函数之外会导致复杂性,即必须持续管理索引参数才能使函数工作。我认为,通常情况下,编写函数的赋值都假设它们是自包含的,而不是依赖于全局变量。

我们可以概念化 reduce 递归地如下所示:

function reduce(arr, fn, initial){
  if (!arr.length)
    return initial;

  if (arr.length == 1)
    return fn(initial, arr[0]);

  return reduce(arr.slice(1), fn, fn(initial, arr[0]));
}

console.log(reduce([1,2,3], (a,b)=>a+b, 0)); // 6

在JavaScript中,每次调用 slice 生成数组该部分的副本,使此版本对于较大的输入效率较低。提高效率的一个选择是使用一个内部递归函数,该函数依赖于两个参数,一个索引和一个累加器,它将遍历数组,但我不确定验证器是否会允许它,因为外部函数将不再调用自身。

代码中还有一件事需要注意 !initial 无论何时都能抓住 initial 是一个计算结果为“falsy”的值,而不仅仅是当它没有作为参数传入时。

这里有一个“hack”ish(因为它修改了 fn ,虽然我们可以将其修改回:),但基于索引的解决方案不需要额外的参数,并使用 fn公司 :

function reduce(arr, fn, initial){
  if (fn.index === undefined)
    fn.index = 0;
  else
    fn.index++;

  if (fn.index == arr.length)
    return initial;

  return reduce(arr, fn, fn(initial, arr[fn.index], fn.index, arr));
}

console.log(reduce([1,2,3], (a,b)=>a+b, 0)); // 6