MapReduce算法寻找连续序列

Question

我需要编写一个小的map/reduce函数，如果数组中至少有4个连续的0，则应返回1，否则应返回与1不同的其他值。

示例：

[6, 7, 5, 0, 0, 0, 0, 3, 4, 0, 0, 1] => 1

[6, 7, 5, 0, 0, 0, 3, 4,0, 0, 0, 0, 0, 1] => 1

[5, 0, 0, 0, 3, 4, 0, 0, 8, 0, 0, 1] => something # 1

这是我的算法：

[6, 7, 5, 0, 0, 0, 0, 3, 4, 0, 0, 1]
    .map((i) => i === 0 ? 1 : 0)
    .reduce((prev, i) => {
      if (i !== 0) {
         return prev + i;
      } else {
        if (prev >= 4) {
          return 4;
        }
        return 0;
      }
    }, 0);

.map方法会将0标记为1，非0标记为0。所以，[6,7,5,0,0,0,0,3,4,0,0,1] 变成了 [0,0,0,1,1,1,1,0,0,1,1,0]。然后使用.reduce方法来收集零的数量。

如果当前元素是1（表示输入数组中的0），它会返回前一个值加上当前值（1）。这意味着它代表着零的数量。如果当前项目是0（表示输入数组不为0），则当其小于4时重置prev为0，否则继续进行。

最后，如果值为4，则至少有4个连续的0。

该算法似乎在运行，但未能满足要求。如果输入有4个连续的0，则需要返回1，否则应返回任何非0数字。

您认为有什么方法可以做到这一点吗？

- James

---

如果您不需要对数组求和，那么使用 arr.toString().indexOf('0000') > -1 不是更简单吗？ - Daniel Lizik

重点是我需要使用Map-Reduce算法。这可以通过更具创意的方式完成，例如下面的答案。 - James

Answer 1

您可以使用 Array#some 及一个 this 对象来完成计数。

与 Array#reduce 相反，Array#some 允许在找到正确的计数后结束迭代。

function isContinuous(array) {
    return +array.some(function (a, i) {
        if (a === 0) {
            this.count++;
            return this.count === 4;
        }
        this.count = 0;
    }, { count: 0 });
}

console.log(isContinuous([6, 7, 5, 0, 0, 0, 0, 3, 4, 0, 0, 1]));
console.log(isContinuous([6, 7, 5, 0, 0, 0, 3, 4, 0, 0, 0, 0, 0, 1]));
console.log(isContinuous([5, 0, 0, 0, 3, 4, 0, 0, 8, 0, 0, 1]));

- Nina Scholz

---

这很酷，array 前面的 + 是什么意思？ - Muntasir Alam

some 返回 true 或 false，但我们需要一个数值，例如 1 表示 true，0（与 1 不同的值）表示 false。加号运算符是一元运算符，将其后面的值转换为 Number 类型。 - Nina Scholz

Answer 2

这是一个使用4位表示法的ES6函数，每个1位代表输入数组中的非零值。

仅保留最近的4位：每次迭代，下一位从右侧移入，同时丢弃最左边的位，始终保持4位。如果结果在任何时候变为零，则循环停止。

function has0000(arr) {
    let c = 1;
    return +!arr.every( n => c = (c*2+!!n) & 0xF );
}

console.log(has0000([6, 7, 5, 0, 0, 0, 0, 3, 4, 0, 0, 1]));
console.log(has0000([6, 7, 5, 0, 0, 0, 3, 4, 0, 0, 1]));

你的代码

尽管计算零的算法是正确的，但是当需要返回1时，返回值并不是1，反之亦然。

返回值是回调函数中最后一个返回的值，因此它表示一个计数，可以是任何非负数。

即使找到了4个连续的零，这个计数也可以从零重新开始，因此您失去了实际上已经匹配的“知识”。

主要修复方法是交换if语句，并首先执行if(prev >= 4)。这样，一旦计数达到4，您将保持该计数，无论其后跟着什么。它将不再重置为0。

第二个修复方法是检测最终返回值是否恰好为4，并将其转换为1。 必须以只有4才能转换为1的方式进行。您可以通过除以4来实现此目的。

因此，在不改变其他任何内容的情况下，只需进行最小的更改，即可得到纠正后的代码：

var res = [6, 7, 5, 0, 0, 0, 0, 3, 4, 0, 0, 1]
    .map((i) => i === 0 ? 1 : 0)
    .reduce((prev, i) => {
      if (prev >= 4) {
         return 4;
      } else if (i !== 0) {
         return prev + i;
      } else {        
        return 0;
      }
    }, 0) / 4;
    
console.log(res);

坚持仅使用map和reduce的缺点是，你无法在处理完所有输入元素之前退出。这很遗憾，因为一旦发现4个零，就没有理由继续执行了。此时结果已经是最终的了。

以下是更简洁格式的修正代码，我还省略了map，因为它是可以轻松整合到reduce回调中的：

var res = [6, 7, 5, 0, 0, 0, 0, 3, 4, 0, 0, 1]
    .reduce((prev, i) => prev >= 4 ? 4 : i ? 0 : prev + 1, 0) 
    / 4;
    
console.log(res);

- trincot

Answer 3

使用 .map 和 .reduce 来满足您的要求：

//the following returns 1 if there is at least 4 consecutive 0's
//otherwise returns 0, 2, 4 or 6:

function cons4zeroes(arr) {
  return arr
    .map((i) => i ^ 0 ? 0 : 2)
    .reduce((p, i) => p ^ 1 ?
      i ^ 0 ?
        (p + i) % 7 :
        0 :
      1,
      0)
}

console.log(
  cons4zeroes([6, 7, 5, 0, 0, 0, 0, 3, 4, 0, 0, 1]), " => 1"
);
console.log(
  cons4zeroes([6, 7, 5, 0, 0, 0, 3, 4, 0, 0, 0, 0, 0, 1]), " => 1"
);
console.log(
  cons4zeroes([5, 0, 0, 0, 3, 4, 0, 0, 8, 0, 0, 1]), " => something # 1"
);

这个解决方案基于您的逻辑，但将每个0映射到2而不是1，将1保留给当找到4个连续的0时。然后，对连续的2进行求和，在第4个零之前发现非零值时重置为0，取模7以在找到4个零时将和转换为1（4×2 = 1 mod 7）。

无使用.map()的替代方法：

//the following returns 1 if there is at least 4 consecutive 0's
//otherwise returns 0, 2, 4 or 6:

function cons4zeroes(arr) {
  return arr.reduce((p, i) => p ^ 1 ?
      i ^ 0 ? 0 : (p + 2) % 7 : 1, 0)
}

console.log(
  cons4zeroes([6, 7, 5, 0, 0, 0, 0, 3, 4, 0, 0, 1]), " => 1"
);
console.log(
  cons4zeroes([6, 7, 5, 0, 0, 0, 3, 4, 0, 0, 0, 0, 0, 1]), " => 1"
);
console.log(
  cons4zeroes([5, 0, 0, 0, 3, 4, 0, 0, 8, 0, 0, 1]), " => something # 1"
);

- Tomas Langkaas

Answer 4

总的来说，你的实现看起来不错，除了一个小细节：你应该将reduce函数的初始值指定为-3（并相应修改其主体以满足你的要求）。

下面提供了修改后的实现版本，在存在至少4个连续零的情况下返回1，否则返回以下其中一个值：-3、-2、-1或0。

var result = [6, 7, 5, 0, 0, 0, 0, 3, 4, 0, 0, 1]
    .map((i) => i === 0 ? 1 : 0)
    .reduce((prev, i) => {
      if (prev === 1) {
          return 1;
      }
      if(i === 0) {
          return -3;
      }
      return prev + (i === 1);
    }, -3);

console.log(result)

- stemm

---

谢谢，我最近才开始考虑这个。 - James